博文

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

已有 17001 次阅读 2009-4-30 08:38 |个人分类:科研笔记|系统分类:科研笔记| 复杂网络, 网络, 系统, 聚类, 社区结构

随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏[1][2]。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站[3]；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元[4][5]。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。

在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法[6]、谱平分法[7][8]、随机游走算法[9]和派系过滤算法[10][11]等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法[2]和基于边介数度量的分裂算法[1][12][13]等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法[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 networks[J]. PNAS, 2001, 99(12): 7821-7826.

[2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.

[3] Fell D A, Wagner A. The small world of metabolism[J]. Nature(Biotechnology, 2000, (18): 1121-1122.

[4] Pool l, Kochen M. Contacts and Influence[J]. Social Networks, 1978, (1): 1-48.

[5] Milgram S. The small world problem[J]. Psychology Today, 1967, (2): 60-67.

[6] Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphs[J]. Bell System Technical Journal, 1970, 49: 291-307.

[7] Fiedler M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal, 1973, 23(98): 298-305.

[8] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. 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 Walks[J]. Computer and Information Sciences. 2005,284-293.

[10]G. Palla, I. Derenyi, I. Farkas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J]. Nature,2005 435(7043): 814-818.

[11]G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modules[J]. Phys. New. J, 2007,186.

[12]Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizations[C]. International Conference on Communities and Technologies, 2003, 81-96.

[13]F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networks[J]. Eur. Phys. J. B, 2004, 101: 2658-2663.

[14]Wu F, Huberman B A. Find communities in linear time: A physics approach[J]. Euro. Phys. J B, 2003, 38: 331-338.

[15]Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J]. PNAS, 2007, 104(18): 7327-7331.

[16]Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Structure in Complex Networks[J]. Operations Research and Management Science, 2008, 17(6), 144-149.

[17]Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69 (2): 026113.

[18]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004,70: 066111.

[19]Duch J, Arenas A. Community detection in complex networks using extreme optimization[J]. Physical Review E,2005,72: 027104.

[20]R. Guimerà and L. A. N. Amaral, Functional cartography of complex metabolic networks[J]. Nature, 2005, 433: 895-900.

[21]A. Medus, G. Acuña, and C. O. Dorso. Detection of community structures in networks via global optimization[J]. Physica A, 2005, 358: 593-604.

[22]J. Reichardt and S. Bornholdt. Statistical Mechanics of Community Detection[J]. Phys. Rev. E, 2006, 74: 016110.