并行社区发现算法的可扩展性研究

刘强; 贾焰; 方滨兴; 周斌; 胡玥; 黄九鸣

doi:10.11959/j.issn.1000-436x.2018052

您当前的位置：

首页 >

文章列表页 >

并行社区发现算法的可扩展性研究

学术论文 | 更新时间：2024-06-05

- 并行社区发现算法的可扩展性研究
- Research on the scalability of parallel community detection algorithms
- 通信学报 2018年39卷第4期页码：13-20
- 作者机构：
  
  1. 国防科技大学计算机学院，湖南长沙 410073
  2. 北京邮电大学计算机学院，北京 100876
- 作者简介：
  
  [ "刘强（1981-），男，江苏句容人，国防科技大学博士生，主要研究方向为社交网络分析、数据挖掘、复杂网络等。" ]
  [ "贾焰（1960-），女，四川成都人，国防科技大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。" ]
  [ "方滨兴（1960-），男，江西万年人，中国工程院院士，北京邮电大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。" ]
  [ "周斌（1971-），男，江西南昌人，国防科技大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。" ]
  [ "胡玥（1993-），女，陕西宝鸡人，国防科技大学硕士生，主要研究方向为社交网络分析。" ]
  [ "黄九鸣（1981-），男，福建安溪人，国防科技大学讲师，主要研究方向为社交网络分析、信息安全等。" ]
- 基金信息：
  
  国家重点研发计划基金资助项目(2017YFB0803303);国家自然科学基金资助项目(61502517);国家自然科学基金资助项目(61472438)
- DOI：10.11959/j.issn.1000-436x.2018052
  中图分类号： TP311
- 网络出版日期：2018-04，
  
  纸质出版日期：2018-04-25
- 稿件说明：
移动端阅览
刘强, 贾焰, 方滨兴, 等. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018,39(4):13-20.

Qiang LIU, Yan JIA, Binxing FANG, et al. Research on the scalability of parallel community detection algorithms[J]. Journal on communications, 2018, 39(4): 13-20.
刘强, 贾焰, 方滨兴, 等. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018,39(4):13-20. DOI： 10.11959/j.issn.1000-436x.2018052.

Qiang LIU, Yan JIA, Binxing FANG, et al. Research on the scalability of parallel community detection algorithms[J]. Journal on communications, 2018, 39(4): 13-20. DOI： 10.11959/j.issn.1000-436x.2018052.

摘要

社交网络中往往蕴含着大量用户和群体信息，如话题演化模式、群体聚集效应以及信息传播规律等，对这些信息的挖掘成为社交网络分析的重要任务。社交网络的群体聚集效应作为社交网络的一种特征模式，表现为社交网络的社区结构特性。社区结构的发现已成为其他社交网络分析任务的基础和关键。随着在线社交网络用户数量的急剧增长，传统的社区发现手段已经难以适应，从而催生了并行社区发现技术的发展。对当前主流并行社区发现方法Louvain算法和标签传播算法在超大规模数据集上的可扩展性进行了研究，指出了各自的优缺点，为后续应用提供参考。

Abstract

The social network often contains a large amount of information about users and groups

such as topic evolution mode

group aggregation effect

the law of information dissemination and so on.The mining of these information has become an important task for social network analysis.As one characteristic of the social network

the group aggregation effect is characterized by the community structure of the social network.The discovery of community structure has become the basis and key point of other social network analysis tasks.With the rapid growth of the number of online social network users

the traditional community detection methods have been difficult to be used

which contributes to the development of parallel community detection technology.The current mainstream parallel community detection methods

including Louvain algorithm and label propagation algorithm

were tested in the large-scale data sets

and corresponding advantages and disadvantages were pointed out so as to provide useful information for later applications.

关键词

Keywords

references

李建华 , 汪晓锋 , 吴鹏 . 基于局部优化的社区发现方法研究现状 [J ] . 中国科学院院刊 , 2015 , 30 ( 2 ): 238 - 247 .

LI J H , WANG X F , WU P . Review on community detection methods based on local optimization [J ] . Bulletin of Chinese Academy of Sciences , 2015 , 30 ( 2 ): 238 - 247 .

CORNEIL D G , GOTLIEB C C . An efficient algorithm for graph isomorphism [J ] . Journal of the ACM , 1970 , 17 ( 1 ): 51 - 64 .

NEWMAN M E J . Fast algorithm for detecting community structure in networks [J ] . Physical Review E , 2004 , 69 ( 6 ):066133.

NEWMAN M E J , . Modularity and community structure in networks [C ] // The National Academy of Sciences of the United States of America . 2006 : 8577 - 8582 .

ROSVALL M , BERGSTROM C T . Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems [J ] . Plos One , 2011 , 6 ( 4 ):e18209.

NEWMAN M E J . Spectral methods for community detection and graph partitioning [J ] . Physical Review E , 2013 , 88 ( 4 ):042822.

RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks [J ] . Physical Review E , 2007 , 76 ( 3 ):036106.

赵卓翔 , 王轶彤 , 田家堂 , 等 . 社会网络中基于标签传播的社区发现新算法 [J ] . 计算机研究与发展 , 2011 , 48 ( S3 ): 8 - 15 .

