|
|
- 2016
基于多重特征向量的有向网络社团结构划分算法
|
Abstract:
有向网络社团结构的识别对于理解复杂系统的结构特性和动力学特性都有着重要的意义。提出了一种基于拉普拉斯矩阵多重特征向量的有向网络社团结构划分算法，该算法利用有向网络拉普拉斯矩阵的前c个较小特征值所对应的特征向量来划分有向网络的社团结构。在人工数据和实证数据上与模块度的谱优化算法和模拟退火算法做了对比实验。实验结果表明，当社团结构明显时，该算法的归一化互信息指标的值接近于1。当社团结构不明显时，该算法所取得的效果也优于谱优化和模拟退火算法。与这两种算法相比，在实证网络上模块度Q值也可以提高17.28%和19.21%。该文工作对于理解有向网络上拉普拉斯矩阵的多重特征向量与网络的社团结构的关系具有十分重要的意义。
| [1] | ONNELA J P, SARAM？KI J, HYV？NEN J, et al. Structure and tie strengths in mobile communication networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(18):7332-7336. |
| [2] | GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826. |
| [3] | GONG X, LI K, Li M, et al. A spectral algorithm of community identification[J]. EPL (Europhysics Letters), 2013, 101(4):48001. |
| [4] | KRZAKALA F, MOORE C, MOSSEL E, et al. Spectral redemption in clustering sparse networks[J]. Proceedings of the National Academy of Sciences, 2013, 110(52):20935-20940. |
| [5] | VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4):395-416. |
| [6] | CHUNG F. Laplacians and the Cheeger inequality for directed graphs[J]. Annals of Combinatorics, 2005, 9(1):1-19. |
| [7] | GLEICH D. Hierarchical directed spectral graph partitioning[R]. California:Stanford University, 2006. |
| [8] | LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1):016118. |
| [9] | 狄增如. 系统科学视角下的复杂网络研究[J]. 上海理工大学学报, 2011, 33(2):111-116. DI Zeng-ru. Research of complex networks from the view point of systems science[J]. Journal of University of Shanghai for Science and Technology, 2011, 33(2):111-116. |
| [10] | NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2):026113. |
| [11] | FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3):75-174. |
| [12] | ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4):1118-1123. |
| [13] | CHENG X Q, SHEN H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2010, 2010(04):P04024. |
| [14] | NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23):8577-8582. |
| [15] | BAUER F. Normalized graph Laplacians for directed graphs[J]. Linear Algebra and its Applications, 2012, 436(11):4193-4222. |
| [16] | BARABáSI A L, OLTVAI Z N. Network biology:Understanding the cell's functional organization[J]. Nature Reviews Genetics, 2004, 5(2):101-113. |
| [17] | PAN Y, LI D H, LIU J G, et al. Detecting community structure in complex networks via node similarity[J]. Physica A:Statistical Mechanics and Its Applications, 2010, 389(14):2849-2857. |
| [18] | 宣照国, 苗静, 党延忠, 等. 科研领域关联网络的社团结构分析[J]. 上海理工大学学报, 2008, 30(3):249-252. XUAN Zhao-guo, MIAO Jing, DANG Yan-zhong, et al. Community structure of Chinese nature science basic research weighted networks[J]. Journal of University of Shanghai for Science and Technology, 2008, 30(3):249-252. |
| [19] | 邵凤, 郭强, 曾诗奇, 等. 微博系统网络结构的研究进展[J]. 电子科技大学学报, 2014, 43(2):174-183. SHAO Feng, GUO Qiang, ZENG Shi-qi, et al. Research progress of the microblog system structures[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2):174-183. |
| [20] | LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. Physical Review Letters, 2008, 100(11):118703. |
| [21] | NEWMAN M E J. Spectral methods for community detection and graph partitioning[J]. Physical Review E, 2013, 88(4):042822. |
| [22] | WANG X, QIAN B, DAVIDSON I. On constrained spectral clustering and its applications[J]. Data Mining and Knowledge Discovery, 2014, 28(1):1-30. |
| [23] | CHAUHAN S, GIRVAN M, OTT E. Spectral properties of networks with community structure[J]. Physical Review E, 2009, 80(5):056114. |
| [24] | ARENAS A, DíAZ-GUILERA A, PéREZ-VICENTE C J. Synchronization reveals topological scales in complex networks[J]. Physical Review Letters, 2006, 96(11):114102. |
| [25] | SHEN H W, CHENG X Q. Spectral methods for the detection of network community structure:a comparative analysis[J]. Journal of Statistical Mechanics:Theory and Experiment, 2010(10):P10020. |
| [26] | GUIMERA R, AMARAL L A N. Cartography of complex networks:Modules and universal roles[J]. Journal of Statistical Mechanics:Theory and Experiment, 2005(2):P02001. |
| [27] | PONS P, LATAPY M. Computing communities in large networks using random walks[J]. J Graph Algorithms Appl, 2006, 10(2):191-218. |
| [28] | LOVáSZ L. Random walks on graphs:a survey[J]. Combinatorics, Paul Erdos is Eighty, 1993, 2(1):1-46. |
| [29] | LANCICHINETTI A, FORTUNATO S. Community detection algorithms:a comparative analysis[J]. Physical Review E, 2009, 80(5):056117. |
| [30] | DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics:Theory and Experiment, 2005(9):P09008. |
| [31] | PALLA G, BARABáSI A L, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136):664-667. |
| [32] | 刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013, 62(17):178901. LIU Jian-guo, REN Zhuo-ming, GUO Qiang, et al. Node importance ranking of complex networks[J]. Acta Phys Sin, 2013, 62(17):178901. |
| [33] | MALLIAROS F D, VAZIRGIANNIS M. Clustering and community detection in directed networks:a survey[J]. Physics Reports, 2013, 533(4):95-142. |
| [34] | NEWMAN M E J, LEICHT E A. Mixture models and exploratory analysis in networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(23):9564-9569. |
| [35] | COLEMAN J S. Introduction to mathematical sociology[M]. London:Free Press Glencoe, 1964. |
| [36] | TANG L, LI S, LIN J. Community structure detection based on the neighbor node degree information[J]. Int J Mod Phys C, 2015, 27(4):1650046. |
