复杂网络社区结构划分方法

1、复杂网络社区结构划分方法已有 3661 次阅读 2009-4-30 08:38|个人分类:科研笔记|系统分类:科研笔记|关键词：网络，系统，复杂网络，社区结构，聚类，划分方法随着对网络性质的物理意义和数学特性的深入研究，人们发现许多 实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由 若十个“社区”或“组”构成的。每个社区内部的结点间的连接相对非 常紧密，但是各个社区之间的连接相对来说却比较稀疏12。揭示网 络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如 社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文 网络中的社区代表针对同一主题的相关论文；万维网中

2、的社区就是讨论 相关主题的若干网站3；而生物化学网络或者电子电路中的网络社区 可以是某一类功能单元45。发现这些网络中的社区有助于我们更加 有效的理解和开发这些网络。在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的 网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络 （网络中边的权值为正实数）；另一类是符号社会网络，即网络中既包含 正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法 相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分 算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图 论的算法，比如K-L算法6、谱平分法78、随机游走算

3、法9和派 系过滤算法1011等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法2 和基于边介数度量的分裂算法11213 等。最近几年 从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致 可划分如下：基于电阻网络性质的算法14、基于信息论的算法15、 基于PCA的算法16和最大化模块度17的算法18-23等。对于符号 网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结 构的算法24，且 Bo Yang等提出一种基于代理的启发式划分符号网络 社区结构的算法(FEC)25。尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚 未解决的基本问题，如社区概念虽

4、然大量使用，但却缺少严格的数学定 义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明 复杂网络中社区发现的研究还需要付出大量的努力。关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009 长篇综述文章 Community Detection in graphs by SantoFortunato (arXiv:0906.0612)参考文献1Girvan M, Newman M E J. Community structure in social and biological networksJ. PNAS, 2001, 99(12): 7821-7826.2Newman M

5、 E J. Fast algorithm for detecting community structure in networksJ. Physical Review E, 2004, 69(6): 066133.Fell D A, Wagner A. The small world of metabolismJ.Nature(Biotechnology, 2000, (18): 1121-1122.Pool l, Kochen M. Contacts and InfluenceJ. Social Networks, 1978, (1): 1-48.Milgram S. The small

6、world problemJ. Psychology Today, 1967, (2): 60-67.Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphsJ. Bell System Technical Journal, 1970, 49: 291-307.Fiedler M. Algebraic connectivity of graphsJ. Czechoslovak Mathematical Journal, 1973, 23(98): 298-305.Pothen A, Simon H,

7、 Liou K P. Partitioning sparse matrices with eigenvectors of graphsJ. SIAM Journal on Matrix Analysis andApplications. 1990, 11(3): 430-452.P. Pons and M. Latapy. Computing Communities in Large Networks Using Random WalksJ. Computer and Information Sciences. 2005,284-293.G. Palla, I. Derenyi, I. Far

8、kas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and SocietyJ. Nature,2005 435(7043): 814-818.G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modulesJ. Phys. New. J, 2007,186.Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated

9、 discovery of community structure within organizationsC. International Conference on Communities and Technologies, 2003, 81-96.F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networksJ. Eur. Phys. J. B, 2004, 101: 2658-2663.Wu F, Huberman B A. Find communities i

10、n linear time: A physics approachJ. Euro. Phys. J B, 2003, 38: 331-338.Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networksJ. PNAS, 2007, 104(18): 7327-7331.Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Stru

11、cture in Complex NetworksJ. Operations Research and Management Science, 2008, 17(6), 144-149.Newman M E J, Girvan M. Finding and evaluating community structure in networksJ. Physical Review E, 2004, 69 (2): 026113.Clauset A, Newman M E J, Moore C. Finding community structure in very large networksJ.

12、 Phys. Rev. E, 2004,70: 066111.Duch J, Arenas A. Community detection in complex networks using extreme optimizationJ. Physical Review E,2005,72: 027104.R. Guimera and L. A. N. Amaral, Functional cartography of complex metabolic networksJ. Nature, 2005, 433: 895-900.A. Medus, G. Acuna, and C. O. Dors

13、o. Detection of community structures in networks via global optimizationJ. Physica A, 2005, 358: 593-604.J. Reichardt and S. Bornholdt. Statistical Mechanics of Community DetectionJ. Phys. Rev. E, 2006, 74: 016110.Newman M E J. Finding community structure in networks using the eigenvectors of matricesJ. Physical Review E, 2006, 74(3): 036104.P. Doreian and A. Mrvar. A Partitioning Approach to Structural Balan