ZHAO Z X , WANG Y T , TIAN J T , et al . A novel algorithm for community discovery in social networks based on label propagation [J ] . Journal of Computer Research and Development , 2011 , 48 ( S3 ): 8 - 15 .

刘世超 , 朱福喜 , 甘琳 . 基于标签传播概率的重叠社区发现算法 [J ] . 计算机学报 , 2016 , 39 ( 4 ): 717 - 729 .

LIU S C , ZHU F X , GAN L . A label-propagation-probability-based algorithm for overlapping community detection [J ] . Chinese Journal of Computers , 2016 , 39 ( 4 ): 717 - 729 .

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.

LIU Q , LIU C , WANG J , et al . Evolutionary link community structure discovery in dynamic weighted networks [J ] . Physica A:Statistical Mechanics and its Applications , 2017 , 466 : 370 - 388 .

FARKAS I , ÁBEL D , PALLA G . Weighted network modules [J ] . New Journal of Physics , 2007 , 9 ( 6 ):180.

高学东 , 王立敏 , 马红权 , 等 . 基于共享最近邻探测社团结构的算法 [J ] . 系统工程理论与实践 , 2009 , 29 ( 10 ): 102 - 109 .

GAO X D , WANG L M , MA H Q , et al . Detecting community structure based on shared nearest neighbor [J ] . Systems Engineering Theory and Practice , 2009 , 29 ( 10 ): 102 - 109 .

刘文远 , 王佳楠 , 王林 . 基于局部扩张查询的重叠社区发现 [J ] . 小型微型计算机系统 , 2015 , 36 ( 10 ): 2229 - 2234 .

LIU W Y , WANG J N , WANG L . Community detection based on local expansion query [J ] . Journal of Chinese Computer Systems , 2015 , 36 ( 10 ): 2229 - 2234 .

WICKRAMAARACHCHI C , FRINCU M , SMALL P , et al . Fast parallel algorithm for unfolding of communities in large graphs [C ] // 2014 IEEE High Performance Extreme Computing Conference (HPEC) . 2014 : 1 - 6 .

乔少杰 , 郭俊 , 韩楠 , 等 . 大规模复杂网络社区并行发现算法 [J ] . 计算机学报 , 2017 , 40 ( 3 ): 687 - 700 .

QIAO S J , GUO J , HAN N , et al . Parallel algorithm for discovering communities in large-scale complex networks [J ] . Chinese Journal of Computers , 2017 , 40 ( 3 ): 687 - 700 .

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2008 ( 10 ):P10008.

STAUDT C L , MEYERHENKE H . Engineering parallel algorithms for community detection in massive networks [J ] . IEEE Transactions on Parallel and Distributed Systems , 2016 , 27 ( 1 ): 171 - 184 .

LU H , HALAPPANAVAR M , KALYANARAMAN A . Parallel heuristics for scalable community detection [J ] . Parallel Computing , 2015 , 47 : 19 - 37 .

AKSHAY U B . Scalable community detection using label propagation and map-reduce [R ] . 2012 .

从玉相 . 基于MapReduce的社区挖掘算法 [D ] . 上海:上海交通大学 , 2013 .

CONG Y X . Community detection based on MapReduce [D ] . Shanghai:Shanghai Jiao Tong University , 2013 .

ZHANG Q , QIU Q , GUO W , et al . A social community detection algorithm based on parallel grey label propagation [J ] . Computer Networks , 2016 , 107 : 133 - 143 .

BAE S H , HOWE B . GossipMap:a distributed community detection algorithm for billion-edge directed graphs [C ] // The International Conference for High Performance Computing,Networking,Storage and Analysis . 2015 : 1 - 12 .

李春英 , 汤庸 , 林海 , 等 . 基于标签传播的可并行复杂网络重叠社区发现算法 [J ] . 中国科学:信息科学 , 2016 , 2 : 212 - 227 .

LI C Y , TANG Y , LIN H , et al . Parallel overlapping community detection algorithm in complex network based on label propagation [J ] . Science China Information Sciences , 2016 , 2 : 212 - 227 .

PENG C , ZHANG Z , WONG K C , et al . A scalable community detection algorithm for large graphs using stochastic block models [C ] // The 24th International Joint Conference on Artificial Intelligence . 2015 : 2090 - 2096 .

YANG J , LESKOVEC J . Defining and evaluating network communities based on ground-truth [J ] . Knowledge and Information Systems , 2012 , 42 ( 1 ): 181 - 213 .

KWAK H , LEE C , PARK H , et al . What is Twitter,a social network or a news media? [C ] // The 19th International Conference on World Wide Web . 2010 : 591 - 600 .

LEUNG I X Y , HUI P , LIO P , et al . Towards real-time community detection in large networks [J ] . Physical Review E , 2009 , 79 ( 6 ):066107.

浏览量

1811

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向学位/学历证书可信管理的可扩展类PBFT算法

支持多模态网络的可扩展异构服务功能链并行编排部署系统

基于APG合并及拓扑势优化的启发式用户关联策略

基于局部扩展的社区发现研究现状

软件定义网络可扩展性研究综述