复杂网络中的集团结构

1、复杂网络中的社团结构 2010年7月19日复杂网络中的集团结构纲要实际网络中的社团结构社团结构定义检验算法的网络与Q函数探索社团结构的方法算法的评价以及加权网络的聚类方法一个具体工作（基于比较性定义下的聚类方法） 复杂网络中的集团结构实际系统中的社团结构复杂网络中的集团结构Collaboration network between scientists working at the Santa Fe Institute. The colors indicate high level communities obtained by the algorithm of Girvan and Newm

2、an and correspond quite closely to research divisions of the institute.Zacharys karate club, a standard benchmark in community detection. The colors correspond to the best partition found by optimizing the modularity of Newman and Girvan.复杂网络中的集团结构Community structure in technological networks.Sample

3、 of the web graph consisting of the pages of a web site and their mutual hyperlinks, which are directed. Communities, indicated by the colors, were detected with the algorithmof Girvan and Newman, by neglecting thedirectedness of the edges.Best division of econophysicists collaboration network, with

4、 the divisions detected by GN algorithm represented by different colors and numbers.复杂网络中的集团结构Community structure in protein-protein interaction networks. The graph pictures the interactions between proteins in cancerous cells of a rat. Communities, labeled by colors, were detected with the k-clique

5、 percolation method by Palla et al.复杂网络中的集团结构人际关系网引文网WWW网新陈代谢网食物链网社团结构和功能之间的关系复杂网络中的集团结构社团结构的定义复杂网络中的集团结构社团结构的描述性定义Community structure（社团结构） is the groups of network vertices. Within these groups there have dense internal links, but between groups there are fewer edges. M. E. J. Newman, Detecting co

6、mmunity structure in networks. Eur. Phys. J. B 38, 321-330 (2004). 复杂网络中的集团结构社团结构的数学描述Clique - Complete graphk-core - subgraph in which each node is adjacent to at least a minimum number, k, of the other nodes in the subgraph.K-Clique CommunityLS-SetAn LS-set is a set of nodes such that each of its

7、proper subsets has more ties to its complement within the set than outside.复杂网络中的集团结构社团结构的比较性定义复杂网络中的集团结构检验算法的网络及Q函数复杂网络中的集团结构人工网络GN BenchmarkLFR benchmark一些实证网络（已知社团结构） 检验算法的网络复杂网络中的集团结构GN经典人造网常用的人造网是由128个顶点构成的网络，这128个顶点被平均分成四份，构成四个社团，每个社团包含32个顶点。每个顶点度的期望值为16，Zin表示顶点与社团内部顶点连边数目的期望值，Zout表示顶点与社团外顶点连边

8、数目的期望值，从而Zin + Zout =16.Zout越小说明顶点与社团外部的连接越少，网络的社团结构越明显； Zout越大说明网络越混乱，社团结构越不明显。对于Zout值大的网络还能够基本正确的对网络进行划分的算法，在实际应用中适用范围更广，价值更大。复杂网络中的集团结构LFR benchmarkLFR benchmark is a generalization of the GN benchmark to heterogeneous group sizes and graph degree distribution. Groups are also a priori fixed with

9、 the degrees and the community sizes following a power-like distribution. As before, nodes have kin connections within its own group and kout edges linking elsewhere.复杂网络中的集团结构检验算法的一些实际网络空手道俱乐部网（34个点，78条边）科学家合作网（物理学家、经济物理学、桑塔菲研究所） 美国大学足球赛季网（115个点，616次常规赛）猴子网（16个点）已知社团结构，便于比较算法的好坏。复杂网络中的集团结构评价函数Modul

10、arity含义是：网络中连接社团内部顶点间的边的比例与拥有相同社团结构但是顶点间随机连接的网络中连接社团内部顶点间的边的比例的期望值的差值。对Q函数的质疑复杂网络中的集团结构探测集团结构的基本方法复杂网络中的集团结构寻找社团结构的方法基于网络拓扑结构GN algorithm based on edge betweenness： M. Girvan, M. E. J. Newman PNAS 99 7821(2002)Spectral analysis； L. Donetti, M. A. Munoz J. Stat. Mech. (2004) P10012基于网络上的动力学Potts Mode

