基于结构和适应度的社区发现

doi:10.3969/j.issn.0253-2778.2014.07.004

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (7): 563-569.DOI: 10.3969/j.issn.0253-2778.2014.07.004

基于结构和适应度的社区发现

高启航，景丽萍，于剑，林友芳

北京交通大学交通数据分析与挖掘北京市重点实验室，北京 100044

收稿日期:2014-03-21 修回日期:2014-06-15 接受日期:2014-06-15 出版日期:2023-05-11 发布日期:2014-06-15
通讯作者: 景丽萍
作者简介:高启航，男，1989年生，硕士生. 研究方向：数据挖掘，机器学习. E-mail: gao7hang@163.com
基金资助:
中央高校科研业务费专项基金（2014JBM029）资助.

Community detection based on structure and fitness

GAO Qihang, JING Liping, YU Jian, LIN Youfang

Beijing Key Lab of Traffic Data Analysis and Mining, Beijing Jiaotong University, Beijing 100044, China

Received:2014-03-21 Revised:2014-06-15 Accepted:2014-06-15 Online:2023-05-11 Published:2014-06-15

摘要/Abstract

摘要： 复杂社会网络无处不在，对复杂社会网络进行社区发现越来越被人们重视.基于局部结构的社区发现可以在不用了解全局的情况下对某些节点进行划分；社会网络的社区适应度特性可以找出不同适应度下的社区结构.基于局部结构以及社区适应度的网络属性，提出一种新的社区发现算法.通过实验比较，算法能较好、较快的发现社区结构，在人工网络以及真实社会网络均取得较之已有方法更好的效果.

关键词: 社区发现, 结构社区, 社区适应度, 复杂社会网络, 局部社区

Abstract: Many systems can be described as complex social networks, and increasing attention has been paid to the detection of social communities out of complex social networks. Structured-based community detection can be achieved locally without knowledge of the overall situation. The community fitness characteristics of social networks can help to identify community structures at different fitnesses. A new algorithm based on structure and fitness was proposed to test large generated networks and real networks. Experiments had shown its better efficiency and higher accuracy.

Key words: community detection, community structure, community fitness, large networks, local community

中图分类号:

TP31

高启航，景丽萍，于剑，林友芳. 基于结构和适应度的社区发现[J]. 中国科学技术大学学报, 2014, 44(7): 563-569.

GAO Qihang, JING Liping, YU Jian, LIN Youfang. Community detection based on structure and fitness[J]. Journal of University of Science and Technology of China, 2014, 44(7): 563-569.

参考文献

［1］汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用［M］. 北京:清华大学出版社, 2006.
［2］ Newman M E J. The structure and function of complex networks［J］. SIAM Review, 2003, 45(2): 167-256.
［3］ Li Y D, Liu J, Liu C L. A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks［J］. Soft Computing, 2014, 18(2): 329-348.
［4］ Bu Z, Zhang C C, Xia Z Y, et al. A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network［J］. Knowledge-Based Systems, 2013, 50: 246-259.
［5］ Shi C, Cai Y N, Fu D, et al. A link clustering based overlapping community detection algorithm［J］. Data & Knowledge Engineering, 2013, 87: 394-404.
［6］ Li K, Pang Y. A unified community detection algorithm in complex network［J］. Neurocomputing, 2014, 130(1): 36-43.
［7］ Bennetta L, Liub S S, Papageorgioub L G, et al. A mathematical programming approach to community structure detection in complex networks［C］// Proceedings of the 22nd European Symposium on Computer Aided Process Engineering. London, UK: Elsevier, 2012: 1 387-1 391.
［8］ Girvan M, Newman M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences, 2002, 99(12): 7 821-7 826.
［9］ Fortunato S. Community detection in graphs［J］. Physics Reports, 2010, 486(3): 75-174.
［10］ Wu F, Huberman B A. Finding communities in linear time: A physics approach［J］. The European Physical Journal B, 2004, 38(2): 331-338.
［11］ Newman M E J. Fast algorithm for detecting community structure in networks［J］. Physical review E, 2004, 69(6): 066133(1-5).
［12］ Zhou H J, Lipowsky R. Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities［C］//Proceedings of the International Conference on Computational Science. Springer, 2004: 1 062-1 069.
［13］ Xu X W, Yuruk N, Feng Z D, et al. SCAN: A structural clustering algorithm for networks［C］//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2007: 824-833.
［14］ Martelot E L, Hankin C. Fast multi-scale community detection based on local criteria within a multi-threaded algorithm［EB/OL］. http://arxiv.org/abs/1301.0955.
［15］ Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks［J］. New Journal of Physics, 2009, 11(3): 033015(1-18).
［16］ Serrano M , Bogu M, Vespignani A. Extracting the multiscale backbone of complex weighted networks［J］. Proceedings of the National Academy of Sciences, 2009, 106(16): 6 483-6 488.
［17］ 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(1-9).
［18］ Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks［J］. New Journal of Physics, 2009, 11(3): 033015(1-20).
［19］ Hubert L, Arabie P. Comparing partitions［J］. Journal of Classification, 1985, 2(1): 193-218.

[1]	万亮, 方文培, 王成园, 王善勇. 复杂社会网络视角下企业绿色转型的研究述评与展望——一个整合性分析框架[J]. 中国科学技术大学学报, 2020, 50(10): 1330-1342.
[2]	唐风琴，2，丁文文. 基于谱聚类带有节点特征的社区发现算法[J]. 中国科学技术大学学报, 2018, 48(2): 162-173.

基于结构和适应度的社区发现

Community detection based on structure and fitness

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价