南京大学学报(自然科学版) ›› 2016, Vol. 52 ›› Issue (1): 159–166.

• • 上一篇    下一篇

一种面向大规模社会网络的社区发现算法

梁晋1,2,梁吉业1,2*,赵兴旺1,2   

  • 出版日期:2016-01-27 发布日期:2016-01-27
  • 作者简介:(1. 山西大学计算机与信息技术学院,太原,030006; 2. 山西大学计算智能与中文信息处理教育部重点实验室,太原,030006)
  • 基金资助:
    基金项目:国家自然科学基金(61432011,U1435212),山西省自然科学基金(2015011048),山西省回国留学人员科研资助项目
    (2013-101)
    收稿日期:2015-06-10
    *通讯联系人,E-mail:ljy@sxu.edu.cn

A community detection algorithm for large social network

Liang Jin1,2 Liang Jiye1,2* Zhao Xingwang1,2   

  • Online:2016-01-27 Published:2016-01-27
  • About author:(1. School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, China 2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan, 030006, China)

摘要: 随着社会网络中顶点和边的逐渐增加,计算效率成为了大规模社会网络中社区发现面临的一大难题。为了更加高效地探测社会网络中隐含的社区结构,提出一种基于抽样与标签传播的社区发现算法。该算法首先利用基于度的随机游走技术对整体网络进行抽样得到子图,然后采用基于概要的社区发现算法对此子图进行社区发现,得到核心社区,最后依据已有社区结构与未抽样的节点的相似度迭代式地将社区标签传播到剩余节点。在真实社会网络数据集上,与已有算法通过实验进行了比较分析,结果表明算法能够在保证有效性的同时提高计算效率。

Abstract: Community detection aims at mining the community structures of Social Information Networks(SINs), which is the foundation of other related researches on social computing. A community (also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. Finding community structures from user data has become a hot topic in network analysis. With the rapid development of Web 2.0 and the rise of online social networks, computational efficiency of community detection in large-scale social networks has become a major problem. Although research achievements are numerous at present such as the L-M algorithm, CBCD algorithm etc, most of these achievements cannot be adopted in large-scale social networks because of the heavy computation and the decrease of accuracy. For detecting communities efficiently in various social networks, we propose a network community detection algorithm based on sampling and label propagation. In particular, the proposed algorithm firstly generates some subgraphs via random walk sampling and computes the weight of each edge, then detects communities on these subgraphs. In the end, we partition the unsampled nodes into the communities according to subgraphs’ structures. The experiments are conducted in comparison with widely used state-of-the art community detection algorithms on several real networks. The results show that the proposed algorithm can provide computational efficiency, while maintaining the effectiveness

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 金飚兵*, 冯一军, 伍瑞新. 人工电磁超材料的电磁波调控特性[J]. 南京大学学报(自然科学版), 2014, 50(3): 235 .
[2] 汪 璐,贾修一*,顾雁囡. 三支决策贝叶斯网络分类器[J]. 南京大学学报(自然科学版), 2016, 52(5): 833 .