11、l；J. Reichardt, S. Bornhold, Phys Rev Lett. 93 (2004) 218701Random Walk：，cond-mat/0412368 ; H. ZhouCircuits：F. Wu, B.A. Huberman, Eur. Phys. J. B 38 (2004) 331Q函数优化Extremal Optimization：J. Duch A. Arenas, Phys Rev E. 72 (2005) 02710Newmans fast algorithm； M. E. J. Newman, Phys Rev E. 69 (2004) 06613

12、3复杂网络中的集团结构1、层次聚类法根据顶点间的距离或相似程度划分网络中的社团。具体过程为： 1 定义两点间的距离或相似度，社团与社团间的距离或相似度； 2 将每个顶点视为一个社团，并根据定义计算社团间的距离或相似度； 3 将距离最近的或相似度最高的社团合并，形成新的社团，重新计算社团间的距离或相似度； 4 重复第3步操作，直到网络中的所有顶点被归入一个社团为止。复杂网络中的集团结构结构等价定义顶点间的相似度结构等价：如果一个顶点与网络中其余顶点的连接方式和另一顶点与网络中其余顶点的连接方式完全相同，则这两个顶点结构等价。例如在人际关系网中，如果两个人的朋友完全相同，则这两个人就是结构等价的。

13、用欧几里德距离度量衡量结构等价。顶点i，j的距离为此距离等于0时，两顶点结构等价。 复杂网络中的集团结构其他距离及相似度的定义可参见 Mika Gutafsson, Comparison and validation of community structures in complex networks. Physica A 367(2006)559-576 M. Girvan, E. Newman, Community structure in social and biological networks, PNAS99(12)(2002)7821-7826复杂网络中的集团结构层次聚类法社团

14、与社团间的距离可以采用最短距离法、最长距离法或平均距离法。层次距离的过程可以用树状图表示复杂网络中的集团结构2、GN算法Girvan和Newman提出的分裂算法已经成为探索网络社团结构的一种经典算法，简称GN算法。 由网络中社团的定义可知，所谓社团就是指其内部顶点的连接稠密，而与其他社团内的顶点连接稀疏。这就意味着社团与社团之间存在联系的通道比较少，并且要想从一个社团到另一个社团，至少要通过这些通道中的一条。如果能找到这些重要的通道，并将它们移除，那么网络就自然而然的分成了各个社团。 用最短路径边介数标记每条边对连通性的重要程度。复杂网络中的集团结构GN算法最短路径边介数的定义为：找出每对顶点

15、间的最短路径，计算每条边被多少条最短路径通过，这个值就是这条边的最短路径边介数。GN算法的具体过程： 计算网络中各条边的边介数； 找出边介数最大的边，并将它移除（如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开）； 重新计算网络中剩余各条边的边介数； 重复第、步，直到网络中所有的边都被移除。复杂网络中的集团结构GN算法与Q值最优社团划分的选择复杂网络中的集团结构3、 边集聚系数法边集聚系数：一条边的集聚系数等于网络中利用这条边构成的三角形的个数除以利用这条边潜在可以构成三角形的个数。连接i，j两点的边的集聚系数表示为：连接不同社团的点的边，被较少的三角形包含，或者根

16、本不包含于任何三角形。从而边集聚系数就小。然而社团内部由于有比较稠密的边，所以应该包含较多的三角形，因此连接集团内部的点的边的边集聚系数就大。复杂网络中的集团结构边集聚系数法修正的边集聚系数：对于加权网其边集聚系数为：推广到更大的环：复杂网络中的集团结构边集聚系数法具体过程： 1、确定g值，根据边集聚系数的定义，计算每条边的集聚系数； 2、断开边集聚系数最小的边； 3、重新计算每条边的集聚系数； 重复2、3过程，直到每条边都被断开为止。复杂网络中的集团结构4、优化算法贪婪算法直接以最大化Q函数值为目标，探索网络中的社团。由此产生一类新的算法优化算法贪婪算法的具体步骤：(1)初始时将网络中每个顶

