多关系网络社团发现算法

doi:10.12068/j.issn.1005-3026.2018.10.002

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (10): 1375-1379.DOI: 10.12068/j.issn.1005-3026.2018.10.002

多关系网络社团发现算法

黄新宇，陈东明，任涛

(东北大学软件学院，辽宁沈阳110169)

收稿日期:2017-06-26 修回日期:2017-06-26 出版日期:2018-10-15 发布日期:2018-09-28
通讯作者: 黄新宇
作者简介:黄新宇(1990-)，男，辽宁凌源人，东北大学博士研究生; 陈东明(1968-)，男，安徽怀宁人，东北大学教授; 任涛(1980-)，男，辽宁沈阳人，东北大学教授.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
辽宁省自然科学基金资助项目(20170540320)；辽宁省教育厅科学研究项目(L20150167)；辽宁省博士科研启动基金资助项目(201601007).国家自然科学基金资助项目(51171041).

Community Discovery Algorithm for Multi-relationship Networks

HUANG Xin-yu， CHEN Dong-ming， REN Tao

School of Software， Northeastern University， Shenyang 110169， China.

Received:2017-06-26 Revised:2017-06-26 Online:2018-10-15 Published:2018-09-28
Contact: CHEN Dong-ming
About author:-
Supported by:
-

摘要/Abstract

摘要： 分析了真实社会网络的特性，建立了节点间多关系网络模型.在此基础上定义了节点间相互作用的影响力等概念，提出了适用于多关系网络的社团发现算法.通过理论验证了相关定义的合理性，并针对多关系网络进行了对比实验.实验结果表明:所提出的多关系网络社团发现算法与其他经典算法相比具有较高的精确度和较低的时间复杂度，具有重要的研究意义及实用价值.

关键词: 在线社会网络, 多关系网络, 社团发现, 异质网络, 重叠社团

Abstract: The characteristics of the real social network were analyzed， and a network model with multi-relationships network between nodes was established. Based on this， the concept of influence of interaction between nodes was defined， and a community discovery algorithm for multi-relationship network (CDMN) was proposed. The rationality of the presented definitions was verified theoretically， and a series of experiments compared with other algorithms were conducted. Experimental results showed that the proposed community discovery algorithm for multi-relationship networks has higher accuracy and lower time complexity than other classical algorithms， and has important research significance and practical value.

Key words: online social network, multi-relationship network, community discovery, heterogeneous network, overlapping community

中图分类号:

TP391

黄新宇，陈东明，任涛. 多关系网络社团发现算法[J]. 东北大学学报:自然科学版, 2018, 39(10): 1375-1379.

HUANG Xin-yu， CHEN Dong-ming， REN Tao. Community Discovery Algorithm for Multi-relationship Networks[J]. Journal of Northeastern University Natural Science, 2018, 39(10): 1375-1379.

参考文献

[1]Du S，Niu K，He Z，et al.Community detection analysis of heterogeneous network［C］// International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Xi′an，2015:509-512.
[2]Zhang H，Wang C D，Lai J H，et al.Modularity in complex multilayer networks with multiple aspects:a static perspective［J］.Applied Informatics，2017，4(1):1-7.
[3]Bródka P，Kazienko P.Multilayer social networks［M］.New York:Springer，2017.
[4]Xie J，Kelley S，Szymanski B K.Overlapping community detection in networks:the state-of-the-art and comparative study［J］.ACM Computing Surveys，2011，45(4):1-35.
[5]Cazabet R，Amblard F.Dynamic community detection［M］.New York:Springer，2014.
[6]李慧嘉，李爱华，李慧颖.社团结构迭代快速探测算法［J］.计算机学报，2017，40(4):970-984.(Li Hui-jia，Li Ai-hua，Li Hui-ying.Fast community detection algorithm via dynamical iteration［J］.Chinese Journal of Computers，2017，40(4):970-984.)
[7]Ai X.Node importance ranking of complex networks with entropy variation［J］.Entropy，2017，19(7):303-310.
[8]Lü L，Chen D，Ren X L，et al.Vital nodes identification in complex networks［J］.Physics Reports，2016，650:1-63.
[9]韩忠明，陈炎，刘雯，等.社会网络节点影响力分析研究［J］.软件学报，2017，28(1):84-104.(Han Zhong-ming，Chen Yan，Liu Wen，et al.Research on node influence analysis in social networks［J］.Journal of Software，2017，28(1):84-104.)
[10]Pan Y，Tan W，Chen Y.The analysis of key nodes in complex social networks［C］// Cloud Computing and Security of the Third International Conference.Nanjing，2017:829-836.
[11]Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33(4):452-473.
[12]Newman M E，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69(6):026113.
[13]SNABook.9_11_edgelist.txt［EB/OL］.(2011-08-17) ［2017-06-27］.https://github.com/maksim2042/SNABook/blob/master/chapter4/9_11_edgelist.txt.

多关系网络社团发现算法

Community Discovery Algorithm for Multi-relationship Networks

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价