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
2、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 of the web g
3、raph 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 division
4、s 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
5、Palla et al.l 人际关系网l 引文网l WWW网l 新陈代谢网l 食物链网社团结构和功能之间的关系社团结构的定义社团结构的描述性定义社团结构的描述性定义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 community structure in network
6、s. Eur. Phys. J. B 38, 321-330 (2004). 社团结构的数学描述l Clique - Complete graphl k-core - subgraph in which each node is adjacent to at least a minimum number, k, of the other nodes in the subgraph.l K-Clique Communityl LS-Setl An 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.