17、点都视为一个社团，每个社团内只有一个顶点。即如果网络中有n个顶点，则有n个社团。(2)两两合并社团，并计算社团合并所产生的Q值的变化量。选择使得Q值增加最大（或减少最小）的方式进行合并。(3)重复步骤(2)的操作，直到所有顶点被归于一个社团为止。网络的最优划分为Q函数最大值所对应的划分方式。复杂网络中的集团结构5、优化算法EO算法极值优化算法的基本思想：通过得到局部变量的极值，达到全局变量的极值。全局变量：局部变量：一个顶点对整体值的贡献标准化的局部变量，也称适合度：复杂网络中的集团结构优化算法算法的具体过程1、将网络中的点随机的分成等大的两部分，连通的部分构成社团。2、计算每个节点的适合度，

18、将适合度最低的点从一部分移动到另一部分，计算全局Q值，并重新计算每点的适合度。3、重复上述过程直到Q值最大为止。断开两部分之间的所有的边。4、对每一子部分重复1-3过程，直到Q值不能进一步提高为止。复杂网络中的集团结构6、谱分析算法主要思想：分析由连接矩阵形成的拉普拉斯矩阵(Laplacian Matrix)或标准矩阵(Normal Matrix)的特征值特征向量。以标准矩阵的分析为例所谓标准矩阵，是由网络的连接矩阵和一个对角矩阵的逆矩阵构成的。对角矩阵中的元素是每个顶点的度值，表示网络中顶点的个数。由于标准矩阵行的标准化，标准矩阵总有最大的特征值等于1，以及与之对应的特征向量（1、1、1）。

19、在对社团化明显的网络的分析中发现，如果网络自然呈现m个社团，则标准矩阵就有m-1个十分接近1的特征值，而其余的特征值则有较大的距离。最大的特征值所对应的特征向量有一个特性：在同一个社团中的顶点所对应的值较为接近。因此，特征向量中元素的值呈现阶梯状分布，并且阶梯的级数与社团的个数相匹配。复杂网络中的集团结构图 顶点0-6号为一个社团，顶点7-12号为一个社团，顶点13-18号为一个社团。图 横坐标表示顶点的编号，纵坐标表示特征向量中顶点对应的数值。可见0-6号的数值比较接近，7-12号的数值比较接近，13-18号的数值比较接近。复杂网络中的集团结构同样的方法也可以对拉普拉斯矩阵进行分析。差别在于

20、，拉普拉斯矩阵总存在平庸的特征值0，考察的标准是大于0的最小的特征值及其对应的特征向量。 复杂网络中的集团结构算法的评价以及加权网络的聚类方法复杂网络中的集团结构划分结果的比较方法正确划分率比较法共同信息比较法D函数比较法复杂网络中的集团结构准确度 （accuracy） 计算得到的集团与已知集团比较精确度 （precision） 在同一个网络上多次计算得到的多组集团间的两两比较 Ying Fan, Menghui Li, et al, Accuracy and Precision of Methods for Community Identification in Weighted Netwo

21、rks, Physica A.算法的复杂度（complexity）评价方法复杂网络中的集团结构加权网上的社团结构算法的推广权重的影响M. E. J. Newman，Phys. Rev. E. 70(2004) 056131复杂网络中的集团结构聚类算法 WGN算法基于网络拓扑结构， 边介数算法根据无权网计算边介数值(Link Betweenness) bij计算加权网中边介数值 ，即Bij= bij/wij；删除介数值最高的边； M. E. J. Newman，Phys. Rev. E. 70(2004) 056131复杂网络中的集团结构聚类算法 极值优化算法（WEO）复杂网络中的集团结构随机把网络划分为节点数相同的两个集团；把对目标函数贡献最小的节点移动到另一个集团，再计算节点的贡献；