南京大学学报(自然科学版) ›› 2016, Vol. 52 ›› Issue (1): 159166.
梁晋1,2,梁吉业1,2*,赵兴旺1,2
Liang Jin1,2 Liang Jiye1,2* Zhao Xingwang1,2
摘要: 随着社会网络中顶点和边的逐渐增加,计算效率成为了大规模社会网络中社区发现面临的一大难题。为了更加高效地探测社会网络中隐含的社区结构,提出一种基于抽样与标签传播的社区发现算法。该算法首先利用基于度的随机游走技术对整体网络进行抽样得到子图,然后采用基于概要的社区发现算法对此子图进行社区发现,得到核心社区,最后依据已有社区结构与未抽样的节点的相似度迭代式地将社区标签传播到剩余节点。在真实社会网络数据集上,与已有算法通过实验进行了比较分析,结果表明算法能够在保证有效性的同时提高计算效率。
[1] Zhao Y, Levina E, Zhu J. Community extraction for social networks. Proceedings of the National Academy of Sciences, 2011, 108(18): 7321-7326. [2] Serrano M ?, Bogu?á M, Sagués F. Uncovering the hidden geometry behind metabolic networks. Molecular Biosystems, 2012, 8(3): 843-850. [3] 杨博, 刘大有, . 复杂网络聚类方法. 软件学报, 2009, 20(1): 54-66. [4] 金弟, 刘大有, 杨博等. 基于局部探测的快速复杂网络聚类算法. 电子学报, 2011, 39(11): 2540-2546. [5] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452. [6] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826. [7] Reichardt J, Bornholdt S. Detecting fuzzy community structures in complex networks with a Potts model. Physical Review Letters, 2004, 93(21): 218-701. [8] Reichardt J, Bornholdt S. Statistical mechanics of community detection. Physical Review E, 2006, 74(1): 016-110. [9] Wu F, Huberman B A. Finding communities in linear time: A physics approach. The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2): 331-338. [10] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066-133. [11] Boettcher S, Percus A G. Optimization with extremal dynamics. Complexity, 2002, 8(2): 57-62. [12] Zhou T, Bai W J, Cheng L J, et al. Continuous extremal optimization for Lennard-Jones clusters. Physical Review E, 2005, 72(1): 016-702. [13] 柴变芳, 赵晓鹏, 贾彩燕,等. 大规模网络的三角形模体社区发现模型. 南京大学学报 (自然科学), 2014, 50(4): 466-473. [14] Kudelka M, Zehnalova S, Platos J. Network sampling based on NN representatives. arXiv preprint arXiv:1402.1661, 2014. [15] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 895-900. [16] Newman M E J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582. [17] Lü Z, Huang W. Iterated tabu search for identifying community structure in complex networks. Physical Review E, 2009, 80(2): 026130. [18] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints. Physical Review E, 2009, 80(2): 026129. [19] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications, 2010, 389(7): 1493-1500. [20] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008. [21] Gleich D F, Seshadhri C. Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2012: 597-605. [22] 张新猛, 蒋盛益. 基于核心图增量聚类的复杂网络划分算法. 自动化学报, 2013, 39(7): 1117-1125. [23] Leskovec J, Kleinberg J, Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 2. [24] Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: Densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York: ACM Press, 2005: 177-187. |
No related articles found! |
|