欢迎访问一起赢论文辅导网
MBA论文
当前位置:首页 > MBA论文
社团结构迭代快速探测算法
来源:一起赢论文网     日期:2017-02-19     浏览数:4393     【 字体:

 39卷  计  算  机  学  报  Vol. 39    2016年  论文在线出版号  No.160  CHINESE J OF COMPUTERS  Online Publishing No.160 ——————————————— 本课题得到国家自然科学青年项目(No.7140119471401188);国家自然科学重点项目(No. 9132420311131009);中央财经大学“青年英才”培育支持项目(No. QYP1603)资助.  李慧嘉,男,1985年生,博士,讲师,主要研究领域为数据挖掘、复杂网络、信息检索,E-mail: Hjli@amss.ac.cn.  李爱华,女,1978年生,博士,副教授,主要研究方向为数据挖掘、管理决策,E-mail: neu_aihua@126.com.  李慧颖,女,1983年生,博士,助理研究员,主要研究领域为生物信息学、复杂网络、数据挖掘,E-mail: lihuiying08@mails.tsinghua.edu.cn.    社团结构迭代快速探测算法     李慧嘉1),    李爱华1),    李慧颖2) 1) (中央财经大学  管理科学与工程学院,  北京,100081) 2) (清华大学  自动化系,  北京,100084)  摘  要  作为复杂网络研究的重要组成部分,社团结构分析对于理解和分析现实世界中各种社会、工程和生物等系统具有非常重要的意义。本文利用动态迭代技术,提出了一种新型的社团探测技术,能够准确而快速地识别网络中的社团结构。首先引入一种动态系统,可以使社团归属从随机状态逐步收敛到最优划分,进一步利用严格的数学分析给出了社团归属在离散时间内收敛到最优的条件。本文创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数。为了使动态系统不需要任何参数选择即可完成向最优社团的收敛,我们设计了一种新颖的图生成模型,使得算法能在无参数的情况下方便高效的运行。本算法具有较高的效率,计算复杂性分析显示算法需要的时间与稀疏网络节点的数量呈线性关系。最后,我们将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够高效地应用于大规模现实网络的分析和计算中。 关键词  社团结构;动态系统;指标函数;线性复杂度;层次结构 中图法分类号  TP393                                                                                   论文引用格式: 李慧嘉,李爱华,李慧颖,社团结构迭代快速探测算法,2016Vol.39,在线出版号  No.160 Li Hui-JiaLi AihuaLi Hui-YingFast community detection algorithm via dynamical iteration2016Vol.39,Online Publishing No.160  Fast community detection algorithm via dynamical iteration Li Hui-Jia1),    Li Aihua1),    Li Hui-Ying2)   1)( School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, China)  2)( Department of Automation, Tsinghua University, Beijing 100084, China)  Abstract A feature, observable in many networks, is the presence of community structures, i.e. clusters of vertices which are densely connected to each other while less connected to the vertices outside. The community structure identification is  an  important  problem  in  a  wide  range  of  applications such  as  marketing  in  social  networks  and study of protein interaction networks. Usually, the community members have more properties in common among themselves than with nonmembers and detecting community structure helps analyzing and searching the network with  less  effort.  However,  most  existing  approaches  fall  into  the  categories  of  either  optimization  based  or heuristic methods which do not meet both speed and accuracy requirements simultaneously. In this paper, a new fast and accurate community detection algorithm is proposed based on dynamic system in complex networks. First, 网络出版时间:2016-10-29 01:09:36网络出版地址:http://www.cnki.net/kcms/detail/11.1826.TP.20161029.0109.002.html2  计  算  机  学  报  2016a  discrete-time  dynamic system is  introduced to  describe  the assignment  of  community memberships,  and the conditions  driving  the  convergence  of  dynamics  trajectory  to  the  optimal  situation  are  formulated.  A  new algorithm is proposed which can be generalized to unify the conventional algorithms widely applied. Furthermore, a new  type  graph  generative  model  is  designed  which performs  the  algorithm  free  of  the  parameters. Our algorithm  is  highly  efficient:  the  computational  complexity  analysis  shows  that  the  required  time  is  linearly dependent on the number of all nodes in a sparse network. We perform extensive simulations with synthetic and also real-world benchmark networks to verify the algorithmic performance. The results showed that the proposed method does not face the resolution limit problem and performs very well. Key words  community structure; dynamic system; quality function; linear time; hierarchical structure  1  引言 随着信息技术的发展,很多现实世界系统可以用复杂网络(complex  network)来模拟[1]-[4],例如InternetWWW网络,交通运输网,电力传输网,科学家合作网,微博关联网,蛋白质交互网和基因关联网络等[5]-[11]。伴随着新型数据处理技术特别是大数据技术的产生和发展,复杂网络特性分析获得了越来越多的关注。社团结构作为复杂网络的一个重要特征,它将网络划分成具有紧密内在联系的子群[12]-[14],而同一子群中的节点通常有共同的属性和关联。准确而快速地发现社团结构能够有效地优化网络系统的预测、控制和演化,例如设计网络推荐系统进行精确地营销[4][15][16],药物靶点和基因关联点的定位[12][17][18],网络社交媒体发展趋势的预测等[13][15][19][20]。 目前虽然已有不少经典的探测方法,但是许多基本的社团相关问题仍然没有非常清晰的解释。例如,社会或生物系统中社团结构的深层次意义是什么?为什么社团结构在网络中会自然地呈现出层次结构[21]-[24]?虽然经典优化方法和启发式算法被广泛应用到社团探测中,但它们的基本思想是比较社团内外的直观属性和拓扑特性[25]-[28]。为了达到一定的准确性,这些方法需要很高的计算复杂度,而且结果会出现一些不可避免的缺陷,如分辨率限制[11]和错误识别[13]等。因此设计一个准确而高效的社团探测算法并进一步刻画拓扑结构隐藏特征(比如动态迭代[29]-[34])非常具有挑战性。 为了能快速而准确地发现最优的社团结构,本文设计出一种新颖的动态系统(如图1所示),可将社团归属从随机状态逐步迭代收敛到使指标函数最大的全局最优划分。利用严格的数学推导,我们进一步给出社团归属收敛到最优的条件。总体来    说,本文创新点主要有三方面: (1)根据严格的数学推导,我们证明了通过迭代动态系统,可以最优化特定指标函数以获取理想的社团分区,即动态迭代过程的固定的稳定值。特定条件下,最优社团划分可以通过迭代动态系统收敛得出。 (2)本文提出一种新颖的一般化目标函数,能够将著名的指标函数整合为统一的形式,这样我们可以通过选择不同的参数,来找到合适的指标函数。 (3)我们进一步设计了一种新颖的图生成模型(graph generative model),使得动态系统不需要任何参数选择即可完成向最优社团的收敛,方便高效。    利用动态系统,我们提出了一个新型的动态社团探测算法,在稀疏网络上其时间复杂度和节点数目线性相关。进一步,为了确定社团的最优数目,本文利用Markov状态转移矩阵及其特征系统给出了具体而严格的证明。最后,实验结果表明,本算法不仅具有较高的准确性,还能够方便地应用到大规模网络的计算和分析中。  图1  根据迭代机制,为了得到最优社团划分X(t),  我们提出一种高效的动态迭代系统( ) ( ) ( ) 1 X t f X t +=,  最大化方程H并论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  3 得到X(t)收敛的最优结果。其中,指标函数H用来衡量t时刻的社团归属X(t)的优劣,网络中不同的社团用不同的扇区表示,可以很容易看出通过迭代收敛,最右端的划分是最优的。 2  相关研究   近年来社团探测技术成为网络分析的热点并涌现出多种探测算法。一般地,每种方法由两部分组成:评估社团划分的质量函数和相应的划分算法。在众多质量函数中,模块度函数Q是最广为人知的。假设AG的邻接矩阵,is是节点i 的社团标志,当ij ss=时有( ) 1 ,j id s s=,否则( ) ,0 ij d s s =。如公式(1)所示,模块度函数Q的增加代表了社团划分的优化。因此,社团探测问题可以转化成为模块度函数Q的最大化问题。 { } ( ) ( ) ( )1,.2ij ij i jijQ A pms d s s¹= - - å    (1) Potts模型是另一种应用广泛的社团探测技术,它通过将社团的标号用自旋状态(spin  states)来表示,进而利用系统的自旋能量函数[35][36]来评估社团划分的质量。Reichardt & Bornholdt(RB)[15]提出了一个泛汉密尔顿函数来刻画能量函数, { } ( ) ( ) ( )1,,2RB ij RB ij i jijH A p s g d s s¹= - - å   (2) 其中RBg为汉密尔顿函数的分辨率参数,,RB ijp g Î。RB模型可以拓展到两个典型的子模型: (1RBER模型:所有的边都具有相同的连接概率,其能量函数如下: { } ( ) ( ) ( )1,.2RBER ij RB i jijH A p s g d s s¹= - - å    (3) 2RBCM模型:边的连接概率与网络的度分布相关,其能量函数如下: { } ( ) ( )1,,22ijRBCM ij RB i jijkkHAms g d s s¹æö = - -ç÷ èø å  (4) 其中ik是节点i 的度。值得注意的是,当1RBg =时,RBCM模型的能量函数等同于模块度函数Q。 另外,HofmanWiggins[16]提出了一个一般化的概率模型并定义了相关的能量函数: { } ( ) ( ) ( )( )111,21                     , ,2HW L ij G i jijKniiH W A Whmms d s sd s m¹=== - -+ååå    (5) 其中1log1outGinpWp-=-,logoutLGinpWWp=+,inp代表两个节点属于相同社团的概率,outp代表两个节点属于不同社团的概率,该能量函数通过贝叶斯方法进行最优化处理。 进一步,RonhovdeNussinov提出的一种无分辨率限制的模型[17],其质量函数如下: { } ( ) ( ) ( )1,,2RN ij ij ij ij i jijH W A W A s g d s s¹= - - å   (6) 其中当ij¹时,1ij ijAA=-,否则0ijA =。此外,ijWWéù =ëû是一个一般化的加权矩阵,为存在和缺失的边进行赋权。 算法方面,Newman-Fast(NF)算法[18]是一种基于模块度优化的迭代算法,它采用贪婪方法逐步更新社团归属,使得模块度的增量最大。Blondel等人提出了Louvain算法[10],它初始时分配给每个节点不同的社团标号,使得每个节点都是一个独立社团,然后逐步迭代社团归属直至模块度函数无法再提高。OCR方法[37]是一种基于同步动态系统的社团探测方法,它得益于动态网络中紧密连接的顶点具有较大的局部同步性能。标签传播方法是一种接近线性时间的社团探测方法[19],算法以分配给每个节点不同的社团标号为起点,然后根据最近邻节点的标号来更新自己的社团标号[36]-[42]直至稳定状态。有趣的是,标签传播等同于局部能量最小值的零温度Potts模型[22]: { } ( ) ( ) ,. KPM ij i jijHAs d s s¹=-å    (7) 另外常见的社团探测方法还包括模拟退火算法(SA[20]、外部优化算法[21][25][26]、最大化期望值算法[24][28]、贝叶斯推理方法[22][27]、变分4  计  算  机  学  报  2016年 贝叶斯方法等[16]和演化迭代方法[36][43][44]等。 3  问题标准化 3.1 概念 我们首先给出一些基本定义,一些主要的参数在表1中进行了说明: (1c, n, m分别表示网络中社团、点和边的数目。 (2inlm和outlm分别表示社团m的团内边和团间边数量。 (3inpm表示社团m团内边的比例,outpm表示社团m团间边的比例。 易得 ( ) ( )2,. 1in outin outll ppn n n n nmm mmm m m m==--    (8)  1   主要参数说明 符号  说明 c  社团数量 n  节点数量 m  边数量 inlm  社团m团内边数量        outlm  社团m团间边数量 nm  社团m内节点数量 inpm  社团m团内边的比例      outpm 社团m团间边的比例 ixm  节点i属于社团m的概率 ikm  节点i与社团m的节点-社团程度 iQm  节点i基于社团m的质量函数  一个节点可以以不同的概率分属不同的社团。考虑一个由n个节点,m条边,c个社团构成的网络G,本文引入向量( ) ( )ii X t x tméù =ëû,1, 2,...,c m=,其中()ixtm表示在时刻t ,节点i 属于社团m的概率。易得: ( )( )1011,   i   .icixtx t Vmmm=££= " Î å              (9) 集合( ) ( )iX t x tméù =ëû, { } 1, 2,..., in=为在时刻t时网络社团归属的集合。 定义  1 (硬划分)硬划分中的每个点i t 时刻仅属于特定社团c,它的充要条件是向量( )iXt的第c个元素为1,其余值都等于0。在硬划分中,不存在重叠节点(overlapping nodes)。 定义  2 (节点-社团度)我们将节点i 在社团m中的节点-社团度表示为ikm,其定义为节点i 连接到社团m的边数。其数学化表示为: . ii k x Am am aa=å                  (10) 利用社团归属( ) Xt,在硬划分的条件下,一些常用的概念nm,inlm,outlm,inpm,outpm可以重新表示为 ( ) ( ),iin t x tmm=å                 (11) ( ) ( )1,2ini j iji j il x t x t Am m m¹= åå        (12) ( ) ( ) ( ) 1, outi j iji j il x t x t Am m m¹=-åå       (13) ( ) ( )( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( )( ) ( )22,i j iji j i inij i j ii j iji j iii ii j iji j iiix t x t Apx t x tx t x t Ax t n t x tx t x t An t x tmmmmmmmm m mmmmm¹¹¹¹==-=-åååååååååå             (14) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )22111(1 )       .1i j iji j ioutij i j ii j iji j ii i ji j i i j ii j iji j iiix t x t Apx t x tx t x t Ax t x t x tx t x t An n n t x tmm mmmmmm m mmmm m m¹¹¹¹¹¹-=--=--=- - -ååååååå å å åååå (15) 3.2 基于迭代的新型动态系统 相比与大多数经典算法,如层次分析法和启发式算法,利用动态系统更新归属向量(即论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  5 ( ) ( )iX t x tméù =ëû)到一个理想的固定值是非常简单的,其计算复杂度非常小,便于在大规模网络上进行计算和分析。虽然有一些其他的动态系统,如随机游走和协同系统,也能够将归属矩阵收敛到一个稳定的状态,但是它们仅仅是对归属矩阵进行迭代而无法保证收敛到最优值(最优化特定的指标函数Q)。为了快速而准确地探测社团结构,我们提出一种新型的动态迭代算法。这里,首先给出离散时间下的动态系统:   ( )( )( ) ( )( )( ) ( )1,iiQ x tiiQ x tix t extx t emmmmmmmm**+=å     (16) 其中( ) ( 1 ) :ni Q x t R Rmm* +®是节点i 归属于社团m的质量函数,() xtm *是一个n 维向量,第i 维是()ixtm,函数Q满足下列约束条件 0.iiQxmm¶=¶                    (17) 由此,我们推断出了几条关于动态系统的重要性质。 性质1 离散的动态系统有两类平凡(trivial)稳定点,分别为: (1)硬社团结构的社团归属,即( ) 1ixtm=和( ) 0ixtm=,mm "¹;   (2)均匀的社团归属,即1( ) ,ixtcm= { } 1, 2,3,..., , in= { } 1, 2,...,c m=。 证明:当( ) 1ixtm=和( ) 0ixtm=时,mm "¹,得到 ( )( )( ) ( )( )( ) ( )( )( )**(* )(* )( ( ))( ( )) ()1()               1.( ) 0iiii iQ x tiiQ x tiQ x tiQ x t Q x tix t extx t ex t ex t e emmmmmmm mmmmmmmmmmm*¹+===+´åå  (18) 同理,对于所有的i 1()ixtcm=,这意味着1( 1)ixtcm+=对于所有的i 成立。证毕。     为了表述方便,此后用()iQtm代替( ) () iQ x tmm*。 定理1 考虑一个一般化离散(连续)时间的动态系统,x*为相应的动态系统曲线的稳定值[24]。 (1)当且仅当Jacobian矩阵()Fxx*¶¶所有的特征值il满足1(Re( 0))ii ll<<时,x*是渐进稳定的。 (2)当Jacobian矩阵()Fxx*¶¶只要有一个特征值il满足1(Re( 0))ii ll>>时,x*是不稳定的。 定理2对于任意的硬社团归属() Xt,记im*为归属值( ) 1iixtm* =时的社团。那么当 ( ) ( ) **μ, ,,iii ii Q t Q tmmm " ¹ <      (19) 动态系统(16)() Xt有一渐进的稳定点。如果对于某节点对im,( ) ( ) **μ, ,iii ii Q t Q tmmm " ¹ >,则此稳定点不固定。 证明.  为了确定动态系统在() Xt处的Jacobian矩阵,系统(16)nK´个状态变量和相应的导数计算如下: ( )( )( )( )( )( )( )( )( )( )( )( )( ) ( )( )( )( )210111,0   ,1iiiiiiiiQ t Q tiiQtiiiixtQtiQtxt ixte x t extxtx t extxtxt ext emmmmmmmmmm m mmmmmmmm¹===¶+=¶¶+¶¶+=¶=åå  (20) 6  计  算  机  学  报  2016年 ( )( )( )( ) ( )( )( )( )( )( )( )( )( )( )( )( )21011,10,iiiiiiiQ t Q tiiQtiiQtiQtixtiixtx t x t e ext x t ext ext extxtmmmmmmmmmmmmmmmm¢¢¢¢=¢=¶+=-¶¶+=-¶¶+=¶å        (21) ( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )2101,10,10,iiiiiQ t Q t iiijiQtjiijxtijxtQtx t e x t ext xtijxt x t extxtxtxtmmmmmmmmm mmmmmmmm¹==æö¶ç÷¶ ¶+ èø =¹ ¶¶+=¶¶+=¶åå(22) ( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )2101,10,10.iiiiiQ t Q t iiijiQtjiijxtijxtQtx t e x t ext xtijxt x t extxtxtxtmmmmmmmmm mmmmmmmm¢¢¢¢¢=¢=æö¶ç÷¶ ¶+ èø =¹ ¶¶+=¶¶+=¶å(23) 对所有的m和m,假设iJ为一个包含( )( )1iixtxtmm¶+¶的KK´的矩阵块。接着,在方程(20)-(23)中运用合适的排列和替换,iiJ() Xt的值为: ( )( )( )( )( )( )( )( )( )1**2**000 00i ikiiiiiikiiQ t Q tQ t Q tQtQtiiQtQtXteeeeeJeeemmmméù êú êú êú êú êú êú êú êú êú êú ë--=û  (24) 基于硬划分下的稳定点,整个Jacobian矩阵可以由以下矩阵表示 ( )11000 0  00iinnXtJJJJéù êú =êú êú ëû     (25) 很显然,基于硬划分下稳定点的Jacobian矩阵的特征值为[45]: ( )( )***  0, , 1, 2, , , .iiiiQtiiQt ieinemmm ml l m m = = = ¼ ¹  (26) 基于定理1,动态系统在() Xt有一个渐进式的稳定点,即如果 , ,| | 1.iimml "<                           (27) 已经对所有*iiml都满足,而且剩余也满足的话需要满足下面条件: ( )( )**, | | 1iiiQtii Qteiemmmm m l " ¹ = < , ,     (28) 即  ( )( ) ( )**() *,.i iiiQt Qtiiii e e Q t Q tm mm mmm " ¹ < Þ < , (29) 另一方面,如果某个点i 和社团*,im m m ¹,我们可以得到( ) ( ) *iiiQ t Q tmm>,那么这个稳定点不固定。证毕。 定理2直观地说明了函数值( )iQtm是“节点i属于社团im*”的质量指标。因此,如果硬社团归属的稳定值是固定的,那么所有节点的相关质量函数都应该是最大的,这可以通过迭代动态系统(16)来实现。相应地,社团探测问题可以简化为设计合适的论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  7 Q函数,用来衡量单个点在所有社团的归属程度。 到目前为止,我们介绍一种基于迭代的动态系统以及分析了其收敛的具体条件。接下来,我们为算法设计一种具有代表性的一般化社团探测指标。考虑下列方程H ( ) ( ) ( ) ( )11  .2niiiH X t x t Q tmmm == åå     (30) 我们下面证明方程H 的全局最优值(global maximum)是动态系统(16)的固定的稳定值。 定理3 如果记() Xt为社团归属向量,那么最大化方程H得到的社团归属向量() Xt的全局最优值是动态系统(16)的固定的稳定值。 证明.  如果() Xt为最大化方程H得到的社团归属向量的全局最优值,利用反证法,假定() Xt是动态系统的不固定的稳定值,那么会有 ( ) ( ) *,, ,iiii Q t Q tm mmm $ $ ¹ >  (31) 其中im*是社团标号,会使得( ) 1iixtm* =。如果( ) 1iixtm* =和( ) 0ixtm=的值互换,那么会有( ) 0iixtm* =和( ) 1ixtm=,则方程H的值的相应变化如下 ( ) ( )( )( ) ( )( )( ) ( )***0, 1 1, 0||0,ii iiixx t x t xiiH X t H X tt Q t Qmm mm m m= = = =-= - >    (32) 这就意味着函数H在节点i属于社团m而非社团im*时有更大的值,这是矛盾的。因此我们开始的假设是无效的,进而可以验证最大化方程H得到的社团归属() Xt的全局最优值是动态系统的固定的稳定点。证毕。     通过定理3,我们容易看出如果最大化H函数时得到的硬划分社团结构是真实的社团结构,那么经过迭代动态系统(16)就会收敛到真实的社团结构上。 3.3 方程Q的一般化形式和拓展形式 我们发现,对于许多社团探测算法,如模块度算法和Potts 模型,优化目标函数有如下的一般形式: ( ) ( )( ) ( ) ( )1111()2            1 ,nnij i jijnij i jjE t f A x t xf A x t xttRm m mmm m m mm+==-=æ=- çèö- - + ÷øåå ååå(33) 其中fm+为奖励项系数,fm-为惩罚项系数,Rm为一般冗余项,公式(33)可以表述为 ( )( )( ) ( )( ) ( ) ( )( ) ( ) ( )( )11111 1 121  ( )211122,nnn jjij i jijnij i jjn n ni ij j ij ji j jxtE t R f A x t xltf A x t x tx f A x t ftA x tRltmm m m mm mm m mm m m m mmmm= +==-=+- = = =éæê=- çêèëù ö-- ú ÷ú øû= - - -++æçèö÷øåå å åååå å å(34) 其中1( ) ( )njjl t x tmm==å是社团m在时刻t 时的规模(节点个数)。 事实上,我们可以将不同类型的指标函数解释为其具有不同的奖励参数和惩罚参数。每一种不同的参数都有自己的内在原因、优势和缺点。我们定义下列方程 ( ) ( ) ( ) ( )111 ,nn i ij j ij j ijj Q t f A x t f A x t Rm m m m m m+- == = - - + åå(35) 选择iRm,使0()iiRxtmm¶=¶,1nuiiRRm==å,例如2iu RRlmm=,可以发现,此时方程(33)明显符合方程(30)定义的能量函数通用形式。 有趣的是,对于特定的社团归属()ixtm,方程(35)所定义的iQm可以引申到几乎所有的著名指标函数,因此它是具有代表性的一般化指标: (1Hofman&wiggins模型[16] 1log , ,   .1in outout inpp f f log R l logpp m m m m m p+--= = =-(36) 2Ronhovde&Nussinov模型[17]  8  计  算  机  学  报  2016,10, ,.in f f min p Rm m m mm+-= = =     (37) 3RB Potts模型(Erdos-Renyi空模型[15] 1 , , 0.RB RB f p f p Rm m m gg +-= - = =     (38) 4RB Potts模型  (configuration空模型)[15] ( ) ( )1 , ,221 ( ),2RB RBRBi j i jijffmmR k k x t x tmmmm m mggg+->= - ==-å  (39) 其中ik是节点i 的度,m是网络中边的数量。 (5)模块度指标  [14] ( ) ( ) ( )11, , 1 ,22 iji j i jijkkf f R k k x t x tmm m m m m m+->= = = - å (40) 其中ki 是节点i 的度,m是网络中边的数量。 (6)标号传播模型[19] 1, 0, 0. f f Rm m m+-= = =                       (41) 4  自动选择参数的社团检测算法 在公式(35)中,目标函数()iQtm的系数必须提前给定,然而当运用图生成模型(graph  generative model)得到时,()iQtm中的系数便能够自动获得。事实上,我们可以通过获知网络特征和相关社团结构的先验知识来确定这些系数。文献[16]展示了由HofmanWiggins提出的一种基于贝叶斯分析的图生成模型,在此模型中系数设定为: out1log , lo l. g , og 1inout inpp f f R lpp m m m m m p+--= = =-(42) 然而在文中作者假定所有网络中的社团都有同样的边的比率,即in in12incp p p = =¼=和12out o out tcup p p = =¼=。显然这个假设并不是对多数网络都有效,例如在LFR网络[23][42]中,各个社团的边的比率是显著不同的。 这里,我们提出一个新型的图生成模型,它考虑了边比率在概率上的差异,提供了具有更好兼容性的版本。本模型实际上是一个广义的Hofman-Wiggins模型,模型中我们假定在网络中的每一个社团都有自己独有的概率,即对于社团m,有特定的inpm和outpm与之对应。所以,对于包含社团结构{q}的网络G,我们提出下列似然函数 ( )( )( )( )( )( )( )( )ij, , , ,, , ,ij ij, , ,( | { })   = . 1      .       . 1 . ,iji j i j i j i jij iji j i i j i ji j i i j i jI IIAA in inIIIAA outIVVAAn outP p G qppppkkkkkkkkk kkkkp> Î > Î> Î > Î> Î > Î--=éê åå-êêëååùúåå -úúûÕ(43) 其中ij ij1 AA=-,kp为将任一节点分配到社团µ中的概率,即, .nnkkp =                                (44)     在方程(43)中,多项式中的项I(III)对应于社团内(间)现存的边,而项II(IV)对应于社团内(间)缺失的边。依据每个社团中节点的数量,项V定义了网络的划分。我们可以将等式(43)化简为: ( ) ( )ij, , , ,, , , , 1 11.iji j i j i j i jij iji j i j i j i jAA in inout outAn out outJpp Pppppkkkkkkk k kkk k kp> Î > Î> Î > Îåå éæ ö æ ö -ê =ç ÷ ç ÷ê -è ø è øëåå-ùúûÕ(45) 因此,t 时刻的对数似然函数,可以被整理表示为一个硬划分() Xt的形式: ( ) ( ) ( ) ( )( ) ( )( ) ( )( ) ( )( )ij1log  log21          log1          log          log 1          2 log .ini j ijouti j iini j ijouti j iouti iji j ioutii j ipLP t P t x t x t Appx t x t Jpx t A px t A pnntnkkkkkkkkkkkkkkk¹¹¹¹é æö==ê ç÷ê èø ëæö-+ç÷-èø++-ù æö+ç÷úèøûååååååååå(46) 论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  9 通过比较公式(46)和公式(33),可以看出(46)中的头两项分别表示奖励项和惩罚项,而其余的为冗余项。此外,我们还可以引入参数1g和2g,用来分别控制各个项的作用强度 ( ) ( ) ( )( ) ( )( ) ( )( ) ( )( )12 ijij1γ log21         γ log1         log         log 1          2 log .ini j ijouti j iinij outi j iouti iji j ioutii j iiipH t x t x t Appx t x t Apx t A px t A pnxtnkkkkkkkkkkkkkkk¹¹¹¹é æö=ê ç÷ê èø ëæö-+ç÷-èø-+-ù æö+ç÷úèøûåååååååååå(47) 值得注意的是,等式(47)的算法复杂度是O(n2),进一步它可以被整理为: ( ) ( ) ( )( ) ( )( )( )1221γlog21         γ log11         γ log1   (      log1         log 1ini j ijouti j iinoutinij outi j iouti ijouti j iii j ipH t x t x t Appppx t x tppx t Apxtkkkkkkkkkk kkkkk¹¹¹¹é æö=ê ç÷ê èø ëö æö-- ÷ ç÷÷-èøøæö-+ç÷-èøæö +ç÷-èø+-ååååååååå ( )( )          2 log ,outiipnxtnkkkù æö+ç÷úèøûå(48) 上式则拥有O(mc)的计算复杂度,算法复杂度的详细讨论将在下一节进行。基于方程(35),可以得到模型(47)中的系数为: 1log ,inoutpfpkmkg+æö=ç÷èø        (49) 21log ,1inoutpfpkmkg-æö-=- ç÷-èø                   (50) ( ) log log 11     2log .outoutijouti j ipR A ppnnkmkkk¹ì æö ï= + -í ç÷-ï èø îü æö+ý ç÷èøþåå(51) 可以证明最小化质量函数(48)得到的硬划分社团结构() Xt与真实的社团结构是一致的。我们容易看出在简单的情况下,当节点被放置在正确的社团中时能量函数(48)的值会减小,例如假定有两个完全相似的社团1C2C,其中1 2 1 2 1 2,, in in out outC C C C C C p p p p n n = = =。另外,假定有一个节点处于1C2C之外,分别与1C2C1k2k条连边。接下来,我们比较两种情况,即这个节点要么属于社团1C  (情况1),要么属于社团2C (情况2)。在情况12中,等式(48)的差异如下: ( ) 1,2 1 2 1 211log log .21in inout outpp H k kppkkkk gg æöæ ö æ ö -D = - - - ç÷ç ÷ ç ÷ç÷-è ø è ø èø(52) 在这个例子中,假设120,o n ut ippkk gg>>,那么如果1 2kk>则1, 20 H D>,反之亦然。所以,为了使得() Ht最大,这个新节点应该划归到它能获得更多连接的社团中。 根据定理2和定理3,我们可以通过使用动态系统(16)来最大化一个质量函数。这里,我们展示一种实现最大化的更加便捷的做法。 定理4 假设质量函数形如等式(30),并且对于所有的,, ikm,在任意一个硬划分情况下有下列条件: ( )( )0,ikiQtxtm¶=¶                       (53) 那么最大化质量函数(30)得到硬划分归属X,便是动态系统(54)的一个渐进稳定点。 ( )( )( )( )( )( )( ) 11.iiHtxtiiHtcxtix t extx t emmmmkk¶-¶¶-¶=+=å      (54) 证明.  在等式(30)两边求导,我们可以得到 ( )( )( ) ( )( )( )1.2iii ii H t Q tQ t x tx t x tkmkk mmæö ¶¶=+ç÷ ¶¶èøå (55) 10  计  算  机  学  报  2016年 假设X(t)是一个硬划分,通过假设( )( )0,ikiQtxtm¶=¶我们可以得到 ( )( )( )12.iiHtQxttmm¶=¶                (56) 从而根据等式(56)和( )( )0ikiQtxtm¶=¶,我们可以推断出动态系统(16)与动态系统(54)  Jacobian行列式在() Xt上是一致的。因此,如果() Xt是最大化H得到的结果,那么根据定理3它就是等式(16)的一个渐进稳定点,从而也就是系统(54)的一个渐进稳定点。证毕。 推论1 如果网络参数,即inpm,outpm和nm,{ } 1, 2,...,c m=是已知的,并且最大化函数H能够得到硬划分() Xt,那么() Xt就能通过迭代动态系统(54)获得。 本文提出的算法是以定理4为基础的。为此我们需要计算( )( )iHtxtm¶¶使得( )( )0ikiQtxtm¶=¶。根据公式(46),通过重整和变形,我们可以得到( )( )iHtxtm¶¶为: ( )( )( )( )( )( )( )12log12 2 log21log21 11            21             2 log1inoutininioutiiinin in outoutiinii oupp p Htlk x t x t pplp pp x tpn k xpmm mmm m m mmmm mmmmm m mmggéù êú êú êú êú êú ëû æçççççæö¶ ç÷æö ¶èø =+ç÷¶¶èøæö-¶ ç÷ æö- -èø ç÷ +ç÷¶èø-+--è-( )( )( )( )( )( )( ) ( )log1             log2log 11             ( 1 )2             1 log 1 log 1.toutoutai aiinaaiinipk k pxtpn n kxtnn k pnmmmmmmmmmmù æöú ç÷úèøûéù¶æö êú ++ç÷¶ êúèø ëû é ¶-ê + - -¶ êëæöù + - - - + +ç÷ ûèøåå(57) 为了满足准则(53)1g和2g应该被适当地选取。从数值上来说,我们发现11inpmg =和21 g =能近似完美地满足这个准则。通过将等式(57)中的这些系数替换,我们得到 ( )( )( )( )( )( )( )log12 2 log21log21 11 21  2 log11 2inoutininiin outiiinin in outoutiinii outaapp p Htlk x t p x t pplp pp x tpn k xpkmm mmm m m m mmmm mmmmm m mmméùæö¶ êúç÷æö ¶ êúèø =+ç÷ êúç÷ ¶¶èø êú êú ëû é æö-¶ ê ç÷ æö- -êèø ç÷ +êç÷¶êèø êëù æö-+ - - ú ç÷-úèøû+ å( )( )( )( )( )( )( ) ( )logloglog 11  ( 1 )2  1 log 1 log 1.outoutiiinaaiinipkpxtpn n kxtnn k pnmmmmmmmmméù¶æö êú+ç÷¶ êúèø ëû é ¶-ê + - -¶ êëæöù + - - - + +ç÷ ûèøå  (58) 论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  11 在公式(58)中,() ntm,()inptm和()outptm都是以()ixtm为自变量的方程,具体形式请见公式(11)(14)(15)。 为了实现社团划分,接下来我们提出基于迭代动态系统(54)的快速算法(算法1)。此外,在每一个步骤中,动态系统(54)以一个预先确定好的步数进行迭代,这也就是动态迭代。具体的算法流程如下所示。 算法1    社团划分算法流程 输入:网络G,其节点数为n,边数为m。最大迭代步数maxR 输出:社团归属矩阵X   1:初始化(0) X并且设置bestX(4.2中阐述)2: 重复 3:利用等式(11)(12)(13)(14) (15) 分别更新, , ,in out inn l l pm m m m和outpm; 4:利用公式(58)计算( )( )iHtxtm¶¶; 5:利用公式(54)迭代归属矩阵() Xt6:利用公式(46)计算函数() LP t7:如果已经达到迭代步数上限maxR,则转向步骤8;否则,回到步28:将满足() LP t最大化的归属() Xt记为tX9:如果()t bestLP X LP >,令() best tLP LP X =并且令best tXX=; 10:如果达到迭代最大步数maxR,返回bestX; 否则,回到步骤14.1 算法复杂度 在每步动态迭代中,计算对数似然函数(46)的复杂度是max() O m c ×,其中maxc是社团数量的最大值。同时,对于拥有强社团结构的网络,该动态过程的收敛速度是相当快的。动态迭代的次数maxR并不直接取决于节点的数量,实际上,它与社团结构的模糊程度是相关的。因此,算法总的计算复杂度为max() O m c ×,而对于稀疏网络,更会下降为max() O n c ×。另外,计算复杂度与网络的拓扑结构相关。在许多网络中,社团的数目比网络的节点数目要小得多,例如空手道俱乐部网络[46],在这些实例中,对于稀疏网络,算法的计算复杂度为() On。表2列出了一些著名算法的计算复杂度,通过比较可以看出我们的算法是非常快速的。然而,在一些特殊的网络中,社团的数量和网络的节点数量是相关的,例如团环网络(ring  of  cliques),其中的每一个团只有很少数量的节点。在这些网络中,复杂度仍然为max() O n c ×。 表2  在稀疏网络中,著名算法计算复杂度分析比较 算法  计算复杂度 CNM[38] 2O( ) nlo n g DA[39] 2O(  ) n lo n g Louvain[10] O(  ) nlo n g OCR-HK[37] 2() On Bayesian inference[22] ) O(nlog na Variational Bayesian[16] 1.44() On RN Potts model[17] 1.3() On      为了检验算法的性能,我们与7个著名的算法进行比较,其中包括Louvain 方法[10]Newman Fast(NF) 方法[14]Hoffman&Wiggins方法[16]SA方法[20]Peixito方法[33]Danon方法[39]CNM方法[40]。同时我们也考虑网络的规模,检验其与算法性能的关系。这里,实验环境是一台拥有2GHz  CPU4GB内存的台式电脑,运行系统是Windows 7,程序软件是Matlab2010b。为了进行测试,我们利用LFR模型[23][42]生成稀疏网络,该模型中的社团结构是提前定义好的,但是网络中节点的连接情况是由参数控制的,包括节点数目n、节点的平均度<k>、最大节点度maxk、混合比例参数(Mixing Parameter)q(每个节点与其他社团的节点共享q比例的边)、最小社团规模minc和最大社团规模maxc。在LFR网络中,混合比例参数(Mixing Parameter)q用来调整网络的模糊性。q的变化范围为0,1 êú ëû,较大的q代表更加弱的社团结构。我们统一设定实验中网络的节点平均度<k>=8(和WWW网络接近,为典型的稀疏网络)、最大节点度maxk=20、最小社团规模minc=10和最大社团规模maxc=100(在网络规模固定的情况下,mincmaxc控制网络中社团的个数)。为了证明结果的一般性,我们分别在0.2 q=和0.6 q=的两个LFR网络上进行试验,结果展示在图2中。首先看出我们的算法在所有的网络规模中都比其他的方法快;其次,我们方法的计算时间几乎是是随着网络的规12  计  算  机  学  报  2016年 模线性扩展的,因此可以在拥有数百万甚至数亿节点的大规模网络中进行实现。           (a)                                                       (b) 2  不同规模的LFR网络下,各个算法运行时间的比较,其中  (a)0.2 q=和  (b)0.6 q=.   4.2初始化社团归属矩阵 在算法1的步骤1中,社团归属矩阵应该给定初始化形式。我们设计如下的方法,首先,初始归属矩阵( ) 0ixm被设定为: ( ) { } { }110 ; 1, 2, , , 1, 2, ,. . 0,iicix y i n ccs t ymmmmm== + = ¼ = ¼= å(59) 其中iym是一个小的高斯噪声。这个策略可以避免在性质1中描述的第二类平凡解。在接下来的步骤中,受益于之前迭代过程的最好结果,我们有以下改进策略 ( ) { } { }10 ; 1, 2, , , 1, 2, ,. . 0,besti i icix x y i n cs t ym m mmmm== + = ¼ = ¼= å(60) 其中bestixm是bestX( , ) i m元素。换句话说,此过程通过迭代渐进地去改进结果。值得注意的是,此步的高斯噪声的强度,即iym,必须比上一次(公式(59))的大很多;否则,动态过程将会收敛到之前的结果。 4.3确定最优的社团个数 在运行算法之前,我们应当预先设定社团的数量,因为它并不是一个显著的先验信息。在许多著名算法中,社团数量被隐式地提前指定,因为不同的社团个数会对划分质量产生极大地影响。例如, CNM算法[38]Louvain算法[10]所考虑的初始值为n,而对于二分迭代算法如SA[20]DA[39],初始值则设为2。 在算法1中,我们只需要设定社团的初始个数为一个大于或者等于实际社团个数的值,因为额外的社团会随着动态系统在迭代过程中逐渐被合并掉,因此,这是一个粗糙且容易实现的步骤。 5  实验 本文算法不仅在人工基准网络有良好的性能,另外在真实数据网络[47]-[53]特别是大规模网络上,如大型科学家合作网络,有着出色的表现。 5.1 人工网络 首先,我们将算法应用到著名的GNLFR基准网络[27][41]。实验结果表明,即使在含有模糊社团结构的网络中,算法也具有非常高的准确性。 图3展示了在GN基准网络[14][40]中不同算法性能的比较结果。GN网络由Newman等人提出,共包含n=128 个节点,  分成4个社团,  每个社团包含32 个节点。假设属于相同社团的节点对以概率Zin 相连接,  而属于不同社团的节点对以概率Zout相连接。网络中点的平均节点度固定为<k> =16,可以得到Zin Zout  有关系31Zin + 96Zout=16。我们发现,当7.4outZ £时,基本上所有算法都具有较高的性能论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  13 (0.75 NMI³)。随着outZ的增加,基本上所有算法的划分效率都会急剧降低,但是本文算法直到8outZ ®时依然具有最高的准确率,从而说明其划分能力的高效性。  图3 GN网络中7种不同算法的标准互信息值(NMI)对比,图中的每个点表示50次不同实验结果的平均值。 为了进一步进行验证,我们将算法应用到LFR基准网络上。LFR网络模型由Lancichinetti等人提出[23][42],具有无标度特征的度分布和社团规模分布,因此更加接近现实中社会和生物系统。LFR网络模型的生成由一些参数控制:节点数目n、节点的平均度<k>、最大节点度maxk、混合比例参数(Mixing Parameter)q(每个节点与其他社团的节点共享q比例的边)、最小社团规模minc和最大社团规模maxc。q的变化范围为0,1 êú ëû,用来调整网络的模糊性,较大的q代表更加弱的社团结构。在本次实验中,我们统一设定网络的节点平均度<k>=10、最大节点度maxk=20,每个社团的规模有大小之分(由参数mincmaxc控制,从而在网络规模固定的情况下可以调节社团的个数)。结果如图4所示,其中当网络规模为1000 n=时,其拥有的小(大)社团个数为100(50),当网络规模为5000 n=时,其拥有的小(大)社团个数为300(200)。我们可以发现,在每一种情况下,本文算法都具有最高的标准互信息值(NMI)值。 另外,我们还将算法应用到包含1000个社团,每个社团包含10个节点的团环网络(ring of cliques)上。这种团环网络[11]可以用来说明模块度指标(和一些其他的指标)有分辨率限制问题(resolution limit problem)。团环网络利用少量的边将一些团(完全图)连接起来,并使用团的数目和每个团的规模这两个参数进行控制。结果显示,本文算法不仅能精确地发现每个团,而且不具有分辨率限制问题,进一步验证了算法的高效性。        (a)  (b)    (c) 14  计  算  机  学  报  2016年  (d) 4本文算法与一些著名算法的性能对比  (a) 1000 n=的小社团LFR网络; (b) 1000 n=的大社团LFR网络; (c) 5000 n=的小社团LFR网络; (d) 5000 n=的大社团LFR网络。每个点为50次计算结果的平均值。 5.2  科学家合作网络 进一步,为了验证算法的高效性,我们将算法应用到一个大规模网络--科学家合作网(Scientists Cooperation Network)[14][40]上。该网络包含56276个点和315810条加权边,代表了56276位物理学家在预印本网站arxiv.org共同署名发表论文的合作关系。我们根据算法的划分结果,输出转换后的邻接矩阵(相同社团内的节点被整合在一起,呈现出层次结构)进行可视化,如图5(a)所示。可以看出,和许多社会网络一样,科学家合作网呈现出较强的社团特征和层次特征,其中三个最大的社团具有现实意义,分别代表物理的主要研究领域:核物理、天体物理和凝聚态物理。  (a)  (b) (c) 图  5算法在科学家合作网上的运算结果。(a)  转换后的邻接矩阵; (b)  社团规模的幂率分布; (c)  八个社团的子图片段,不同社团用不同的形状表示。 通过算法,我们从网络中共挖掘出696个社团。图5(b)以幂率坐标的形式展示了社团的规模分布情况,可以看出,这是一种典型的无标度分布,这和许多社会网络一致。最大社团节点数为202,最小社团节点数为2,平均社团节点数为81。社团节点分布呈现不均匀特征,5.9%的大规模社团包含大约30.2%的节点,而剩余社团的规模均较小。 进一步,为了验证社团划分的准确性,我们截取并展示了一个包含8个社团的子图片段,不同的社团不用的形状表示,如图5(c)所示。可以容易看出,算法的划分结果非常好,而且该结果与文献[40][41]完全相同,因此表明其非常适合在大规模网络上进行运算,对进一步研究分析大数据问题具有极其重大的价值。 5.3  更多现实网络 最后,为了更加充分地验证我们的算法,我们在七个著名的现实世界网络上进行试验,结果在表3中展示。为了方便地和现有方法进行比较,我们展示了现有方法在这些网络中得到的最高模块度论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  15 (Modularity)Q值,这些最高值是通过比较大量划分算法后得到的,相关网络和最高Q值的文献出处也被展示出来。 表3  在现实网络中算法性能的分析比较 网络  网络参考文献 现有方法的最高Q值 最高Q值参考文献 本文算法的QEmail  [20]  0.579  [54]  0.568 US Football  [40]  0.606  [54]  0.602 Zachary Karate [46]  0.42  [54]  0.416 Les Miserables  [50]  0.561  [54]  0.554 Dolphin  [51]  0.531  [54]  0.527 Jazz  [52]  0.446  [54]  0.439 PGP-Key signing [53]  0.878  [54]  0.883     从表3中可以看出,本文算法的Q值非常接近现有方法的最高Q值,而且我们的算法具有一般方法所不具有的线性时间,其计算复杂性非常小。值得一提的是,在PGP-Key signing network上,本文算法比现有方法的最高值还高,充分展示了本文算法的高效性。 表4  在大规模网络数据中的算法性能分析 网络  n  m  Rg  Rm  NMI Amazon  334863  925872  75149  73961  0.404 Dblp  317080  1049866  13477  14531  0.412 Youtube,      1134890  2987624  8385  10156  0.337 Livejournal,  3997962  34681189  287512  176351  0.304 Orkut  3072441  117185083  6288363  5963451  0.376 Friendster  65608366  1806067135  957154  937640  0.424     为了进一步验证算法应用的广泛性,我们在六个大规模网络数据上进行实验验证。这六个大规模网络数据是从Stanford  Network  Analysis  Platform (SNAP)  1下载的,并且提供了真实的网络划分以供比较验证。其中Amazon网络是一个产品网络,其中两个产品如果经常被同时购买,那么它们之间就有一条边;Dblp网络展示了科学家之间共同发表论文的关系;Youtube, Livejournal, Orkut和  Friendster网络则是从不同社交网站中提取的社会关系网络。     我们将划分结果和一些网络关键属性在表4中展示出来,其中nm分别代表网络的点数和边数,                                                                 1  http://snap.stanford.edu/data/index.html RgRm分别代表真实社团数目和划分社团数目,NMI代表互信息值的值[23][42]。通过比较很多现存的算法[54][55][56],我们发现本文算法具有较高的准确性,非常适合于在百万节点以上的网络中进行实验分析。值得一提的是,我们发现划分社团数目Rm和真实社团数目Rg非常接近,从而验证了本算法具有非常好的模型选择功能。 6  结论     本文提出了一种高效的动态社团划分算法,通过引入一种新型的基于离散时间的动态系统,来描述社团归属的从随机状态到最优划分的动态轨迹,并利用严格的数学分析找出了社团归属动态收敛到最优的条件。另外,本文还创新性地提出了一种划分指标函数的一般化形式,通过选择不同的参数,可以拓展到很多著名的划分指标函数。本算法非常高效,计算复杂度分析表明在稀疏网络中,算法需要的时间与网络节点数目呈线性关系。 此外,我们还可以对算法的应用进行更深入的探讨,例如:1.  如何进一步加快算法速度,使得其能够在超大规模的网络上准确划分社团,如包含几亿到几十亿节点的微博网络和生物网络上;2.  由于现实世界并不都是双向关系,网络中会出现单向或者混合方向的边,如何利用算法高效地处理这种混杂网络,是一个挑战。  致  谢  中国科学院管理学院石勇教授、中央财经大学刘志东教授对本文提出了很多建设性建议,特表示感谢。最后,感谢评审老师细致耐心的审查! 参  考  文  献 [1]  Fortunato  S.  Community  detection  in  graphs.  Physics  Reports,  2010, 486(3), 75-174. [2]  Gong  Mao-Guo,  Cai  Qing,  Chen  Xiao-Wei  and  Ma  Li-Jia.  Complex network  clustering  by  multiobjective  discrete  particle  swarm  optimization based on decomposition, IEEE Transactions on Evolutionary Computation,  2014, 18(1), 82-97. [3] Pizzuti  C. A  multiobjective  genetic  algorithm  to  find  communities  in complex networks. IEEE Transactions on Evolutionary Computation, 2012, 16(3), 418-430. [4]  Rubio-Largo  A,  Vega-Rodriguez  M  A,  Gomez-Pulido  J  A  and Sanchez-Perez Juan M. Multiobjective Metaheuristics for Traffic Grooming 16  计  算  机  学  报  2016in  Optical  Networks.  IEEE  Transactions  on  Evolutionary  Computation, 2013, 17(4), 457-473. [5] Rolland T, Tasan M, Charloteaux B, et al. A Proteome-Scale Map of the Human Interactome Network. Cell, 2014, 159(5), 1212-1226. [6] Liu Ying, Moser J, Aviyente S. Network Community Structure Detection for  Directional  Neural  Networks  Inferred  From  Multichannel  Multisubject EEG  Data.  IEEE  Transactions  on  Biomedical  Engineering,  2014,  61(7), 1919-1930. [7]  Gharavi  H,  Hu  Bin.  Multigate  communication  network  for  smart  grid. Proceedings of the IEEE, 2011, 99(6), 1028-1045. [8]  Tremblay  N,  Borgnat  P.  Graph  Wavelets  for  Multiscale  Community Mining. IEEE Transactions on Signal Processing, 2014, 62(20), 5227-5239. [9] Yang Bo, Liu Ji-Ming , Feng Jian-Feng. On the Spectral Characterization and  Scalable  Mining  of  Network  Communities.  IEEE  Transactions  on Knowledge and Data Engineering, 2012, 24(2), 326-337. [10] Blondel V. D, Guillaume J, Lambiotte R, Lefebvre E. Fast unfolding of communities  in  large  networks.  Journal  of  Statistical  Mechanics:  Theory and Experiment, 2008, 2008(10), 10008. [11] Fortunato S, Barth_elemy M. Resolution limit in community detection. Proceedings  of  the  National  Academy  of  Sciences  of  the  United  States  of America, 2007, 104(1), 36-41. [12]  Khadivi  A,  Rad  A  A,  Hasler  M.  Network  Community  Detection Enhancement  by  Proper  Weighting.  Physical  Review  E,  2011,  83(4), 046104. [13] Zhang Xiang-Sun, Wang Rui-Sheng, Wang Yong, Wang Ji-Guang, Qiu Yu-Qing, Wang Lin, Chen Luo-Nan. Modularity optimization in community detection of complex networks. Europhysics Letters, 2009, 87(3), 38002. [14]  Newman  M  E  J,  Girvan  M.  Finding  and  evaluating  community structure in networks. Physical Review E, 2004, 69(2), 026113. [15]  Reichardt  J,  Bornholdt  S.  Statistical  mechanics  of  community detection. Physical Review E, 2006, 74(1), 016110. [16] Hofman J M, Wiggins C H. Bayesian Approach to Network Modularity. Physical Review Letters, 2008, 100(25), 258701.  [17]  Ronhovde  P,  Nussinov  Z.  Local  resolution-limit-free  Potts  model  for community detection. Physical Review E, 2010, 81(4), 046114. [18]  Newman  M  E J.  Fast  algorithm  for  detecting  community  structure  in networks. Physical Review E, 2004, 69(6), 066133. [19]  Raghavan  U  N,  Albert  R,  Kumara  S.  Near  linear  time  algorithm  to detect  community  structures  in  large-scale  networks.  Physical  Review  E, 2007, 76(3), 036106. [20]  Guimera  R,  Nunes  Amaral  L  A.  Functional  cartography  of  complex metabolic networks. Nature, 2005, 433(7028),895-900.  [21]  Duch  J,  Arenas  A.  Community  detection  in  complex  networks  using extremal optimization. Physical Review E, 2005,72(2), 027104. [22] Hastings M. B. Community detection as an inference problem. Physical Review E, 2006, 74(3), 035102.  [23]  Lancichinetti  A,  Fortunato  S.  Community  detection  algorithms:  A comparative analysis. Physical Review E, 2009, 80(5), 056117. [24]  Nadakuditi  R,  Newman  M  E J. Graph spectra and  the detectability  of community  structure  in networks.  Physical  Review  Letters,  2012, 108(18), 188701. [25]  Radicchi  F.  Driving  interconnected  networks  to  supercriticality. Physical Review X, 2014, 4(2), 021014.  [26]  Radicchi  F.  A  paradox  in  community  detection.  Europhysics  Letters, 2014, 106(3), 38001.  [27]  Radicchi  F.  Detectability  of  communities  in  heterogeneous  networks. Physical Review E, 2013, 88(1), 010801.  [28]  Zhang  Pan,  Moore  C.  Scalable  detection  of  statistically  significant communities  and  hierarchies,  using  message  passing  for  modularity. Proceedings  of  the  National  Academy  of  Sciences,  2014,  111(51), 18144-18149. [29]  Rosvall  M,  Bergstrom  C.  T.  Maps  of  random  walks  on  complex networks reveal community structure. Proceedings of the National Academy of Sciences, 2008, 105(4), 1118-1123. [30] Esquivel A V, Rosvall M. Compression of flow can reveal overlapping modular organization in networks. Physical Review X, 2011, 1(2), 021025. [31]  Peixoto  T  P.  Parsimonious  module  inference  in  large  networks. Physical Review Letters, 2013, 110(14), 148701.  [32] Li Hui-Jia, Li Hui-Ying, Li Ai-Hua. Analysis of Multi-Scale stability in Community  Structure.  Chinese  Journal  of  Computers,  2015,  38(2), 301-312(in Chinese). ( 李慧嘉,李慧颖,李爱华.  多尺度的社团结构稳定性分析. 计算机学报, 2015, 38(2), 301-312.) [33]  Peixoto  T  P.  Model  selection  and  hypothesis  testing  for  large-scale network  models  with  overlapping  groups.  Physical  Review  X,  2015,  5(1), 011033. [34]  Aldecoa  R,  Marin  I.  Surprise  maximization  reveals  the  community structure of complex networks. Scientific reports, 2013, 3, 1060. [35] Li Hui-Jia and Zhang Xiang-Sun.  Analysis  of  stability  of  community structure  across  multiple  hierarchical  levels. Europhysics  Letters,  2013, 103(5), 58002 [36]  Stanoev  A,  Smilkov  D,  Kocarev  L.  Identifying  communities  by influence  dynamics  in  social  networks.  Physical  Review  E,  2011,  84(4), 046102.  [37] Boccaletti S, Ivanchenko M, Latora V, Pluchino A. Detecting complex network  modularity  by  dynamical  clustering.  Physical  Review  E,  2007, 75(4), 045102.  [38] Clauset A, Newman M. E. J, Moore C. Finding community structure in 论文在线出版号  No.160            李慧嘉等:社团结构迭代快速探测算法  17 very large networks. Physical Review E, 2004, 70(6), 066111.  [39]  Danon  L,  Diaz-Guilera  A,  Duch  J,  Arenas  A.  Comparing community structure  identification.  Journal  of  Statistical  Mechanics:  Theory  and Experiment, 2005, 2005(09), 09008.  [40]  Girvan  M,  Newman  M.  E.  J.  Community  structure  in  social  and biological  networks.  Proceedings  of  the  National  Academy  of  Sciences  of the United States of America, 2002, 99(12), 7821-7826. [41]  Jiang  Qi-Xia,  Zhang  Yan,  Sun  Mao-Song.  Community  Detection  on Weighted Networks: A Variational Bayesian Method. Advances in Machine Learning, Springer Berlin, Heidelberg, 2009, 5828, 176-190. [42] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community  detection  algorithms.  Physical  Review  E,  2008,  78(4), 046110-046115. [43] Shen Hua-Wei, Cheng Xue-Qi, Chen Hai-Qiang, Liu Yue. Information Bottleneck  Based  Community  Detection  in  Network.  Chinese  Journal  of Computers, 2008, 31(4), 677-686(in Chinese). (  沈华伟,  程学旗,  陈海强,  .  基于信息瓶颈的社区发现.  计算机学报, 2008, 31(4), 677-686.) [44]  Tibely  G,  Kertesz  J.  On  the  equivalence  of  the  label  propagation method  of  community  detection  and  a  Potts  model  approach.  Physica  A, 2008, 387(19-20), 4982-4984. [45]  Shi  J,  Malik  J.  Normalized  cuts  and  image  segmentation.  IEEE Transactions  on  Pattern  Analysis  and  Machine  Intelligence,  2000,  22(8), 888-905. [46] Zachary W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4), 452-473. [47]  Brownlee  A  E  I,  McCall  J  A.  W,  Zhang  Q.  Fitness  Modelling  with Markov Networks. IEEE Transactions on Evolutionary Computation, 2013, 17(6), 862-879. [48]  Echegoyen  C,  Mendiburu  A,  Santana  R,  Lozano  J.  A.  Toward understanding  EDAs  based  on  Bayesian  networks  through  a  quantitative analysis.  IEEE  Transactions  on  Evolutionary  Computation,  2012,  16(2), 173-189.  [49]  Li  Hui-Jia,  Daniels  J.  Social  significance  of  community  structure: Statistical view. Physical Review E, 2015, 91(1), 012801. [50] Knuth  D  E. The  Stanford  GraphBase:  A  Platform  for  Combinatorial Computing, Reading, New York, USA : Addison-Wesley Professional, 1993, 37, 592. [51] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M. The bottlenose  dolphin  community  of  Doubtful  Sound  features  a  large proportion  of  long-lasting  associations,  Behavioral  Ecology  and Sociobiology, 2003, 54(4), 396-405. [52] Gleiser  P,  Danon  L. List  of  edges  of  the  network  of  jazz  musicians, Advances in Complex Systems, 2003, 6, 565. [53] Boguna  M, Pastor-Satorras  R, Diaz-Guilera A,  Arenas  A. Models  of social  networks  based  on  social  distance  attachment,  Physical  review  E, 2004, 70(5), 056122. [54] Agarwal G, Kempe D. Modularity-maximizing graph communities via mathematical  programming,  European  Physical  Journal  B,  2008,  66(3), 409-418. [55] Bhatia  N  P, Szego  G  P.  Stability  theory  of  dynamical  systems. Berlin HeidelbergSpringer-Verlag, 2002. [56] Yang  J,  Leskovec  J. Defining  and  evaluating  network  communities based  on  ground truth,  Knowledge  and  Information  Systems,  2015,  42(1), 181-213.     Li Hui-Jia, born in 1985, Ph.D, lecturer. His research interests include data mining, complex  networks,  and  information retrieval.   Li Aihua, born in 1978, Ph.D, associate professor. Her research interests  include  data  mining  and  management  decision sciences.   Li  Hui-Ying,  born  in  1983,  Ph.D,  assistant  professor.  Her research  interests  include  bioinformatics,  complex  networks, and data mining.     BackgroundDetecting community  structure  in networks  has  broad applications  since  nodes  in  the  same  community  generally possess  mutual  properties  or  relationships  relative  to  nodes interconnecting  different  communities.  Typical  examples include  a  social  circle  in  which  members  have  common interests,  a  group  of  proteins  that work  together  for  functional realization,  and  tweets  under  the  same  topic  spreading  the opinion.  Distinguishing  the  communities  facilitates  the operation,  control,  and  optimization  of  networked  systems, such  as  developing  tools  for  precision marketing,  identifying 18  计  算  机  学  报  2016target  points  for drug  discovery,  searching  and  mining  online social networks for trend predictions and so on. The  traditional  optimization  or  heuristic  methods  are usually  used  in  present  techniques,  with the  common  logic  of comparing  the  intuitive  properties  and  external  behaviors  in and  outside  of  the  communities.  However,  to  obtain  an acceptable  accuracy,  these  methods usually  have  a  high-level computational  complexity.  In  this  paper,  we  propose  a  new algorithm using dynamical  system to realize the fast and exact detection  of  communities  in  complex  networks.  First,  a discrete-time  dynamical  system is  introduced to  describe  the assignment  of  community  memberships,  and  the  conditions driving  the  convergence  of  dynamics  trajectory to  the  optimal situation  is formulated. Further,  we  design  a  new  type  graph generative  model,  which  performs  the  algorithm  free  of  the parameters. By analyzing the eigenvalue gap of the Markovian transition matrix, we provide a mathematical theory to identify the  optimum  number  of  communities  in  a  network,  and  the stability  of  community  structure.  Our  algorithm  can  also  be generalized to unify the conventional algorithms widely applied. Our algorithm is highly efficient: the computational complexity analysis  shows that  the  required  time  is  linearly  dependent  on the number of all nodes in a sparse network. This  research  is  supported  by  National  Nature  Science Foundation under Grant 913242031113100971401194 and 71401188.  The  first  two  foundations  aim  to  the  study  on complex networks from many scientific fields. The main focus is  on  three  aspects:  The  statistical  properties  of  complex networks, the model of the evolution of complex networks, the dynamics  of  complex  networks.  The study  of  community structure properties is  a  fundamental task  of  these works. The last  two  foundations  aim  at  studying  community  structure characteristics in social network specifically. The authors have made some  in-depth  researches on  the  measure  of  community structure,  the  method  to  uncover  the  hierarchical  and overlapping  community  structure  in  large  networks,  and  its application  on  finding  the intrinsic  properties  of  community structure.  

[返回]
上一篇:2017ESI中国200所高校综合排名
下一篇:中国研究生在校生规模中长期预测