基于多关系网络的社区检测算法

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (1): 147-154.

基于多关系网络的社区检测算法

喻金平¹, 郑杰², 朱桂祥²

1.江西理工大学工程研究院,赣州 341000;
2.江西理工大学信息工程学院,赣州 341000

收稿日期:2014-01-11 修回日期:2014-03-03 发布日期:2020-09-02
作者简介:喻金平(1964-),男,江西南昌人,硕士,教授,研究方向为数据挖掘;郑杰(1990-),男,安徽六安人,硕士,研究方向为数据挖掘、复杂网络;朱桂祥(1988-),男,江苏扬州,硕士,研究方向为社交网络、数据挖掘。
基金资助:
江西省教育厅自然科学基金资助项目(DJJ12346); 江西省研究生创新专项基金资助项目(YC2013-S198)

Community Detection Algorithm in Multi-Relational Networks

Yu Jingping¹, Zheng Jie², Zhu Guixiang²

1. School of Engineering Research Institute, Jiangxi University of Science and Technology, Ganzhou 341000, China;
2. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China

Received:2014-01-11 Revised:2014-03-03 Published:2020-09-02

摘要/Abstract

摘要： 针对传统的社区检测算法主要适用于单关系网络,忽略了多关系网络中各关系间的相互影响,不能区分出各关系对于社区检测的重要性等问题,提出一种基于节点和关系联合排名模型,能够将多关系合并为单关系的InteractRank算法。该算法在多关系网络中结合PageRank算法以及随机游走模型的思想,考虑了多关系网络中各关系内和关系间个体的联系。同时,利用谱聚类对InteractRank算法得到的单关系网络进行聚类,用于社区检测。通过UCI标准数据集上的仿真实验表明：InteractRank算法能够在多关系网络进行有效的社区检测。

关键词: 多关系网络, 社区检测, PageRank, 随机游走模型, 谱聚类

Abstract: In view of the traditional community detection algorithms being mainly applied to single relational networks, ignoring the interaction of relationship in the multi-relational networks, being unable to distinguish the importance of each relation for community detection, a novel algorithm called InteractRank was proposed. Based on the node and the relation of ranking model, the algorithm could transform multi-relational network into single relational network. Combined the PageRank algorithm and the random walk model, the algorithm considered the connection within groups and between groups in multi-relational networks. After transforming into single relational networks, spectral clustering algorithm was adopted to detect community. Through the simulation experiments on the standard UCI dataset, InteractRank indicates to be effective to community detection in multi-relational networks.

Key words: multi-relational networks, community detection, PageRank, random walk model, spectral clustering

中图分类号:

TP393

喻金平, 郑杰, 朱桂祥. 基于多关系网络的社区检测算法[J]. 系统仿真学报, 2015, 27(1): 147-154.

Yu Jingping, Zheng Jie, Zhu Guixiang. Community Detection Algorithm in Multi-Relational Networks[J]. Journal of System Simulation, 2015, 27(1): 147-154.

参考文献

[1] Watts D J, Strogatz S H.Collective dynamics of ‘small-world’ networks[J]. Nature (S0028-0836), 1998, 393(6684): 440-442.
[2] Barabási A L, Albert R.Emergence of scaling in random networks[J]. Science (S0036-8075), 1999, 286(5439): 509-512.
[3] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences (S0036-8075), 2002, 99(12): 7821-7826.
[4] Dai B T, Chua F C T, Lim E P, et al. Structural Analysis in Multi-Relational Social Networks[C]// SDM. USA: SIAM, 2012: 451-462.
[5] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bringing order to the web[M]. USA: Stanford InfoLab., 1999.
[6] 丁兆云, 周斌, 贾焰, 等. 微博中基于多关系网络的话题层次影响力分析[J]. 计算机研究与发展, 2013, 50(10): 2155-2175.
(Ding Zhaoyun, Zhou Bin, Jia Yan, et al. Topical Influence Analysis Based on the Multi-Relational Network in Microblogs[J]. Journal of Computer Research and Development, 2013, 50(10): 2155-2175.)
[7] Cai D, Shao Z, He X, et al. Mining hidden community in heterogeneous social networks[C]// Proceedings of the 3rd International Workshop on Link Discovery. USA: ACM, 2005: 58-65.
[8] Tang L, Wang X, Liu H.Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery (S1384-5810), 2012, 25(1): 1-33.
[9] 司夏萌, 刘云, 丁飞, 等. 具有社团结构的有界信任舆论涌现模型研究[J]. 系统仿真学报, 2009, 21(23): 7644-7647.
(Si Xiameng, Liu Yun, Ding Fei, et al. Research on Bounded Confidence Consensus Emergency Model with Community Structure[J]. Journal of System Simulation (S1004-731X), 2009, 21(23): 7644-7647.)
[10] 李睿琪, 唐明, 许伯铭. 多关系网络上的流行病传播动力学研究[J]. 物理学报, 2013, 62(16): 168903.
(Li Ruiqi, Tang Ming, Hui Pakming.Epidemic spreading on multi-relational networks[J] Acta Phys. Sin, 2013, 62(16): 168903.)
[11] Berlingerio M, Coscia M, Giannotti F, et al. Multidimensional networks: foundations of structural analysis[J]. World Wide Web (S1386-145X), 2013, 16(5-6): 567-593
[12] Rodriguez M A, Shinavier J.Exposing multi-relational networks to single-relational network analysis algorithms[J]. Journal of Informetrics (S1751-1577), 2010, 4(1): 29-41.
[13] 郑伟, 王朝坤, 刘璋, 等. 一种基于随机游走模型的多标签分类算法[J]. 计算机学报, 2010, 33(8): 1418-1426.
(Zheng Wei, Wang Chaokun, Liu Zhang, et al. A Multi-Label Classification Algorithm Based on Random Walk Model[J]. Chinese Journal of Computers, 2010, 33(8): 1418-1426.)