基于核心节点的网络社区发现方法研究

张拥华

（湖南工业职业技术学院，湖南 长沙 410208）

1 引言

随着信息技术的飞速发展，各种开放式的电子商务应用平台不断涌现，人们之间的沟通越来越多地依赖于虚拟的交互平台和现代技术手段，虚拟的社会网络开始走进人们的生活，并诞生了网络社区的新生事物。对网络社区的数据进行分析、挖掘，揭示数据背后的规律、知识，作为各种不同应用的决策支撑成为许多研究人员关注的领域。虚拟的网络社区不同于真实世界的社会，网络社区的成员通常存在许多交集，而且一个成员可能归属于不同的社区，从而存在重叠的现象，匈牙利的社会科学家Palla通过大量的实验证明重叠社区现象存在的普遍性，可以用贴标签的方式来形象地描述重叠社区与非重叠社区的区别，非重叠社区就是社区中的节点只能贴上一个标签，表示该节点只能归属于这一个社区，而重叠社区则没有这个限制，社区中任意一个都可以贴上多个标签，表示这个节点同时属于这些社区，就好比我们同时加入好多个兴趣圈子，里面有音乐圈子、篮球圈子、运动养生圈子等等。基于Palla的派系过滤理论的方法有：T.S.Evans的Clique Graph[1]，CPM算法[2]，基于极大子团合并的EAGLE算法[3]。

由于网络规模呈不断增加的趋势，在进行社区发现过程中，难以获得网络的全局信息，因此，研究人员提出从网络的局部信息入手进行研究，并设计了基于局部社区的算法，实验证明采用局部社区进行计算的算法能成功获得社区结构，同时，也可以使用在重叠社区与非重叠社区发现工作中，具有重要的实践意义和价值，具有代表性的算法主要包括：基于极大子团扩张的GCE算法[4]、Clauset的Local Modularity方法[5]等。

本文将针对传统社区发现算法的不足之处，提出一种基于核心节点的局部社区扩张算法EALCN（Expansion Algorithm based on Local Community Core Nodes），并对算法的时间复杂度进行分析，最后通过仿真实验证明该算法在大多数高度重叠的社区发现上具有一定的优势，具有一定的可行性。

2 问题定义

在本文中，网络都被定义成多个局部社区的集合，而局部社区则是由核心节点以及围绕这个核心节点的一系列的节点组成。一个节点是否被纳入到一个社区中则是由适应度函数F来决定，一个局部社区S包含节点n，当且仅当n满足F(n)＞0。局部社区都是从一个初始节点开始，通过适应度函数不断判断社区外的节点是否加入到社区中，从而不断壮大社区规模，直到没有合适的节点可以加入社区中。经过多次的迭代之后，网络中所有节点便都分配到不同的社区中。如图1所示，是一个局部社区的例子，图中的网络由几个结构非常明显的局部社区构成，红色节点表示核心节点，其具有极大的度数，黑色的节点则是普通成员节点。从图中我们可以很清晰看到重叠社区重叠部分高度重叠的特征，重叠的程度通常都是跟初始节点以及适应度函数相关。

图1 一个局部社区的例子

3 基于核心节点的局部社区发现算法

局部社区的发现大体都是由一个种子节点开始，然后经过不断地扩张，最终形成一个社区。诸如LFM这些传统的社区发现算法，通常都是采用随机的方式选取初始节点，这样选出来的节点往往都不是核心节点，这样就会造成算法的准确性极低。GCE算法尝试使用网络中的极大子团替代节点作为种子扩张，但是极大子团的获取需要大量的计算，这就使得算法的效率大幅度降低。根据网络节点度的分布特征我们知道，网络中度数很大的节点是少量的，大多数节点度是很小的，而这些度数很大的节点往往也是社区的核心，所有我们完全可以通过找出这类节点作为种子节点来进行扩张。考虑到权重对种子节点的影响，我们在选取种子节点时，将权重也加入影响因素中。基于此，本文提出了一种基于核心节点的社区发现算法，该算法首先发现网络中的一系列核心节点，然后将他们的跟随者加入到社区中，从而形成社区结构。具体流程如图2所示。

图2 算法流程图

3.1 种子节点的选取

在现实生活中，每个人都有自己的兴趣圈子，在这些圈子里每个人都扮演者不同的角色，比如你关注的某个网络主播要开始主播，你可能就会去加入到这个圈子中去，但是这个主播是这个圈子的核心，起着引导作用，而大多数的关注只是一个普通的参与者。这个就清晰地反映出在一个社交圈中，每个人的影响力是不同的，他对这个社交圈所起到的作用也就不一样，换句话说就是他在这个社交圈中的重要性不一样。上文提到过，我们认为局部社区就是核心节点及其跟随者所构成的群体结构。因此，最快找出这个社区的方法就是先找出其核心节点，然后再围绕核心节点进行社区扩张。由无标度网络模型，我们知道网络中的节点大多数度数是很小的，只有少量的节点的度数很大。那么假设网络中的每一个节点都至少归属于一个社区(独立节点自成一个社区)，则社区中必定会存在着这样一个核心节点。

首先，本文对PageRank算法进行改进，使其能够适应无向图的节点排序，以找出网络中的潜在核心节点。

