文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 复杂网络社团发现算法研究新进展_骆志刚
侵权投诉

复杂网络社团发现算法研究新进展_骆志刚

48 国防科技大学学报 2011年

型代表算法有Newman快速算法、CNM算法

[6]

和MSG-MV算法等。Newman快速算法将每个节点看作是一个社团,每次迭代选择产生最大Q值的两个社团合并,直至整个网络融合成一个社团。整个过程可表示成一个树状图,从中选择Q值最大的层次划分得到最终的社团结构。该算法的总体时间复杂度为O(m(m+n))。在Newman快速算法的基础上,CNM算法采用堆数据结构来计算和更新网络的模块度,大大提高了计算速度;MSG-MV算法则引入多步扩展,迭代过程中每次可合并多对社团以避免过早地收缩到少数较大的社团。

第二类算法主要采用分裂的思想,自顶向下进行。例如,Newman最早提出的GN算法就属于这类算法,算法通过依次删去网络中边介数(即网络中经过每条边的最短路径数)最大的边,直至每个节点单独退化为社团,然后从整个删边过程中选取对应最大Q值时的结果。该算法复杂度较高,为O(n)。随后,Newman等人通过定义模块度矩阵,将模块度用矩阵的特征向量表示,提出一种用于划分网络社团结构的谱方法。该算法通过求解模块度矩阵的最大正特征值以及对应的特征向量,依据特征向量中元素的符号将网络不断递归二分,直至子网络再细分已不能增大Q值。整个算法的平均时间复杂度为,较GN算法在计算速度和准确度上均有较大提高。

第三类算法则是直接寻优法,如Duch等提出的EO算法

[9]

[8]

[7]

3

[1]

[4][5]

团内外连接度的差异时,引入了社团大小作为分母进行平均,从理论和数值试验上证明了作为模块度D值要优于Q值。

总的来说,模块度优化算法是目前应用最为广泛的一类算法,但是在具体分析中,很难确定一种合理的优化目标,使得分析结果难以反应真实的社团结构,尤其是分析大规模复杂网络时,搜索空间非常大,使得许多模块度近似优化算法的结果变得更不可靠。

1 2 基于谱分析的社团发现算法

谱分析法建立在谱图理论基础上,其主要思想是根据特定图矩阵的特征向量导出对象的特征,利用导出特征来推断对象之间的结构关系。通常选用的特定图矩阵有拉普拉斯矩阵和随机矩阵两类。图的拉普拉斯矩阵定义为L=D-W,其中D为以每个节点的度为对角元的对角矩阵,W为图的邻接矩阵;随机矩阵则是根据邻接矩阵导出的概率转移矩阵P=D

-1

W。这两类矩阵有

一个共同性质,同一社团节点对应的特征分量近似相等,这成为目前谱分析方法实现社团发现的理论基础。

基于谱分析的社团发现算法普遍做法是将节点对应的矩阵特征分量看作空间坐标,将网络节点映射到多维特征向量空间中,运用传统的聚类方法将节点聚成社团。例如,Donetti等

[14]

基于节

点之间的距离度量,在不同维度的特征空间中建立聚类树图,从中选择全局模块度最大的划分作为社团发现结果。Capocci等

[15]

以及Agarwal等提出的整数规划方

法。EO算法的思想是将每个节点对模块度Q值的贡献大小定义为局部变量,然后在随机初始划分的基础上,通过贪婪策略调整局部变量(具有最小贡献度的变量)来提高全局目标函数Q值。整数规划方法则通过求解对应的松弛线性规划问题能够给出最大模块度的一个上界,这是以前方法所不具备的。此外,还有一些基于遗传算法、蚁群算法等智能算法的社团发现算法也可归为此类。

近年来越来越多的研究发现:模块度优化方法无法发现小于一定粒度的社团

[10-11]

则基于同一社团

的节点对应的随机矩阵特征分量强相关这一性质

提出计算特征向量的Pearson相关系数来度量节点之间的相似度。

应用谱分析法不可避免地要计算矩阵特征值,计算开销大,但由于能够通过特征谱将节点映射至欧拉空间,并能够直接应用传统向量聚类的众多研究成果,灵活性较大。1 3 基于信息论的社团发现算法

从信息论的角度出发,Rosvall等

[11]

把网络的

。在实际

模块化描述看作对网络拓扑结构的一种有损压缩,从而将社团发现问题转换为信息论中的一个基础问题:寻找拓扑结构的有效压缩方式。如图1所示,原拓扑结构X通过编码器产生模块描述Y,解码器对Y进行解码,推测出原结构Z,那么何种模块描述Y是最优的?以信息论的观点来看,互信息I(X,Y)最大时,即最能反应原始结构,网络中,尤其是大规模网络中,社团的大小不一,该问题尤为突出。为此,研究者们提出一些局部

[12]

调整策略。如Ruan等结合谱平分法和局部搜索方法提出的HQcut算法,在分裂网络前增加统计测试来判断是否需进一步细分。此外,部分研究者提出新的模块度来避免Q值存在的粒度问[13]

上一页第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....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email