《复杂社团结构分析.ppt》由会员分享，可在线阅读，更多相关《复杂社团结构分析.ppt（55页珍藏版）》请在金锄头文库上搜索。
1、复杂网络中的社团结构樊瑛北京师范大学系统科学系2010年7月19日纲要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 corre
2、spond 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 of the web graph con
3、sisting of the pages of a web site and their mutual hyperlinks, which are directed. Communities, indicated by the colors, were detected with the algorithm of Girvan and Newman, by neglecting the directedness of the edges.Best division of econophysicists collaboration network, with the divisions dete
4、cted 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
5、et al.l人际关系网l引文网lWWW网l新陈代谢网l食物链网 社团结构和功能之间的关系社团结构的定义社团结构的描述性定义社团结构的描述性定义Community structureCommunity structure（社团结构）（社团结构）is the groups of network vertices. Within these groups there have dense is the groups of network vertices. Within these groups there have dense internal links, but between groups
6、 there are internal links, but between groups there are fewer edgesfewer edges. . M. E. J. Newman, Detecting community structure in networks. Eur. Phys. J. B 38, 321-330 (2004). 社团结构的数学描述lClique - Complete graphlk-core - subgraph in which each node is adjacent to at least a minimum number, k, of the
7、 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个顶点 被平均分成四份
8、，构成四个社团，每个社团包含32个顶点 。每个顶点度的期望值为16，Zin表示顶点与社团内部顶点 连边数目的期望值，Zout表示顶点与社团外顶点连边数目 的期望值，从而Zin + Zout =16.lZout越小说明顶点与社团外部的连接越少，网络的社团结 构越明显； Zout越大说明网络越混乱，社团结构越不明显 。l对于Zout值大的网络还能够基本正确的对网络进行划分的 算法，在实际应用中适用范围更广，价值更大。LFR benchmarklLFR benchmark is a generalization of the GN benchmark to heterogeneous group s
9、izes 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美国大学
10、足球赛季网（115个点，616次常规赛 ）l猴子网（16个点） 已知社团结构，便于比较算法的好坏。评价函数-Modularity含义是：网络中连接社团内部顶点间的边的比例与拥有相同社团结构但是 顶点间随机连接的网络中连接社团内部顶点间的边的比例的期望值的差值 。对Q函数的质疑探测集团结构的基本方法寻找社团结构的方法l基于网络拓扑结构lGN algorithm based on edge betweenness： M. Girvan, M. E. J. Newman PNAS 99 7821(2002)lSpectral analysis； L. Donetti, M. A. Munoz J.
11、Stat. Mech. (2004) P10012l基于网络上的动力学lPotts Model；J. Reichardt, S. Bornhold, Phys Rev Lett. 93 (2004) 218701lRandom Walk：M.Latapy, P.Pons，cond-mat/0412368 ; H. Zhou PRE.67.041908lCircuits：F. Wu, B.A. Huberman, Eur. Phys. J. B 38 (2004) 331lQ函数优化lExtremal Optimization：J. Duch A. Arenas, Phys Rev E. 72
12、(2005) 02710lNewmans fast algorithm； M. E. J. Newman, Phys Rev E. 69 (2004) 066133 1、层次聚类法l根据顶点间的距离或相似程度划分网络中的社团。l具体过程为：1 定义两点间的距离或相似度，社团与社团间的距离或 相似度；2 将每个顶点视为一个社团，并根据定义计算社团间的 距离或相似度；3 将距离最近的或相似度最高的社团合并，形成新的社 团，重新计算社团间的距离或相似度；4 重复第3步操作，直到网络中的所有顶点被归入一个 社团为止。结构等价定义顶点间的相似度l结构等价：如果一个顶点与网络中其余顶点的连接方式 和另一顶
13、点与网络中其余顶点的连接方式完全相同，则 这两个顶点结构等价。例如在人际关系网中，如果两个 人的朋友完全相同，则这两个人就是结构等价的。l用欧几里德距离度量衡量结构等价。顶点i，j的距离为l此距离等于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 bio
14、logical networks, PNAS99(12)(2002)7821-7826层次聚类法l社团与社团间的距离可以采用最短距离法、最长距离法或 平均距离法。l层次距离的过程可以用树状图表示2、GN算法lGirvan和Newman提出的分裂算法已经成为探索网络社团 结构的一种经典算法，简称GN算法。 l由网络中社团的定义可知，所谓社团就是指其内部顶点的 连接稠密，而与其他社团内的顶点连接稀疏。这就意味着 社团与社团之间存在联系的通道比较少，并且要想从一个 社团到另一个社团，至少要通过这些通道中的一条。如果 能找到这些重要的通道，并将它们移除，那么网络就自然 而然的分成了各个社团。 l用最短
15、路径边介数标记每条边对连通性的重要程度。GN算法l最短路径边介数的定义为：找出每对顶点间的最短路径， 计算每条边被多少条最短路径通过，这个值就是这条边的 最短路径边介数。lGN算法的具体过程：计算网络中各条边的边介数；找出边介数最大的边，并将它移除（如果最大边介数的 边不唯一，那么既可以随机挑选一条边断开也可以将这些 边同时断开）；重新计算网络中剩余各条边的边介数；重复第、步，直到网络中所有的边都被移除。GN算法与Q值l最优社团划分的选择3、 边集聚系数法l边集聚系数：一条边的集聚系数等于网络中利 用这条边构成的三角形的个数除以利用这条边 潜在可以构成三角形的个数。l连接i，j两点的边的集聚系
16、数表示为：l连接不同社团的点的边，被较少的三角形包含 ，或者根本不包含于任何三角形。从而边集聚 系数就小。然而社团内部由于有比较稠密的边 ，所以应该包含较多的三角形，因此连接集团 内部的点的边的边集聚系数就大。边集聚系数法 修正的边集聚系数： 对于加权网其边集聚系数为： 推广到更大的环：边集聚系数法l具体过程：1、确定g值，根据边集聚系数的定义，计算 每条边的集聚系数；2、断开边集聚系数最小的边；3、重新计算每条边的集聚系数；重复2、3过程，直到每条边都被断开为止。4、优化算法贪婪算法l直接以最大化Q函数值为目标，探索网络 中的社团。由此产生一类新的算法 优化算法l贪婪算法的具体步骤： (1)初始时将网络中每个顶点都视为一个社团，每个社团内只有 一个顶点。即如果网络中有n个顶点，则有n个社团。 (2)两两合并社团，并计算社团合并所产生的Q值的变化量。选 择使得Q值增加最大（或减少最小）的方式进行合并。 (3)重复步骤(2)的操作，直到所有顶点被归于一个社团为止。 网络的最