G=＜V,E,w＞是一个无向加权网络，w表示权重，则任意节点i的PR值为：

其中，N是网络G中节点总数；wij为边ij的权重；c为调节因子，为一个常数，通常设置为0.85左右，Si即为节点的度。上述定义是基于递归定义的。可以看出，每个节点的PR值都依赖于其邻接节点的PR值，而且后者会按照自身权值与前者所有邻接节点权值之和之比来将自身的PR值分配给前者。

具体的PR值计算请看下列中的伪代码：

?

经过排序后的节点，排名靠前的都有成为核心节点的潜质了，但是，初始化是非常关键的。选择一个正确的节点作为初始节点进行扩张可以快速地得到一个正确的社区结构，然而从一个错误初始节点开始那么结果往往是很糟糕的。为了避免先后选出的节点都位于同一个社区中，本文采取了更少的邻居节点的方法，即在选择核心节点时，先判断此节点与先前的核心节点的共同邻居数，当这个数大于阈值时，则弃置它，即核心节点之间的共同邻居数必须小于阈值β。

3.2 局部社区的扩张

本算法定义了一个适应度函数，只有选取了适当的种子节点，便可以通过贪婪算法来不断扩大适应度函数，从而获取得到一个最优的社区结构。该适应度函数可以计算出任意子图的适应度，子图的适应度反映出了子图内部与外部的连接密度情况，对子图做任何的修改都会引起适应度的变化。通过不断修改子图的成员，添加或者删除，使得子图的适应度不断增大，直到子图的适应度不在发生变化为止，此时便得到了最优的社区结构。

对于一个给定的社区S,那么S的适应度为：

其中，Kin(s)是社区S的内部节点度数和，Kout(s)是社区S与外部的连接数之和,α为一个可控制社区规模大小的参数。

节点适应度是指一个节点对于社区适应度的贡献，所以对于一个给定的节点A，那么其对于社区S的节点适应度为：

其中，S+A表示将节点A加入社区S后的社区。

局部社区发现算法通常都是由一个初始节点开始，然后不断进行社区扩张，从而形成完整的社区结构。但是，算法的结果受到算法扩张模式的影响是极大的。一般地，算法中都出现节点震荡、重复计算和畸形生长的问题，因此，本文定义的社区发现流程如算法2所示。

?

经过上述过程，便可以由一个初始核心节点得到一个社区结构。

3.3 局部社区的优化——合并冗余社区

几乎所有的重叠社区发现算法都无可避免地会遇到“过渡重叠”的问题，这类社区也被称为冗余社区。虽然我们在极力地提高种子节点的选择精准度，以及优化社区的扩张模式，但是网络本身的不确定性以及算法本身在参数的控制上存在的不确定性，会造成社区与社区之间出现严重的交叉现象。为了检测出社区间的冗余情况，以及合并冗余社区，本文定义了一个重叠度来定量地刻画社区的冗余情况。

给定两个社区C1和C2，则他们之间的重叠度为：

当社区的重叠程度超过阈值时，将两个社区进行合并操作，经过反复的实验，可以发现这个阈值设为0.65左右较为合适。在构造局部社区的同时，冗余社区的检测工作也在同步进行，在一个社区结构形成之后，立即对其检测，如果该社区的冗余度小于设定的阈值，便接受这个社区；如果大于设定的阈值，那么就放弃这个社区。通过反复进行这些操作，可以尽可能避免过度重叠的社区出现。

4 仿真与性能分析

为了证明本文所提出的EALCN算法的有效性，在如表1所示的环境下进行试验。

表1 实验环境

图3为原始网络图，图4为使用EALCN算法后得到的优化处理结果。

图3 原始网络图

图4 使用EALCN算法划分结果

比较图3和图4，使用EALCN算法可以获得多个覆盖全网络的局部社区，并且具有算法复杂度小、执行效率高的特点。

5 结束语

本文针对目前网络规模不断增大的情况下，难以获得网络全局信息的现实问题，利用网络中的局部信息来实现对目标函数的优化。具体而言是通过修改PageRank算法来获取初始核心节点，然后由初始核心节点开始，通过不断地优化目标函数来构建局部社区结构。实验证明，本文提出的EALCN算法能有效地改进网络社区的划分效果，提高社区划分的准确性。

[1]柴变芳,于剑,贾彩燕,等.一种姓于随机块榄喂的快速广义社区发现算法[J].软件报.2013,24(11):2699-2709.

[2].G.Palla,1.Derenyi,I.Farkas,T.Vicsek.Uncovering the overlapping community structure of complex networks in nature and society.Nature.2005,435(7043):814-818.

[3]H.Shen,X.Cheng,K.Cai,M.B.Hu.Detect overlapping and hierarchical community structure in networks.Physica A:Statistical Mechanics and its Applications.2009,388(8):1706-1712.

[4]C Lee,F Reid,A McDaid,N Hurley.Detecting highly overlapping community structure by greedy clique expansion IA].ln Proc.SNA-KDD Workshop1⋆"1,Washington DC,USA:IEEE,2010.33-42.

[5]A.Clauset.Finding local community structure in networks.Physical Review E.2005,72(2):026132+.