第1期 骆志刚,等:复杂网络社团发现算法研究新进展 51
=
i
ln gi+
A
j
ij
ln g,j
i
通过简单变形后可直接运用EM算法进行求解。由于该算法未对社团结构作过多假设,具有较强的灵活性,能够发现不同结构类型的社团,如具有二分结构的社团,这是之前方法所不具备的。同时所求得的参数 ri中暗含了节点i到社团r的隶属程度,因此,通过该算法能够识别出重叠社团,并得到隶属程度大小。然而,该方法基于EM算法来估计未知参数,收敛速度较慢,计算复杂度较高,一定程度上制约了算法的应用规模。2 6 基于边聚类的重叠社团发现
以往社团发现算法的研究均以节点为对象,考虑如何通过划分、聚类、优化等技术将节点归为
[31]
重叠或不重叠的社团。最近,Evans等和Ahn等
[32]
(1)建立统一的度量标准。由于复杂网络的类型众多,连接规律各有不同,很难以社团结构的某种统一的模块度(如Q值)来刻画社团发现算法的优劣。一种更为科学的方式是建立一套包含多种复杂网络的统一标准测试集,以评判算法在不同类型网络中的优劣,明确算法的适用范围。
(2)适用于大规模复杂网络的社团发现算法。复杂网络的规模越来越大,对算法的计算复杂度提出了更高要求。虽然在不考虑重叠社团的情况下,已出现一些接近于线性时间复杂度的算法,但这些算法通常采用较为激进的贪婪策略,网络规模变大且非稀疏时,其结果变得不可靠。在重叠社团发现算法中,很多算法需要通过多次计算来获得最佳的社团数,计算开销过大。因此,考虑复杂网络社团密度不均的特点,从局部社团出发研究网络的社团结构是未来的重要研究方向之一。此外,设计适合于大规模网络分析的高效并行算法也是未来重要的研究方向之一。
(3)重叠社团与层次社团的结合。一般认为,社团之间共享部分边缘节点从而产生重叠社团,然而重叠社团结构远比想象的要复杂。实际上,除了重叠性,层次性也是社团结构的另一大特性。例如,第i层中的中心节点,可能在第j层中就变成了边缘节点。可见,重叠性与层次性两者联系十分紧密,有必要将两者融和在一起来解构复杂网络。在目前的众多方法中,唯有边社团给出了社团重叠性和层次性普遍并存的合理解释,未来以边为对象来研究网络社团结构将是一个值得深入研究的方向。
分别发表了以边为研究对象来划分社团。
虽然节点属于多重社团,但边通常只对应某一特定类型的交互(真实网络中的某种性质或功能)。因此,以边为对象使得划分的结果更能真实地反映节点在复杂网络中的角色或功能。文献[31-32]虽然都是对边进行聚类来提示重叠社团,但在处理方式上有所不同。
文献[31]将原网络转换为加权线图,即原网络中的边映射为线图中的节点,线图中的节点存在边当且仅当原网络中所对应的边存在共享节点,而边权值等于1 (k-1),其中k为共享节点的度。通过网络的转换,最大的好处是可以直接应用非重叠社团发现算法来提示网络的重叠社团。
文献[32]则着重解决社团的重叠性与层次性之间的冲突,提出边社团的概念,即将社团看作是紧密相连的边集合。作者在定义边间相似度的基础上,采用层次聚类建立聚类树状图。由于每个节点拥有一条到多条边,每条边存在于一个边社团中,因此对该树状图不同层次的切割得到的社团结构对应着不同层次的重叠社团。
参考文献:
[1] GirvanM,NewmanMEJ.CommunityStructureinSocialand
BiologicalNetworks[J].PNatlAcadSciUSA,2002,99(12):7821-7826.
[2] 解亻刍,汪小帆.复杂网络中的社团结构分析算法研究综述
[J].复杂系统与复杂性科学,2005,2(3):12.
[3] 李晓佳,张鹏,狄增如,等.复杂网络中的社团结构[J].复
杂系统与复杂性科学,2008,5(3):24.
[4] NewmanMEJ.FastAlgorithmforDetectingCommunityStructure
inNetworks[J].PhysRevE,2004,69(6):066133.
[5] ClausetA.FindingLocalCommunityStructureinNetworks[J].
PhysRevE,2005,72(2):026132.
[6] SchuetzP,CaflischA.MultistepGreedyAlgorithmIdentifiesCommunity
StructureinRea-lworldandComputer-generatedNetworks[J].PhysRevE,2008,78(2):026112.
[7] NewmanMEJ.ModularityandCommunityStructureinNetworks
[J].ProcNatlAcadSciUSA,2006,103(23):8577-8582.[8] DuchJ,ArenasA.CommunityDetectioninComplexNetworks
[RevE,:
3 总结与展望
从异常复杂的网络解构出其中的社团结构,已成为当今复杂系统研究领域一项具有挑战性的
研究课题。虽然该课题近些年受到广泛关注,涌现出一批新颖的算法,但目前相关研究仍未形成统一的框架和度量标准,尤其是重叠社团发现算法的研究,尚存许多问题丞待解决。我们认为,复杂网络社团发现的进一步研究可从以下几个方面
些堡盟塑咝坐坠翌堕匹堡旦墅婴墅望型盟垡塑复杂网络社团发现算法研究新进展‘骆志刚,丁凡,蒋晓舟,石金龙 国防科技大学学报 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....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...
热门文档