浏览全部资源
扫码关注微信
基于局部扩展的社区发现研究现状
Research status of community detection based on local expansion
- 通信学报 2019年40卷第1期 页码：149-162
- 作者机构：
天津科技大学计算机科学与信息工程学院，天津 300457
- 作者简介：
[ "史艳翠（1982- ），女，河北保定人，博士，天津科技大学讲师，主要研究方向为移动服务计算、推荐系统、社会网络。" ]
[ "王嫄（1989- ），女，山西太原人，博士，天津科技大学讲师，主要研究方向为文本挖掘、知识图谱、推荐系统、社会网络。" ]
[ "赵青（1983- ），女，天津人，博士，天津科技大学讲师，主要研究方向为并行计算、分布式计算。" ]
[ "张贤坤（1970- ），男，安徽芜湖人，博士，天津科技大学教授，主要研究方向为语义网、案例推理、复杂网络。" ]
- 基金信息：国家自然科学基金资助项目(61402331);国家自然科学基金资助项目(61702367);国家自然科学基金资助项目(61402332);天津市教委科研计划基金资助项目(2017KJ035);天津市教委科研计划基金资助项目(2017KJ033)
DOI：10.11959/j.issn.1000-436x.2019013
中图分类号： TP391-
网络出版日期：2019-01，
纸质出版日期：2019-01-25
- 稿件说明：
移动端阅览
史艳翠, 王嫄, 赵青, 等. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019,40(1):149-162.
Yancui SHI, Yuan WANG, Qing ZHAO, et al. Research status of community detection based on local expansion[J]. Journal on communications, 2019, 40(1): 149-162.
史艳翠, 王嫄, 赵青, 等. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019,40(1):149-162. DOI： 10.11959/j.issn.1000-436x.2019013.
Yancui SHI, Yuan WANG, Qing ZHAO, et al. Research status of community detection based on local expansion[J]. Journal on communications, 2019, 40(1): 149-162. DOI： 10.11959/j.issn.1000-436x.2019013.
摘要
社区发现能有效挖掘网络的特性以及隐藏的信息。局部扩展是社区发现常用的一种方法，该方法大体上可以分为种子的选择和局部扩展两部分。因此，为了分析现有方法的优劣以及适用场合，对种子的选择、局部扩展以及评价指标等方法进行概括、比较和分析，总结了基于局部扩展的社区发现的应用以及研究难点。最后，对基于局部扩展的社区发现的研究方向进行了展望。
Abstract
Community detection can effectively mine the characteristics of the network as well as the hidden information.Local expansion is a commonly used method of community detection
and it can be divided into two steps:the selection of seeds and the local expansion.Therefore
in order to analyze the advantages and disadvantages of the existing methods and their application
these methods about the selection of seeds
local expansion and evaluation were summarized
compared and analyzed.Then
the application and the research difficulties of community detection based on local extension were summarized.Finally
the research directions of community detection based on local expansion were given.
关键词
Keywords
references
李建华 , 汪晓锋 , 吴鹏 . 基于局部优化的社区发现方法研究现状 [J ] . 中国科学院院刊 , 2015 , 30 ( 002 ): 238 - 247 .
LI J H , WANG X F , WU P . Research status of community discovery methods based on local optimization [J ] . Bulletin of Chinese Academy of Sciences , 2015 , 30 ( 002 ): 238 - 247 .
YIN H , BENSON A R , LESKOVEC J , et al . Local higher-order graph clustering [C ] // ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2017 : 555 - 564 .
ZENG J P , YU H F . A study of graph partitioning schemes for parallel graph community detection [J ] . Parallel Computing , 2016 , 58 ( C ): 131 - 139 .
SHANG C X , FENG S Z , ZHAO Z Y , et al . Efficiently detecting overlapping communities using seeding and semi-supervised learning [J ] . International Journal of Machine Learning and Cybernetics , 2017 , 8 ( 2 ): 455 - 468 .
LANCICHINETTI A , FORTUNATO S , KERTESZ J . Detecting the overlapping and hierarchical community structure in complex networks [J ] . New Journal of Physics , 2009 , 11 ( 3 ): 1 - 20 .
HUANG J B , SUN H L , LIU Y G , et al . Towards online multiresolution community detection in large-scale networks [J ] . Plos One , 2011 , 6 ( 8 ): 1 - 11 .
BAUMES J , GOLDBERG M , KRISHNAMOORTHY M , et al . Finding communities by clustering a graph into overlapping subgraphs [C ] // IADIS International Conference on Applied Computing . 2005 : 97 - 104 .
NATHAN E , ZAKRZEWSKA A , RIEDY J , et al . Local community detection in dynamic graphs using personalized centrality [J ] . Algorithms , 2017 , 10 ( 3 ): 1 - 26 .
JEUB L G S , MAHONEY M W , MUCHA P J , et al . A local perspective on community structure in multilayer networks [J ] . Network Science , 2017 , 5 ( 2 ): 144 - 163 .
BAE S H , HALPERIN D , WEST J , et al . Scalable and efficient flow-based community detection for large-scale graph analysis [J ] . ACM Transactions on Knowledge Discovery from Data , 2017 , 11 ( 3 ): 1 - 29 .
龙渊 . 基于局部扩充的重叠社区发现算法研究和改进 [D ] . 重庆:重庆大学 , 2016 .
LONG Y . Study and improvement of overlapping community discovery based on local expansion [D ] . Chongqing:Chongqing University , 2016
BAUMES J , GOLDBERG M , MAGDON-ISMAIL M . Efficient identification of overlapping communities [C ] // International Conference on Intelligence and Security Informatics . 2005 : 27 - 36 .
国琳 , 左万利 , 彭涛 . 基于隶属度的社会化网络重叠社区发现及动态集群演化分析 [J ] . 电子学报 , 2016 , 44 ( 3 ): 587 - 594 .
GUO L , ZUO W L , PENG T . Overlapping community detection and dynamic group evolution analysis based on the degree of membership in social network [J ] . ACTA Electronica Sinica , 2016 , 44 ( 3 ): 587 - 594 .
YANG J X , ZHANG X D . Finding overlapping communities using seed set [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2017 , 467 : 96 - 106 .
陈俊宇 , 周刚 , 南煜 , 等 . 一种半监督的局部扩展式重叠社区发现方法 [J ] . 计算机研究与发展 , 2016 , 53 ( 6 ): 1376 - 1388 .
CHEN J Y , ZHOU G , NAN Y , et al . Semi-supervised local expansion method for overlapping community detection [J ] . Journal of Computer Research and Development , 2016 , 53 ( 6 ): 1376 - 1388 .
WHANG J J , GLEICH D F , DHILLON I S . Overlapping community detection using neighborhood-inflated seed expansion [J ] . IEEE Transactions on Knowledge and Data Engineering , 2016 , 28 ( 5 ): 1272 - 1284 .
杨贵 , 郑文萍 , 王文剑 , 等 . 一种加权稠密子图社区发现算法 [J ] . 软件学报 , 2017 , 28 ( 11 ): 3103 - 3114 .
YANG G , ZHENG W P , WANG W J , et al . Community detection algorithm based on weighted dense subgraphs [J ] . Journal of Software , 2017 , 28 ( 11 ): 3103 - 3114 .
CAO J P , WANG S Z , WANG H . Detecting communities on topic of transportation with sparse crowd annotations [J ] . IEEE Transactions on Intelligent Transportation Systems , 2017 , 18 ( 4 ): 1017 - 1022 .
CHEN Q , WU T T , FANG M . Detecting local community structures in complex networks based on local;degree central nodes [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2013 , 392 ( 3 ): 529 - 537 .
DESHPANDE P , RAVINDRAN B . MCEIL:An improved scoring function for overlapping community detection using seed expansion methods [C ] // IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining . 2017 : 652 - 659 .
GLEICH D F , SESHADHRI C . Vertex neighborhoods,low conductance cuts,and good seeds for local community methods [C ] // 18th ACM SIGKDD international conference on Knowledge discovery and data mining . 2012 : 597 - 605 .
WANG X F , LIU G S , LI J H , et al . Locating structural centers:a density-based clustering method for community detection [J ] . Plos One , 2017 , 12 ( 1 ): 1 - 23 .
SU Y S , WANG B J , ZHANG X Y . A seed-expanding method based on random walks for community detection in networks with ambiguous community structures [J ] . Scientific Reports , 2017 , 7 : 1 - 10 .
汪涛 , 刘阳 , 席耀一 . 一种基于核心节点跳转的局部社区发现算法 [J ] . 上海交通大学学报 , 2015 , 49 ( 12 ): 1809 - 1816 .
WANG T , LIU Y , XI Y Y . Detection of local community structure of complex networks based on core nodes jumping [J ] . Journal of Shanghai Jiaotong University , 2015 , 49 ( 12 ): 1809 - 1816 .
常振超 , 陈鸿昶 , 黄瑞阳 , 等 . 采用影响力节点集扩展的局部社团检测 [J ] . 西安交通大学学报 , 2016 , 50 ( 4 ): 41 - 47 .
CHANG Z C , CHEN H C , HUANG R Y , et al . A local community detection method using expansion of influential nodes set [J ] . Journal of Xian Jiaotong University , 2016 , 50 ( 4 ): 41 - 47 .
LEE C , REID F , MCDAID A , et al . Detecting highly overlapping community structure by greedy clique expansion [C ] // 4th International Workshop on Social Network Mining and Analysis (SNA-KDD) . 2010 .
SHANG M S , CHEN D B , ZHOU T . Detecting overlapping communities based on community cores in complex networks [J ] . Chinese Physics Letters , 2010 , 27 ( 5 ): 1 - 4 .
李婕 , 王兴伟 , 郭静 , 等 . 面向移动通信网络的局部扩张群组构造方法 [J ] . 东北大学学报(自然科学版) , 2017 , 38 ( 12 ): 1691 - 1695 .
LI J , WANG X W , GUO J , et al . Clique percolation based local fitness method for user clustering in telecommunication network [J ] . Journal of Northeastern University , 2017 , 38 ( 12 ): 1691 - 1695 .
KUMAR P , GUPTA S , BHASKER B . An upper approximation based community detection algorithm for complex networks [J ] . Decision Support Systems , 2017 , 96 : 103 - 118 .
BECKER E , ROBISSON B , CHAPPLE C E , et al . Multifunctional proteins revealed by overlapping clustering in protein interaction network [J ] . Bioinformatics , 2011 , 28 ( 1 ): 84 - 90 .
肖觅 , 孟祥武 , 史艳翠 . 一种基于移动用户行为的回路融合社区发现算法 [J ] . 电子与信息学报 , 2012 , 34 ( 10 ): 2369 - 2374 .
XIAO M , MENG X W , SHI Y C . A circuits merging community discovery algorithm based on mobile user behaviors [J ] . Journal of Electronics ＆ Information Technology , 2012 , 34 ( 10 ): 2369 - 2374 .
WILDER B , IMMORLICA N , RICE E , et al . Influence maximization with an unknown network by exploiting community structure [C ] // The 3rd International Workshop on Social Influence Analysis . 2017 : 2 - 7 .
ZHOU Y , SUN G B , XING Y , et al . Local community detection algorithm based on minimal cluster [J ] . Applied Computational Intelligence and Soft Computing , 2016 , 2016 ( 2 ): 1 - 11 .
张忠正 . 基于核心区域扩展的重叠社区发现算法研究 [D ] . 北京:北京理工大学 , 2016 .
ZHANG Z Z . Overlapping community detection based on core region expansion [D ] . Beijing:Beijing Institute of Technology , 2016
黄立威 , 李彩萍 , 张海粟 , 等 . 一种基于因子图模型的半监督社区发现方法 [J ] . 自动化学报 , 2016 , 42 ( 10 ): 1520 - 1531 .
HUANG L W , LI C P , ZHANG H L , et al . A semi-supervised community detection method based on factor graph model [J ] . ACTA Automatica Sinica , 2016 , 42 ( 10 ): 1520 - 1531 .
徐建民 , 李腾飞 , 吴树芳 . 一种基于用户交互行为的微博社区发现方法 [J ] . 河北大学学报 (自然科学版) , 2016 , 36 ( 2 ): 189 - 196 .
XU J M , LI T F , WU S F . A micro-blogging community discovery method based on user’s interactions [J ] . Journal of Heibei University (Natural Science Edition) , 2016 , 36 ( 2 ): 189 - 196 .
NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks [J ] . Physical review E , 2004 , 69 ( 2 ): 1 - 16 .
陈晶 , 万云 . 社交网络中基于模块度最大化的标签传播算法的研究 [J ] . 通信学报 , 2017 , 38 ( 2 ): 25 - 33 .
CHEN J , WAN Y . Research on label propagation algorithm based on modularity maximization in the social network [J ] . Journal on Communications , 2017 , 38 ( 2 ): 25 - 33 .
邓琨 , 李文平 , 余法红 , 等 . 基于多核心标签传播的复杂网络重叠社区识别方法 [J ] . 通信学报 , 2017 , 38 ( 2 ): 53 - 66 .
DENG K , LI W P , YU F H , et al . Overlapping community detection in complex networks based on multi kernel label propagation [J ] . Journal on Communications , 2017 , 38 ( 2 ): 25 - 33 .
陈羽中 , 施松 , 朱伟平 , 等 . 一种基于邻域跟随关系的增量社区发现算法 [J ] . 计算机学报 , 2017 , 40 ( 3 ): 570 - 583 .
CHEN Y Z , SHI S , ZHU W P , et al . An incremental community discovery algorithm based on neighborhood following relationship [J ] . Chinese Journal of Computers , 2017 , 40 ( 3 ): 570 - 583 .
LIAKOS P , NTOULAS A , DELIS A . Scalable link community detection:a local dispersion-aware approach [C ] // 2016 IEEE International Conference on Big Data (Big Data) . 2016 : 716 - 725 .
LI L , FAN K , ZHANG Z , et al . Community detection algorithm based on local expansion k-means [J ] . Neural Network World , 2016 , 26 ( 6 ): 589 - 605 .
WEN X Y , CHEN W N , LIN Y , et al . A maximal clique based multiobjective evolutionary algorithm for overlapping community detection [J ] . IEEE Transactions on Evolutionary Computation , 2017 , 21 ( 3 ): 363 - 377 .
郭弘毅 , 刘功申 , 苏波 , 等 . 融合社区结构和兴趣聚类的协同过滤推荐算法 [J ] . 计算机研究与发展 , 2016 , 53 ( 8 ): 1664 - 1672 .
GUO H Y , LIU G S , SU B , et al . Collaborative filtering recommendation algorithm combining community structure and interest clusters [J ] . Journal of Computer Research and Development , 2016 , 53 ( 8 ): 1664 - 1672 .
刘宇 , 吴斌 , 曾雪琳 , 等 . 一种基于社交网络社区的组推荐框架 [J ] . 电子与信息学报 , 2016 , 38 ( 9 ): 2150 - 2157 .
LIU Y , WU B , ZENG X L , et al . A group recommendation framework based on social network community [J ] . Journal of Electronics ＆ Information Technology , 2016 , 38 ( 9 ): 2150 - 2157 .
BOUCHARD M , WESTLAKE B G . Community detection in online criminal networks and its implications for research co-offending (forthcoming) [M ] . Analysis of Criminal Networks . Montreal : The University Press , 2017 .
丁晟春 , 王楠 , 吴靓婵媛 . 基于关键词共现和社区发现的微博热点主题识别研究 [J ] . 现代情报 , 2018 , 38 ( 3 ): 10 - 18 .
DING S C , WANG N , WU J C Y . Hot topic detection of Weibo based on keyword co-occurrence and community discovery [J ] . Journal of Modern Information , 2018 , 38 ( 3 ): 10 - 18 .
HOSHI M , TACHIMORI Y . Evaluation of community detection of the networks derived from clinical information and its application to patient classification [J ] . Japan Journal of Medical Informatics , 2014 , 34 ( 1 ): 3 - 15 .
MALL R , ULLAH E , KUNJI K , et al . An adaptive refinement for community detection methods for disease module identification in biological networks using novel metric based on connectivity,conductance ＆ modularity [C ] // IEEE International Conference on Bioinformatics and Biomedicine . 2017 : 2282 - 2284 .
HARENBERG S , SEAY R G , RANSHOUS S , et al . Memory-efficient query-driven community detection with application to complex disease associations [J ] . SDM , 2016 , 15 ( 1 ): 65 - 79 .
GARCIA J O , ASHOURVAN A , MULDOON S F , et al . Applications of community detection techniques to brain graphs:algorithmic considerations and implications for neural function [J ] . Proceedings of the IEEE , 2018 , 106 ( 5 ): 846 - 867 .
吴哲 . 基于局部社区发现的微信朋友圈信息流广告推荐算法研究 [D ] . 浙江:浙江工商大学 , 2016 .
WU Z . Local method for WeChat friendship flow advertisement recommendation algorithm [D ] . Zhejiang:Zhejiang Gongshang University , 2016 .
胡旭 . 基于微博平台企业舆情影响力最大化研究 [D ] . 天津：天津大学 , 2017 .
HU X . Influence maximization of enterprise public opinion based on Weibo platform [D ] . Tianjin:Tianjin University , 2017 .
李国良 , 楚娅萍 , 冯建华 , 等 . 多社交网络的影响力最大化分析 [J ] . 计算机学报 , 2016 , 39 ( 4 ): 643 - 656 .
LI G L , CHU Y P , FENG J H , et al . Influence maximization on multiple social networks [J ] . Chinese Journal of Computers , 2016 , 39 ( 4 ): 643 - 656 .
马茜 , 马军 . 在影响力最大化问题中寻找种子节点的替补节点 [J ] . 计算机学报 , 2017 , 40 ( 3 ): 674 - 686 .
MA Q , MA J . Discovering the substitute for the seeds in influence maximization problem [J ] . Chinese Journal of Computers , 2017 , 40 ( 3 ): 674 - 686 .
TONG G M , WU W L , TANG S J , et al . Adaptive influence maximization in dynamic social networks [J ] . IEEE/ACM Transactions on Networking , 2017 , 25 ( 1 ): 112 - 125 .
INTERDONATO R , TAGARELLI A . Personalized recommendation of Points-of-Interest based on multilayer local community detection [C ] // International Conference on Social Informatics . 2017 : 552 - 571 .
史艳翠 , 杨巨成 , 陈亚瑞 , 等 . 基于移动数据的用户间影响力计算方法 [J ] . 华中科技大学学报(自然科学版) , 2017 , 45 ( 7 ): 110 - 114 .
SHI Y C , YANG J C , CHEN Y R , et al . Calculation method of influence between users based on mobile data [J ] . Journal of Huazhong University of Science ＆ Technology (Natural Science Edition) , 2017 , 45 ( 7 ): 110 - 114 .
0
浏览量
1760
下载量
0
CSCD
- 网络PDF下载
- XML下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
AI问答
鸿云智能
中文
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
- 总访问量：151733 今日访问量：2