2. 厦门大学 自动化系, 厦门 361005
2. Automation Department, Xiamen University, Xiamen 361005, Fujian, P. R. China
社交网络中存在关系不均匀的现象,形成了社交网络中的社区结构[1-3]。网络中的社区结构有助于理解网络的拓扑结构,揭示复杂系统内部的规律,能够为信息推荐和信息传播控制提供有力支撑。目前学者们提出了很多社区发现算法,如谱平分法,模块度优化算法,标签传播算法[4](LPA, label propagation algorithm), 基于信息编码的算法[5](Infomap),基于随机游走的算法[6](Walktrap)。但是上述算法并不能够发现社区内部结构。
Rodriguez等[7]于2014年提出密度峰值聚类算法,能够得到稳定的聚类结果和聚类内部结构。该算法的核心思想在聚类中心的描述上,作者认为聚类中心同时具有2个特点:本身密度大,即被密度不超过它的邻居包围;与其它密度更大的数据点之间的“距离”相对较大。由于社区发现本质上是对网络节点进行聚类,因此该算法能够应用于社区发现中,并且在发现社区的基础上,确定每个社区内部的核心节点。但是在确定数据点的密度时需要给定截断距离,截断距离的选取会直接影响聚类效果。
黄岚等[8]通过相似度定义网络中各节点之间的距离,将密度峰值聚类算法应用于社区发现中, 提出一种基于点距离和密度峰值的社区发现算法(VDDPC, vertex distance and density peaks dustering);Wang[9]等引入了箱线图选取核心节点,将密度峰值聚类算法应用于重叠社区发现算法中;Wang[10]等基于密度峰值聚类算法,提出一种局部扩展的社区发现算法(LCCD, local expanding algorithm)。上述3种算法中截断距离是人为给定的,该参数的选取对社区发现的结果影响很大。Chen[11]等基于密度峰值聚类提出一种线性复杂度的社区发现算法,但是并未提出一种自动的核心节点获取方法。
为了避免参数选取不当对算法性能的影响,笔者提出一种基于信息传递和峰值聚类的自适应社区发现算法(AID, adaptive community detection method based on information transfer and density peaks)。首先,引入信息量来度量节点密度与节点间距离。节点信息量通过节点间的信息传递过程获取。定义信息传递过程基于节点间的信任度, 信任度越高的目的节点获取的信息量越大。用信息量来代替峰值聚类中密度,可避免截断距离的参数选取,且节点传播信息是独立的,易实现并行化。然后,提出一种自动选取核心节点的方法,从而完成整个网络的社区划分。
本算法主要优势:1)无需参数选取;2)能够发现社区内部结构;3)易实现并行化。
1 密度峰值聚类算法思想Rodriguez等人提出的密度峰值聚类算法[7]认为每一个聚类都有一个聚类中心。聚类中心的特点包括:1)核心节点本身密度大,即被密度不超过它的邻居包围;2)与其它密度更大的数据点之间的“距离”相对较大。
设数据集中总的数据点数为N,对于数据集中的每一个数据点i,用局部密度ρi和距离δi标记。
其中局部密度ρi定义为
$ {\rho _i} = \sum\limits_j {X\left( {{d_{ij}} - {d_c}} \right)} , $ | (1) |
式中:当时dij<dc时,X(dij-dc)=1;否则X(dij-dc)=0,dij是数据点i和数据点j之间的距离,dc是截断距离。数据点i的密度等于距该点距离小于dc的数据点个数。因此dc是否选取适当,对聚类结果影响很大。
设
$ {\delta _{qj}} = \left\{ \begin{array}{l} \mathop {\min }\limits_{qj,j < i} \left( {{d_{qiqj}}} \right),i \ge 2;\\ \mathop {\max }\limits_{j \ge 2} \left\{ {{\delta _{qj}}} \right\},i = 1; \end{array} \right. $ | (2) |
由公式(2)可知,数据点i的距离δi表示比其密度大的数据点距离的最小值。
对于数据集中的每一个数据点i,计算得(ρi, δi),以ρ为横轴,为δ纵轴画出该数据集的散点图,即决策图。选取同时具有较大的ρ值和δ值作为核心节点。对于剩余数据点,把其划分到距离其最近的核心节点所在的类簇中,完成整个数据集的聚类。
2 基于信息传递和峰值聚类的自适应社区发现算法研究提出了一种基于信息传递和峰值聚类的自适应社区发现算法(AID)。该算法包含4个部分:1)信息传递,2)距离矩阵计算,3)核心节点获取,4)社区划分。
2.1 信息传递社交网络可表示为图G=(V, E),其中V={v1, v2, …, vn}表示网络中节点集,E={e1, e2, …, em}表示网络中边集,n表示网络中节点的个数,m表示网络中边的条数。
定义网络信息量矩阵Sn×n,其中Sii表示节点i的初始信息量,Sij表示源节点i传递到节点j的信息量。
节点间信息传递遵循如下假设:
信息传递过程中,节点对于信任度不同的邻居节点所传信息量不同,信任度越大,所传递的信息量越大。
基于此定义了源节点i与邻居节点C(i, j)=|Ni∩Nj|的信任度,由公式(3)至公式(6)获得信任度函数。
$ C\left( {i,j} \right) = \left| {{N_i} \cap {N_j}} \right|, $ | (3) |
$ \alpha \left( {i,j} \right) = \frac{{\left| {C\left( {i,j} \right)} \right| + 1}}{{\left| {{N_i}} \right|}}, $ | (4) |
$ \beta \left( {i,j} \right) = \left\{ {\begin{array}{*{20}{c}} {\frac{{2 \times \left| {E\left( {C\left( {i,j} \right)} \right)} \right|}}{{\left( {\left| {C\left( {i,j} \right)} \right|} \right)\left( {\left| {C\left( {i,j} \right)} \right| - 1} \right)}},}\\ {0,} \end{array}} \right. $ | (5) |
$ T\left( {i,j} \right) = \alpha \left( {i,j} \right) \times \left( {\beta \left( {i,j} \right) + 1} \right), $ | (6) |
式中:|C(i, j)|表示节点i与节点j的公共邻居个数,Ni表示与节点i相邻的邻居节点,Nj表示与节点j相邻的邻居节点,|E(C(i, j))|表示节点i与节点j公共邻居间的连边总数。公式(4)中,分母为源节点的邻居个数,使得T(i, j)≠T(j, i),信息量的传递不对称,度数大的节点获得的信息量大。公式(5)表示2节点公共邻居间连边总数与其最大可能的连边总数的比值。由于β(i, j)是建立在α(i, j)的基础上,因此总的信任度定义为公式(6)。
信息传递步骤如下:
1) 初始化所有节点的信息量为1,即信息量矩阵Sn×n为单位矩阵。
2) 遍历网络中的节点,将每个节点依次作为源节点,对其初始信息量1进行扩散传递,此时并不考虑其余节点的信息量。
3) 源节点在扩散传递信息量时,采用广度优先算法。以i为源节点,其传递到邻居节点j的信息量Sij=1×T(i, j),邻居节点j要把源节点i传递的信息量Sij继续扩散到j的邻居节点k,k节点获得信息量Sik=Sij×T(j, k)=1×T(i, j)×T(j, k),直到网络中所有节点都含有节点i的信息量时,节点i的信息传递完成。
信息传递结束后,Sii=1表示节点i的原始信息量,Sij(j=1, 2, …, n; j≠i)表示源节点i传递到网络上其它节点的信息量。
本算法中,每一个节点需要局部密度ρ和距离δ标记。因此需要计算不同节点之间的距离,即距离矩阵。可通过信息量矩阵Sn×n获得距离矩阵Dn×n,具体步骤如下
1) 将Dn×n对角线元素置为0,即节点到自身的距离为0;
2) 令Dij=Sij(i≠j);
3) 依次求出Dn×n每行的最大值Mi(i=1, 2, …, n);
4)
距离矩阵Dn×n中,Dij表示节点i到节点j的距离。节点i的距离δi表示节点i到比它密度大的节点的最短距离,当节点i的密度最大时,令δi=max{δi(j=1, 2, …, n; j≠i)}。这样网络中的每一个节点都可以用密度ρ和距离δ去标记,即(ρ, δ)。
2.3 核心节点获取对于任意节点i,用(ρi, δi)进行标记,并定义了混合参数[7]γi=ρi×δi, i=1, 2, …, n。γi的值越大,越有可能是核心节点。
为了使得整个算法达到自适应的目的,提出一种自动选取核心节点方法:
首先把网络中的节点分为3类,即非核心节点集,核心节点集和未确定节点集。分类依据为:非核心节点集为δ=1的节点构成的集合;核心节点集为δ≥E(δi)+σ(δi), i=1, 2, …n的节点构成的集合,其中E(δi)和σ(δi)为节点距离δ的均值和方差;剩余节点构成的集合即为未确定节点集。
然后进一步确定未确定节点集中的节点是否属于核心节点,采用如下算法
1) 计算核心节点集中混合参数γ的最小值γminc和非核心节点集中混合参数γ的最大值γmaxnc和最小值γmaxnc;
2) 把未确定节点集中γ≤γmaxnc的节点划分到非核心节点集中,被划分的节点总数记为N;
3) 把未确定节点集中的γ≥γminc节点划分到核心节点集中;
4) 对于未确定节点集中剩余的节点,依据γ值的大小进行升序排序。按序遍历节点,如果公式(7)成立则该节点属于非核心节点集,并令γmaxnc=γi;如果公式(7)不成立,则计算终止,把本节点和剩余节点划分到核心节点集中。
$ {\gamma _i} \le \gamma _{\max }^{nc} + \frac{{\gamma _{\max }^{nc} - \gamma _{\max }^{nc}}}{N} \times \frac{{\lambda _{\min }^c - {\gamma _i}}}{{{\gamma _i} - \gamma _{\max }^{nc}}}。$ | (7) |
通过上述方法,确定了网络的核心节点,即核心节点集中的元素。
2.4 社区划分首先,为每一个核心节点分配唯一的且不同于其他核心节点的社区号。
对于非核心节点i,距离矩阵Dn×n中Dji表示节点j到节点i的距离,所有核心节点距节点i的距离可通过距离矩阵D确定。把节点i划分到与它距离最小的核心节点所在的社区内。依次遍历所有非核心节点,即可完成整个网络的社区发现。
完成社区发现后,可通过节点总的信息量,确定节点在社区内的重要程度,即社区内部结构。
2.5 时间复杂度分析本算法由4个步骤组成,第一步信息传递中,单个节点信息传递复杂度为O(n-1),因为网络中节点都要作为源节点进行信息扩散传递,因此总的复杂度为O(n2-n),其中n为网络的节点数;第二步中,获得距离矩阵每行最大值的时间复杂度为O(n2),对距离矩阵归一化处理的复杂度为O(n2),总的复杂度为O(2n2);第三步核心节点选取中只需对网络中的每个节点遍历即可,因此复杂度为O(n);第四步社区划分中,需依次遍历普通节点,其复杂度为O(n-nc),nc为核心节点的个数。综上,总的算法复杂度为O(n2)。由于各个节点的信息传递是相互独立的,因此本算法易实现并行化。
3 实验与分析在真实网络数据集和人工网络数据集上与经典社区发现算法LPA[4]、Infomap[5]、Fastgreedy[12]、Walktrap[6]和基于峰值聚类的VDDPC[8]、LCCD[10]社区算法进行比较,实验结果验证了本算法的可行性和有效性。
3.1 真实网络数据集表 1中列出了4个真实数据集都具有已知的社区结构,包括Karate数据集[13]、Dolphins数据集[14]、Football数据集[15]和Polbooks数据集。
Karate网络数据反映了某大学空手道俱乐部成员之间的关系,节点之间的连边表示成员之间的好友关系,由于校长与俱乐部主管的矛盾,该网络分裂成为2个社区。
Dolphins网络数据中每个节点代表了一只宽吻海豚,节点之间的连边表示2只海豚之间接触频繁。经过长期观察,该网络被分为2个社区。
Football网络数据集中每一个节点代表一支球队,节点之间的连边表示球队之间存在一场或多长比赛。由于球队属于不同的州,每个州内的比赛场次多,因此该网络被分为12个社区。
Polbooks网络数据集中每一个节点代表一本在亚马逊销售的政治类书籍,节点之间的连边表示2本书被同时购买的频率高。由于政治类书籍代表的政治立场不同,所以该网络被划分为3个社区,分别代表“自由”、“保守”和“中立”。
3.2 人工网络数据集Andrea Lancichinetti等人提出了著名的LFR[16]人工基准网络构造模型。该模型的优势在于可以通过参数控制整个网络和各个社区的规模、节点度分布等拓扑性质,使其更加符合真实社交网络的拓扑结构。
该模型中N为网络节点数,〈k〉为平均节点度数,kmax为最大节点度数,Cmin为网络最小社区所含的节点数,Cmax为网络最大社区所含的节点数,t1和t2分别为度分布和社区大小分布的幂指数,μ为模糊参数,表示网络社区的模糊程度,μ值越大,网络的社区结构越难发现,其取值范围为(0, 1)。为了验证本算法的有效性,生成3组网络,分别为LFR1(N=1 000),LFR2(N=5 000),LFR3(N=10 000), 网络其它参数设置如下:平均度数〈k〉=20,最大度数kmax=50,t1=2, t2=1, 社区大小([Cmin, Cmax])取值为[10, 50]。
3.3 评价指标模块度Q[17]被广泛的应用于社区划分结果的评价中。其定义如公式(8)所示。
$ Q = \frac{1}{{2m}}\sum\limits_{ij} {\left[ {{A_{ij}} - \frac{{{k_i}{k_j}}}{{2m}}} \right]} {\delta _{ci,cj}}, $ | (8) |
Q表示网络中社区内部节点之间的连边所占的比例和另一个随机网络中社区内部节点连边所占比例的期望相减得到的差值,其取值范围为0到1。数值越接近1表示社区划分的结果越好。
标准化互信息NMI(normalized mutual information)[18]是由Danon等人提出的一种衡量检测社区与真实社区接近度的指标,其定义如公式(9)所示
$ {\rm{NMI}}\left( {R|P} \right) = 1 - \left[ {H\left( {R|P} \right) + H\left( {P|R} \right)} \right]/2。$ | (9) |
NMI的取值范围为0到1,其值越高表明所划分的社区结构与已知的社区结构越接近。当其取值为1时,所划分的社区结构与已知社区结构相同。
3.4 实验结果与分析将本算法与Infomap、LPA、Fastgreed、Walktrap、VDDPC、LCCD等算法进行对比。VDDPC和LCCD算法需要确定截断距离,依照作者研究选取最优的参数。LPA为随机算法,表 2中的实验结果是独立运行50次的平均值。
图 1为本算法在4个真实网络上的决策图,表 2列出了不同算法在真实数据集上所划分社区的评价结果。
图 1所示决策图中,红色节点为核心节点,本算法利用节点总信息量代替节点密度,使得核心节点与非核心节点产生明显的区别,提高网络社区划分的准确性。
表 2所示,在Karate、Dolphins和Polbooks 3个真实网络数据集上,相较其它6个算法本算法所划分的社区结构具有最高的NMI值,即与网络已有的社区划分最接近。而在Football数据集上,本算法所划分社区的NMI值为0.895,只比Infomap算法低,并且2者相差不大,本算法所划分的社区结构依然有较高的水平。而本算法在Q值上,并未优于其它算法,这主要与Q与NMI的定义有关。模块度Q是从理论上定义社区,其仅仅考虑社区内外节点之间连边数量的比值。而NMI评估的是算法所划分社区与网络真实社区的相似度。以Karate网络为例,本算法所划分的社区与网络原有社区相同(NMI=1), 相应的Q值仅为0.371。对于已有社区结构的网络来说,越接近真实值,算法越有意义,NMI比Q具有更大的指导意义。因此与其它算法相比,本算法所划分的社区结构更加准确。
在真实网络数据集上,与前4种经典社区发现算法相比本算法不仅在准确度上优于上述4种算法,同时本算法还能发现社区内部结构。与后2种基于峰值聚类的社区发现算法相比,本算法无需确定截断距离等额外参数,同时NMI值也优于上述2种算法。
3.4.2 人工网络数据集结果分析图 2,图 3和图 4分别是7种算法在LFR1,LFR2,LFR人工数据集上的实验结果,其横轴为模糊参数μ,纵轴为NMI。
由3图可知,随着μ的增加,7种算法的NMI值都呈现下降趋势。图 2中,当μ<0.5时,除Fastgreed算法,其它算法都能准确的发现网络社区,这是因为Fastgreed算法是针对模块度优化的。当μ>0.5,各算法的NMI值出现明显下降,LPA与Infomap算法分别在μ≥0.6,μ>0.7时,NMI变为0,即整个网络被划分为一个社区。其它4种算法,在μ>0.7,仍能够发现社区,但明显本算法(AID)与Walktrap算法的NMI值要高于其它2种算法。在μ≥0.8时,本算法的NMI值大于其他6种算法。
对3图作横向对比,随着网络节点数增加时,各算法的NMI值的下降趋势减缓。在图 3,图 4中,当μ=0.7,本算法的NMI值低于Infomap和LPA算法,但是本算法的NMI随着μ的增加,下降缓慢,当μ=0.9时,NMI值是7种算法中最高。
综上,本算法在人工数据集上,能够稳定的发现网络的社区结构。当社区结构明显时,能够准确的发现网络社区;当社区结构模糊时,相对于其它算法,依然有较高的社区发现能力。
4 结论笔者提出一种基于信息传递与峰值聚类的自适应的社区发现算法。利用节点间基于信任度的信息传递确定峰值聚类中的节点密度和节点距离,其能够很好的区分核心节与非核心节点;然后通过核心节点完成社区划分。
本算法在整个社区划分过程中,无需额外参数,能够自适应的应用于各种网络中。同时,当节点作为源节点进行信息传递时,与其他节点的信息量无关,因此本算法易实现并行化。实验结果验证了本算法的可行性和有效性。
[1] |
Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826. DOI:10.1073/pnas.122653799 |
[2] |
Fortunato S. Community detection in graphs[J]. Physics Reports, 2009, 486(3-5): 75-174. |
[3] |
Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012, 8(8): 25-31. |
[4] |
Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 36-40. |
[5] |
Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118-1123. DOI:10.1073/pnas.0706851105 |
[6] |
Pons P, Latapy M. Computing communities in large networks using random walks[C]//Computer and Information Sciences-ISCIS 2005. Berlin: Springer Heidelberg, 2005: 284-293.
|
[7] |
Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI:10.1126/science.1242072 |
[8] |
黄岚, 李玉, 王贵参, 等. 基于点距离和密度峰值聚类的社区发现方法[J]. 吉林大学学报工学版, 2016, 46(6): 2042-2051. HUANG Lan, LI Yu, WANG Guishen, et al. Community detection method baased on vertex distance and clustering of density peaks[J]. Journal of Jilin University, 2016, 46(6): 2042-2051. (in Chinese) |
[9] |
Huang L, Wang G, et al. A link density clustering algorithm based on automatically selecting density peaks for overlapping community detection[J]. International Journal of Modern Physics B, 2016, 30(24): 1650167. DOI:10.1142/S0217979216501678 |
[10] |
Wang X, Liu G, Li J, et al. Locating structural centers:a density-based clustering method for community detection[J]. PLoS ONE, 2017, 12(1): e0169355. DOI:10.1371/journal.pone.0169355 |
[11] |
Chen Y. Finding communities by their centers[J]. Scientific Reports, 2016, 6: 24017. DOI:10.1038/srep24017 |
[12] |
Clauset A, Newman M E, Moore C. Finding community structure in very large networks[J]. Physical review E, 2004, 70(2): 066111. |
[13] |
Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1997, 33(4): 452-473. |
[14] |
Lusseau D. The emergent properties of a dolphin social network[J]. Proceedings Biological Sciences, 2003(270): S186-S188. |
[15] |
Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy Sciences of USA, 2002, 99(12): 7821-7826. DOI:10.1073/pnas.122653799 |
[16] |
Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 46-52. |
[17] |
Newman M E, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113. DOI:10.1103/PhysRevE.69.026113 |
[18] |
Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics, 2005, 2005(09): 9-18. |