复杂网络中的集团结构北京师范大学系统科学学院 纲要要l实际网络中的社团结构l社团结构定义l检验算法的网络与Q函数l探索社团结构的方法l算法的评价以及加权网络的聚类方法l一个具体工作（基于比较性定义下的聚类方法） 实际系系统中的社中的社团结构构 Collaboration network between scientists working at the Santa Fe Institute. The colors indicate high level communities obtained by the algorithm of Girvan and Newman and correspond quite closely to research divisions of the institute.Zachary's 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.Sle 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 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 percolation method by Palla et al. l人际关系网l引文网lWWW网l新陈代谢网l食物链网…社团结构和功能之间的关系 社社团结构的定构的定义 社团结构的描述性定义Community structureCommunity structure（社（社（社（社团结团结构）构）构）构） is the groups of network vertices. Within these groups there have dense internal links, is the groups of network vertices. Within these groups there have dense internal links, but between groups there are but between groups there are fewer edgesfewer edges. . M. E. J. Newman, Detecting community structure in networks. Eur. Phys. J. B 38, 321-330 (202X). 社社团结构的数学描述构的数学描述lClique - Complete graphlk-core - subgraph in which each node is adjacent to at least a minimum number, k, of the other nodes in the subgraph.lK-Clique CommunitylLS-SetlAn LS-set is a set of nodes such that each of its proper subsets has more ties to its complement within the set than outside. 社社团结构的比构的比较性定性定义 检验算法的网算法的网络及及Q函数函数 l人工网络lGN BenchmarklLFR benchmarkl一些实证网络（已知社团结构） 检验算法的网算法的网络 GN经典人造网典人造网l常用的人造网是由128个顶点构成的网络，这128个顶点被平均分成四份，构成四个社团，每个社团包含32个顶点。
每个顶点度的期望值为16，Zin表示顶点与社团内部顶点连边数目的期望值，Zout表示顶点与社团外顶点连边数目的期望值，从而Zin + Zout =16.lZout越小说明顶点与社团外部的连接越少，网络的社团结构越明显； Zout越大说明网络越混乱，社团结构越不明显l对于Zout值大的网络还能够基本正确的对网络进行划分的算法，在实际应用中适用范围更广，价值更大 LFR benchmarklLFR benchmark is a generalization of the GN benchmark to heterogeneous group sizes and graph degree distribution. Groups are also a priori fixed with 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. 检验算法的一些算法的一些实际网网络l空手道俱乐部网（34个点，78条边）l科学家合作网（物理学家、经济物理学、桑塔菲研究所） l美国大学足球赛季网（115个点，616次常规赛）l猴子网（16个点）…已知社团结构，便于比较算法的好坏。
评价函数价函数---Modularity含义是：网络中连接社团内部顶点间的边的比例与拥有相同社团结构但是顶点间随机连接的网络中连接社团内部顶点间的边的比例的期望值的差值对Q函数的质疑 探探测集集团结构的基本方法构的基本方法 寻找社找社团结构的方法构的方法l基于网络拓扑结构lGN algorithm based on edge betweenness： M. Girvan, M. E. J. Newman PNAS 99 7821(202X)lSpectral analysis； L. Donetti, M. A. Munoz J. Stat. Mech. (202X) P10012l基于网络上的动力学lPotts Model；J. Reichardt, S. Bornhold, Phys Rev Lett. 93 (202X) 218701lRandom Walk：, ，cond-mat/0412368 ; H. ZhoulCircuits：F. Wu, B.A. Huberman, Eur. Phys. J. B 38 (202X) 331lQ函数优化lExtremal Optimization：J. Duch A. Arenas, Phys Rev E. 72 (202X) 02710lNewman’s fast algorithm； M. E. J. Newman, Phys Rev E. 69 (202X) 066133l…… 1、、层次聚次聚类法法l根据顶点间的距离或相似程度划分网络中的社团。
l具体过程为： 1 定义两点间的距离或相似度，社团与社团间的距离或相似度； 2 将每个顶点视为一个社团，并根据定义计算社团间的距离或相似度； 3 将距离最近的或相似度最高的社团合并，形成新的社团，重新计算社团间的距离或相似度； 4 重复第3步操作，直到网络中的所有顶点被归入一个社团为止 结构等价定义顶点间的相似度l结构等价：如果一个顶点与网络中其余顶点的连接方式和另一顶点与网络中其余顶点的连接方式完全相同，则这两个顶点结构等价例如在人际关系网中，如果两个人的朋友完全相同，则这两个人就是结构等价的l用欧几里德距离度量衡量结构等价顶点i，j的距离为l此距离等于0时，两顶点结构等价 •其他距离及相似度的定义可参见 •Mika Gutafsson, Comparison and validation of community structures in complex networks. Physica A 367(202X)559-576• M. Girvan, E. Newman, Community structure in social and biological networks, PNAS99(12)(202X)7821-7826 层次聚次聚类法法l社团与社团间的距离可以采用最短距离法、最长距离法或平均距离法。
l层次距离的过程可以用树状图表示 2、、GN算法算法lGirvan和Newman提出的分裂算法已经成为探索网络社团结构的一种经典算法，简称GN算法 l由网络中社团的定义可知，所谓社团就是指其内部顶点的连接稠密，而与其他社团内的顶点连接稀疏这就意味着社团与社团之间存在联系的通道比较少，并且要想从一个社团到另一个社团，至少要通过这些通道中的一条如果能找到这些重要的通道，并将它们移除，那么网络就自然而然的分成了各个社团 l用最短路径边介数标记每条边对连通性的重要程度 GN算法算法l最短路径边介数的定义为：找出每对顶点间的最短路径，计算每条边被多少条最短路径通过，这个值就是这条边的最短路径边介数lGN算法的具体过程： ⑴计算网络中各条边的边介数； ⑵找出边介数最大的边，并将它移除（如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开）； ⑶重新计算网络中剩余各条边的边介数； ⑷重复第⑵、⑶步，直到网络中所有的边都被移除 GN算法与算法与Q值l最优社团划分的选择 3、、 边集聚系数法集聚系数法l边集聚系数：一条边的集聚系数等于网络中利用这条边构成的三角形的个数除以利用这条边潜在可以构成三角形的个数。
l连接i，j两点的边的集聚系数表示为：l连接不同社团的点的边，被较少的三角形包含，或者根本不包含于任何三角形从而边集聚系数就小然而社团内部由于有比较稠密的边，所以应该包含较多的三角形，因此连接集团内部的点的边的边集聚系数就大 边集聚系数法集聚系数法l修正的边集聚系数：l对于加权网其边集聚系数为：l推广到更大的环： 边集聚系数法集聚系数法l具体过程： 1、确定g值，根据边集聚系数的定义，计算每条边的集聚系数； 2、断开边集聚系数最小的边； 3、重新计算每条边的集聚系数； 重复2、3过程，直到每条边都被断开为止 4、、优化算法化算法——贪婪算法婪算法l直接以最大化Q函数值为目标，探索网络中的社团由此产生一类新的算法——优化算法l贪婪算法的具体步骤：(1)初始时将网络中每个顶点都视为一个社团，每个社团内只有一个顶点即如果网络中有n个顶点，则有n个社团2)两两合并社团，并计算社团合并所产生的Q值的变化量选择使得Q值增加最大（或减少最小）的方式进行合并3)重复步骤(2)的操作，直到所有顶点被归于一个社团为止网络的最优划分为Q函数最大值所对应的划分方式 5、、优化算法化算法——EO算法算法l极值优化算法的基本思想：通过得到局部变量的极值，达到全局变量的极值。
l全局变量：Ｑl局部变量：一个顶点对整体Ｑ值的贡献l标准化的局部变量，也称适合度： 优化算法化算法l算法的具体过程1、将网络中的点随机的分成等大的两部分，连通的部分构成社团2、计算每个节点的适合度，将适合度最低的点从一部分移动到另一部分，计算全局Q值，并重新计算每点的适合度3、重复上述过程直到Q值最大为止断开两部分之间的所有的边4、对每一子部分重复1-3过程，直到Q值不能进一步提高为止 6、、谱分析算法分析算法l主要思想：分析由连接矩阵形成的拉普拉斯矩阵(Laplacian Matrix)或标准矩阵(Normal Matrix)的特征值特征向量l以标准矩阵的分析为例l所谓标准矩阵，是由网络的连接矩阵和一个对角矩阵的逆矩阵构成的对角矩阵中的元素是每个顶点的度值，表示网络中顶点的个数由于标准矩阵行的标准化，标准矩阵总有最大的特征值等于1，以及与之对应的特征向量（1、1、1……）l在对社团化明显的网络的分析中发现，如果网络自然呈现m个社团，则标准矩阵就有m-1个十分接近1的特征值，而其余的特征值则有较大的距离最大的特征值所对应的特征向量有一个特性：在同一个社团中的顶点所对应的值较为接近因此，特征向量中元素的值呈现阶梯状分布，并且阶梯的级数与社团的个数相匹配。
图 顶点0-6号为一个社团，顶点7-12号为一个社团，顶点13-18号为一个社团图 横坐标表示顶点的编号，纵坐标表示特征向量中顶点对应的数值可见0-6号的数值比较接近，7-12号的数值比较接近，13-18号的数值比较接近 l同样的方法也可以对拉普拉斯矩阵进行分析差别在于，拉普拉斯矩阵总存在平庸的特征值0，考察的标准是大于0的最小的特征值及其对应的特征向量 算法的算法的评价以及加价以及加权网网络的聚的聚类方法方法 划分划分结结果的比果的比较较方法方法l正确划分率比较法l共同信息比较法lD函数比较法 l准确度 （accuracy） 计算得到的集团与已知集团比较l精确度 （precision） 在同一个网络上多次计算得到的多组集团间的两两比较 Ying Fan, Menghui Li, et al, Accuracy and Precision of Methods for Community Identification in Weighted Networks, Physica A.l算法的复杂度（complexity）评价方法价方法 加加权权网上的社网上的社团结团结构构l算法的推广l权重的影响M. E. J. Newman，Phys. Rev. E. 70(202X) 056131 聚聚类算法算法 ---WGN算法算法l基于网络拓扑结构， 边介数算法l根据无权网计算边介数值(Link Betweenness) bij计算加权网中边介数值 ，即Bij= bij/wij；l删除介数值最高的边； M. E. J. Newman，Phys. Rev. E. 70(202X) 056131 聚聚类算法算法 ---极极值优化化算法（算法（WEO）） l随机把网络划分为节点数相同的两个集团；l把对目标函数贡献最小的节点移动到另一个集团，再计算节点的贡献；l重复上面步骤，直到目标函数取得最大值为止；聚聚类算法算法 ---极极值优化算法（化算法（WEO））J. Duch and A. Arenas, Phys Rev E. 72 (202X) 027104 加加权理想网理想网络l128个节点，每32个节点假定为一个集团，共有4个集团集团内内边权的平均值集团间边权的平均值加权实际网络 一种比一种比较性定性定义下的社下的社团结构探构探测方法方法 社社团结构的原始比构的原始比较性定性定义 我我们改改进后的比后的比较性定性定义lModified Definition 划分集划分集团结构的算法构的算法l集团k对顶点i的吸引力：l初始化集团l计算任一集团对每一顶点的吸引力l将顶点移动到吸引力最大的集团中 集集团内部内部边密度密度集集团外部外部边密度密度评价指价指标：： 人工网络上的结果 The accuracy of each detected community comparedwith the counterpart of real-world communities in College football network. 附加内容附加内容 带有有overlapping的社的社团结构构lPalla I Uncovering the overlapping community structure of complex networks in nature and society 202X(7043) 。