第1期 骆志刚,等:复杂网络社团发现算法研究新进展 49
最大等价于求条件信息H(X|Y)最小,Rosvall等给出了条件信息的量化表示并运用模拟退火优化算法进行求解,可实现上千个节点的网络社团发现。测试表明,对于社团大小及边密度不一的社团发现问题,该发现算法要明显优于基于模块度优化的社团发现算法。后来,Rosvall等进一步以描述图中信息的扩散过程为目标
[16]
点严格地划分到某个社团中,而真实世界中这种硬划分并不能真正反应节点和社团的实际关系,例如蛋白质相互作用网络中由于蛋白质功能的多样性,单个蛋白质在不同的时空条件下参与不同的功能模块中。同样的现象普遍存在于各种真实网络之中,如社会网络中的人属于多个集体、网络中的网页属于多个主题等。因此,重叠社团发现更符合真实世界的社团组织规律,成为近几年社团发现研究的新热点,涌现出许多新颖算法。2 1 基于团渗透改进的重叠社团发现算法
由Palla等
[20]
,将问题转换
为寻找描述网络上随机游走的有效编码方式,使该方法更适合于捕捉社团内部节点之间的长程相关性,已有文献测试表明该方法是目前非重叠社团发现算法里准确度最高的一类方法
[17]

。
提出的团渗透算法是首个能够
发现重叠社团的算法,文献[2]中已对其进行详细介绍。该类算法认为社团是由一系列相互可达的
图1 从信息论的角度看社团发现[11]Fig.1 Communitydetectionfromtheviewof
informationtheory[11]
k-团(即大小为k的完全子图)组成的,即k-社团。算法通过合并相邻的k-团来实现社团发现,而那些处于多个k-社团中的节点即是社团的 重叠 部分。
Kumpula等在前人工作基础上进一步提出一种快速团渗透算法(SCP算法)
[21]
1 4 基于标号传播的社团发现算法
很多情况下,复杂网络的边表示的是个体之间的信息传播,其传播的结果通常是使得社团内部节点之间共享相同的信息。Raghavan等
[18]
。该算法分两阶
基
段进行,第一阶段将网络的边按顺序(如加权网络按权值大小顺序)插入到网络中,并同时检测出现的k-团;第二阶段将检测的k-团,根据是否与已有k-社团相邻,并入k-社团或形成新的k-社团。由于边插入的顺序性,在第二阶段检测时SCP算法只需依次对k-团进行局部判断;而且SCP算法能够在一遍运行中检测不同权重阈值下的k-社团,较大地提高了团渗透算法的计算速度。
基于团渗透思想的算法需要以团为基本单元来发现重叠,这对于很多真实网络尤其是稀疏网络而言,限制条件过于严格,只能发现少量的重叠社团
[22]
于该思想提出一种快速的标号传播算法(简称为LPA算法)。如图2所示,LPA算法首先为每个节点指派唯一标号,在每一步迭代中,每个节点将自身标号更新为其邻节点出现次数最多的标号,如果存在多个相同的最多标号,则随机选择一个作为更新值,若干次迭代后密集相连的节点会收敛于同一标号,最终,具有相同标号的节点归为一个

社团。
图2 标号传播过程示意
Fig.2 Theprocessoflabelpropagation[18]
[18]
。
2 2 基于模糊聚类的重叠社团发现算法
另一观点认为可将重叠社团发现归于传统模糊聚类问题加以解决,以计算节点到社团的模糊隶属度来揭示节点的社团关系。这类算法通常从构建节点距离出发,再结合传统模糊聚类求解隶属度矩阵。
张世华等首先应用这一思想
[23]
LPA算法最大的优点在于不需要任何参数输入,比如社团的数目、大小等,而且算法具有线性的时间复杂度为O(m),m为网络的边数,收敛速度非常快,可适用于规模较大的复杂网络。随后,Leung等对标号更新规则进行了改进
[19]
。在LPA
迭代过程中引入衷减因子,每次迭代由衷减因子、边权重、偏好特征决定更新的标号,同时增加标号更新的选择性,比如共享最大标号的邻居少于某个比例时才进行更新,降低了计算开销。
,他们结合谱
分析方法将网络中的节点近似映射到欧拉空间中的数据点,进而利用FCM算法对空间中的数据点进行聚类,从而得到节点与社团之间的隶属度矩
阵。由于模糊聚类算法FCM本身要求预先知道社团数,该算法在模块度Q值的基础上引入新的Q 2 重叠社团发现算法
些堡盟塑咝坐坠翌堕匹堡旦墅婴墅望型盟垡塑复杂网络社团发现算法研究新进展‘骆志刚,丁凡,蒋晓舟,石金龙 国防科技大学学报 v01.33No.1 &坠:垫!! 文章...
2011 文章编号: 1001- 2486( 2011) 01- 0047- 06 复杂网络社团发现算法研究新进展骆志刚, 丁凡, 蒋晓舟, 石金龙 410073) ( 国 防科技大学 计算机学院, ...
( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...
( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...
张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...
张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...
热门文档