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

复杂网络社区结构划分方法已有 3661 次阅读 2009-4-30 08:38 |个人分类:科研笔记|系统分类:科研笔记|关键词:网络，系统，复杂网络，社区结构，聚类，划分方法 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏12。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站3；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元45。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法6、谱平分法78、随机游走算法9和派系过滤算法1011等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法2和基于边介数度量的分裂算法11213等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法14、基于信息论的算法15、基于PCA的算法16和最大化模块度17的算法18-23等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法24，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC)25。尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章 Community Detection in graphs by Santo Fortunato (arXiv:0906.0612)参考文献1 Girvan M, Newman M E J. Community structure in social and biological networksJ. PNAS, 2001, 99(12): 7821-7826.2 Newman M E J. Fast algorithm for detecting community structure in networksJ. Physical Review E, 2004, 69(6): 066133.3 Fell D A, Wagner A. The small world of metabolismJ. Nature(Biotechnology, 2000, (18): 1121-1122.4 Pool l, Kochen M. Contacts and InfluenceJ. Social Networks, 1978, (1): 1-48.5 Milgram S. The small world problemJ. Psychology Today, 1967, (2): 60-67.6 Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphsJ. Bell System Technical Journal, 1970, 49: 291-307.7 Fiedler M. Algebraic connectivity of graphsJ. Czechoslovak Mathematical Journal, 1973, 23(98): 298-305.8 Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphsJ. SIAM Journal on Matrix Analysis and Applications. 1990, 11(3): 430-452.9 P. Pons and M. Latapy. Computing Communities in Large Networks Using Random WalksJ. Computer and Information Sciences. 2005,284-293.10G. Palla, I. Derenyi, I. Farkas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and SocietyJ. Nature,2005 435(7043): 814-818.11G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modulesJ. Phys. New. J, 2007,186.12Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizationsC. International Conference on Communities and Technologies, 2003, 81-96.13F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networksJ. Eur. Phys. J. B, 2004, 101: 2658-2663.14Wu F, Huberman B A. Find communities in linear time: A physics approachJ. Euro. Phys. J B, 2003, 38: 331-338.15Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networksJ. PNAS, 2007, 104(18): 7327-7331.16Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Structure in Complex NetworksJ. Operations Research and Management Science, 2008, 17(6), 144-149.17Newman M E J, Girvan M. Finding and evaluating community structure in networksJ. Physical Review E, 2004, 69 (2): 026113.18Clauset A, Newman M E J, Moore C. Finding community structure in very large networksJ. Phys. Rev. E, 2004,70: 066111.19Duch J, Arenas A. Community detection in complex networks using extreme optimizationJ. Physical Review E,2005,72: 027104.20R. Guimer and L. A. N. Amaral, Functional cartography of complex metabolic networksJ. Nature, 2005, 433: 895-900.21A. Medus, G. Acua, and C. O. Dorso. Detection of community structures in networks via global optimizationJ. Physica A, 2005, 358: 593-604.22J. Reichardt and S. Bornholdt. Statistical Mechanics of Community DetectionJ. Phys. Rev. E, 2006, 74: 016110.23Newman M E J. Finding community structure in networks using the eigenvectors of matricesJ. Physical Review E, 2006, 74(3): 036104.24P. Doreian and A. Mrvar. A Partitioning Approach to Structural Balanc