中文摘要 ： 大量的实证研究表明，众多真实网络同时拥有无标度和模块结构两个重要性质，因此，研究这两个重要性质对于网络上各种各样动态过程的影响显得非常重要。本文研究了一类模块化无标度网络上两个含有多个陷阱的随机游走问题。首先，推导给出了一般网络上多个陷阱问题平均首达时间的一个普适公式，这里的平均首达时间指粒子从任意非陷阱节点出发首次被陷阱点吸收的期望时间。虽然所得公式的计算复杂度很高，但通过该公式计算出的结果是精确的，而且公式的计算方法与过程与陷阱点的数目及位置无关。接着，解析计算了所研究的两个随机游走问题的平均首达时间，并得到了解析结果，且所得解析结果与通过此前导出的普适公式得到的数值结果完全一致。在所考虑的两个随机游走问题中，平均首达时间都是节点数的幂律函数，但是它们的指数并不一样。这一结果表明，陷阱的数目和位置对于平均首达时间的度量大小起着十分关键的作用。文章结尾论证了两种情形下平均首达时间度量大小不同的根本原因在于网络的模块性和无标度性。这一工作有助于加深理解带有模块结构的无标度网络上的扩散问题，同时可以促进复杂随机网络上含有多个陷阱的随机游走问题的进一步深入研究。 相关结果已在《 Physical Review E 》上发表。 文章的发表 PDF 版本： Random walks in modular scale-free networks with multiple traps.pdf
随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个社区或组构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏 。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站 ；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元 。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法 、谱平分法 、随机游走算法 和派系过滤算法 等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法 和基于边介数度量的分裂算法 等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法 、基于信息论的算法 、基于PCA的算法 和最大化模块度 的算法 等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法 ，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC) 。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。 关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章 Community Detection in graphs by Santo Fortunato (arXiv:0906.0612) 参考文献 Girvan M, Newman M E J. Community structure in social and biological networks . PNAS, 2001, 99(12): 7821-7826. Newman M E J. Fast algorithm for detecting community structure in networks . Physical Review E, 2004, 69(6): 066133. Fell D A, Wagner A. The small world of metabolism . Nature(Biotechnology, 2000, (18): 1121-1122. Pool l, Kochen M. Contacts and Influence . Social Networks, 1978, (1): 1-48. Milgram S. The small world problem . Psychology Today, 1967, (2): 60-67. Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphs . Bell System Technical Journal, 1970, 49: 291-307. Fiedler M. Algebraic connectivity of graphs . Czechoslovak Mathematical Journal, 1973, 23(98): 298-305. Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs . SIAM Journal on Matrix Analysis and Applications. 1990, 11(3): 430-452. P. Pons and M. Latapy. Computing Communities in Large Networks Using Random Walks . Computer and Information Sciences. 2005,284-293. G. Palla, I. Derenyi, I. Farkas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society . Nature,2005 435(7043): 814-818. G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modules . Phys. New. J, 2007,186. Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizations . International Conference on Communities and Technologies, 2003, 81-96. F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networks . Eur. Phys. J. B, 2004, 101: 2658-2663. Wu F, Huberman B A. Find communities in linear time: A physics approach . Euro. Phys. J B, 2003, 38: 331-338. Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks . PNAS, 2007, 104(18): 7327-7331. Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Structure in Complex Networks . Operations Research and Management Science, 2008, 17(6), 144-149. Newman M E J, Girvan M. Finding and evaluating community structure in networks . Physical Review E, 2004, 69 (2): 026113. Clauset A, Newman M E J, Moore C. Finding community structure in very large networks . Phys. Rev. E, 2004,70: 066111. Duch J, Arenas A. Community detection in complex networks using extreme optimization . Physical Review E,2005,72: 027104. R. Guimer and L. A. N. Amaral, Functional cartography of complex metabolic networks . Nature, 2005, 433: 895-900. A. Medus, G. Acua, and C. O. Dorso. Detection of community structures in networks via global optimization . Physica A, 2005, 358: 593-604. J. Reichardt and S. Bornholdt. Statistical Mechanics of Community Detection . Phys. Rev. E, 2006, 74: 016110. Newman M E J. Finding community structure in networks using the eigenvectors of matrices . Physical Review E, 2006, 74(3): 036104. P. Doreian and A. Mrvar. A Partitioning Approach to Structural Balance . Social Networks, 1996, 18(2): 149-168. Bo Yang, William K. Cheung, and Jiming Liu. Community Mining from Signed Social Networks . IEEE Transactions on Knowledge and Data Engineering. 2007, 19(10): 1333-1348.
标签: 社区结构
