基于节点多关系的社团挖掘算法及其应用

doi:10.11772/j.issn.1001-9081.2022081218

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (5): 1489-1496.DOI: 10.11772/j.issn.1001-9081.2022081218

基于节点多关系的社团挖掘算法及其应用

周琳¹^,²^,³, 肖玉芝¹^,²^,³(), 刘鹏¹^,²^,³, 秦有鹏¹^,²^,³

^1.青海师范大学计算机学院, 西宁 810016
^2.青海省藏文信息处理与机器翻译重点实验室(青海师范大学), 西宁 810008
^3.藏文信息处理教育部重点实验室(青海师范大学), 西宁 810008

收稿日期:2022-07-19 修回日期:2022-09-15 接受日期:2022-09-23 发布日期:2023-05-08 出版日期:2023-05-10
通讯作者: 肖玉芝
作者简介:周琳（1997—），女，辽宁大连人，硕士研究生，主要研究方向：社团划分
肖玉芝（1980—），女，青海西宁人，教授，博士，CCF会员，主要研究方向：复杂网络理论、数据挖掘、网络舆情分析 qh_xiaoyuzhi@139.com
刘鹏（1995—），男，山西定襄人，硕士研究生，主要研究方向：大数据分析
秦有鹏（1995—），男，甘肃古浪人，硕士研究生，主要研究方向：传播动力学。
基金资助:
国家自然科学基金资助项目(61763041);青海省重点研发计划项目(2020?GX?112)

Community mining algorithm based on multi-relationship of nodes and its application

Lin ZHOU¹^,²^,³, Yuzhi XIAO¹^,²^,³(), Peng LIU¹^,²^,³, Youpeng QIN¹^,²^,³

^1.Computer College，Qinghai Normal University，Xining Qinghai 810016，China
^2.Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province （Qinghai Normal University），Xining Qinghai 810008，China
^3.Key Laboratory of Tibetan Information Processing，Ministry of Education （Qinghai Normal University），Xining Qinghai 810008，China

Received:2022-07-19 Revised:2022-09-15 Accepted:2022-09-23 Online:2023-05-08 Published:2023-05-10
Contact: Yuzhi XIAO
About author:ZHOU Lin， born in 1997， M. S. candidate. Her research interests include community division.
XIAO Yuzhi， born in 1980， Ph. D.， professor. Her research interests include complex network theory， data mining， internet public opinion analysis.
LIU Peng， born in 1995， M. S. candidate. His research interests include big data analytics.
QIN Youpeng， born in 1995， M. S. candidate. His research interests include spread dynamics.
Supported by:
National Natural Science Foundation of China(61763041);Key Research and Development Program of Qinghai Province(2020-GX-112)

摘要/Abstract

摘要：

为度量多关系节点相似性、挖掘具有多关系节点的社团结构，提出基于节点多关系的社团挖掘算法LSL-GN。首先基于节点相似性和节点可达性刻画具有多关系的节点相似性度量指标LHN-ISL；然后利用该指标重构目标网络的低密度模型，并结合GN（Girvan-Newman）算法完成社团划分。将LSL-GN算法与多个经典社团挖掘算法在模块度（Q）、标准化互信息（NMI）和调整兰德指数（ARI）上进行对比，结果显示LSL-GN算法在3个指标上均优于经典算法，说明它的社团划分质量相对较好。将LSL-GN应用于“用户-应用”的移动漫游网络模型中，划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构，而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。

关键词: 社团挖掘, 社团划分, 社团检测, 复杂网络, 移动漫游网络, 节点相似性, 节点可达性

Abstract:

In order to measure the similarity of multi-relational nodes and mine the community structure with multi-relational nodes， a community mining algorithm based on multi-relationship of nodes， called LSL-GN， was proposed. Firstly， based on node similarity and node reachability， LHN-ISL， a similarity measurement index for multi-relational nodes， was described to reconstruct the low-density model of the target network， and the community division was completed by combining with GN （Girvan-Newman） algorithm. The LSL-GN algorithm was compared with several classical community mining algorithms on Modularity （Q value）， Normalized Mutual Information （NMI） and Adjusted Rand Index （ARI）. The results show that LSL-GN algorithm achieves the best results in terms of three indexes， indicating that the community division quality of LSL-GN is better. The “User-Application” mobile roaming network model was divided by LSL-GN algorithm into community structures based on basic applications such as Ctrip， Amap and Didi Travel. These results of community division can provide strategic reference information for designing personalized package services.

Key words: community mining, community division, community detection, complex network, mobile roaming network, node similarity, node reachability

中图分类号:

TP311.3

周琳, 肖玉芝, 刘鹏, 秦有鹏. 基于节点多关系的社团挖掘算法及其应用[J]. 计算机应用, 2023, 43(5): 1489-1496.

Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application[J]. Journal of Computer Applications, 2023, 43(5): 1489-1496.

图/表 16

图1 多关系节点网络示例

Fig. 1 Example of multi-relational node network

图2 网络G0的拓扑结构

Fig. 2 Topology of network G0

图3 节点相似度示意图

Fig. 3 Schematic diagram of node similarity

图4 网络G1划分前后的拓扑结构

Fig. 4 Topology of network G1 before and after division

表1 网络基本信息

Tab. 1 Basic network information

网络	节点数	边数	网络密度	平均路径长度	平均聚类系数
Karate	34	78	0.139	2.408	0.588
Football	115	616	0.094	2.508	0.403
Adjnoun	110	425	0.068	2.536	0.190

图6 Football网络结构

Fig. 6 Football network structure

图7 Football网络划分后的结构

Fig. 7 Football network structure after division

图8 不同划分数下的模块度

Fig. 8 Modularity under different division number

表2 模块度Q、NMI和ARI的对比

Tab. 2 Comparison of Q， NMI and ARI

网络	GN				LSL-GN				Louvain
网络	Q	NMI	ARI	K	Q	NMI	ARI	K	Q	NMI	ARI	K
Karate	0.401 298	0.485 141	0.391 572	5	0.509 467	0.592 526	0.483 075	4	0.415 598	0.497 679	0.429 290	4
Football	0.599 629	0.878 889	0.778 102	10	0.788 884	0.891 017	0.820 503	10	0.604 407	0.884 961	0.806 940	10
Adjnoun	0.080 537	0.052 425	0.000 379	69	0.366 693	0.104 703	0.003 308	25	0.292 772	0.008 634	-0.006 999	6

图9 移动漫游网络模型示例

Fig. 9 Mobile roaming network model example

表3 用户信息

Tab. 3 User information

用户 ID	是否出差	出行时长/d	通话时长/min	使用流量/MB
用户 ID	是否出差	出行时长/d	通话时长/min	出行类应用	通信类应用	视频类应用
用户1	是	5	70	去哪儿（28）、滴滴出行（51）	QQ（124）、微信（316）	抖音（6 144）、优酷（1 935）、爱奇艺（315）、芒果TV（284）
用户2	是	11	286	携程旅行（13）、去哪儿（8）、途牛旅行（0.5）	微信（738）、旺信（265）	快手（8 127）、火山小视频（2 006）
用户3	是	3	69	高德地图（33）、铁路12306（2）	QQ（342）、微信（227）、钉钉（85）	抖音（3 148）、腾讯（2 147）、微视（826）
用户4	否	61	793		微信（2 144）	抖音（21 507）、快手（13 321）、腾讯（10 163）

表4 通话等级设置

Tab. 4 Call level setting

通话等级	标准化结果范围
高于平均通话时长	$85 ≤ a i$
高于但接近平均通话时长	$50 ≤ a i < 85$
低于但接近平均通话时长	$25 ≤ a i < 50$
低于平均通话时长	$a i < 25$

表4 通话等级设置

Tab. 4 Call level setting

通话等级	标准化结果范围
高于平均通话时长	$85 ≤ a i$
高于但接近平均通话时长	$50 ≤ a i < 85$
低于但接近平均通话时长	$25 ≤ a i < 50$
低于平均通话时长	$a i < 25$

图10 移动漫游网络的拓扑结构

Fig. 10 Topology of mobile roaming network

表5 不同社团挖掘算法在移动漫游网络上的划分结果对比

Tab. 5 Division results comparison of different community mining algorithms on mobile roaming network

算法	Q	K
LSL-GN	0.514	4
Louvain	0.494	3
GN	0.472	38

表6 LSL-GN算法的社团划分结果

Tab. 6 Community division results of LSL-GN algorithm

社团	应用平台
1	携程旅行、QQ、钉钉、Bilibili、快手等
2	高德地图、易信、腾讯视频、爱奇艺等
3	去哪儿、优酷、凤凰电视、咪咕视频等
4	铁路12306、滴滴出行、微信、抖音、火山小视频等

图11 LSL-GN算法的社团划分结果

Fig. 11 Community division result of LSL-GN algorithm

参考文献 24

1	汪小帆，李翔，陈关荣. 复杂网络理论及其应用［M］. 北京：清华大学出版社， 2006：162-191.
	WANG X F， LI X， CHEN G R. Complex Network Theory and its Application［M］. Beijing： Tsinghua University Press， 2006： 162-191.
2	DONATH W E， HOFFMAN A J. Lower bounds for the partitioning of graphs［J］. IBM Journal of Research and Development， 1973， 17（5）： 420-425. 10.1147/rd.175.0420
3	MOUDEN Z A EL， JAKIMI A， HAJAR M. Unsupervised graph clustering for community detection in complex networks using spectral analysis［J］. International Journal of Multimedia Intelligence and Security， 2020， 3（4）： 337-347. 10.1504/ijmis.2020.114775
4	SUN H L， DU H X， HUANG J B， et al. Detecting semantic-based communities in node-attributed graphs［J］. Computational Intelligence， 2018， 34（4）： 1199-1222. 10.1111/coin.12178
5	ZHANG H Y， LIN L M， XU L， et al. Graph partition based privacy-preserving scheme in social networks［J］. Journal of Network and Computer Applications， 2021， 195： No.103214. 10.1016/j.jnca.2021.103214
6	DŽAMIĆ D， ALOISE D， MLADENOVIĆ N. Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization［J］. Annals of Operations Research， 2019， 272（1/2）： 273-287. 10.1007/s10479-017-2553-9
7	FENG S S， ZHANG H X， CAO J， et al. Merging user social network into the random walk model for better group recommendation［J］. Applied Intelligence， 2019， 49（6）： 2046-2058. 10.1007/s10489-018-1375-z
8	GIRVAN M， NEWMAN M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826. 10.1073/pnas.122653799
9	吴卫江，桑睿彤，郑艺峰. 基于限制性随机游走局部谱近似社区发现算法［J］. 计算机工程与设计， 2021， 42（9）：2472-2477. 10.16208/j.issn1000-7024.2021.09.010
	WU W J， SANG R T， ZHENG Y F. Local spectrum approximation algorithm with limited random walk for community detection［J］. Computer Engineering and Design， 2021， 42（9）： 2472-2477. 10.16208/j.issn1000-7024.2021.09.010
10	LI W， XIE J， XIN M， et al. An overlapping network community partition algorithm based on semi-supervised matrix factorization and random walk［J］. Expert Systems with Applications， 2018， 91： 277-285. 10.1016/j.eswa.2017.09.007
11	CHENG J J， ZHANG W B， YANG H J， et al. A seed-expanding method based on TOPSIS for community detection in complex networks［J］. Complex， 2020， 2020： No.9017239. 10.1155/2020/9017239
12	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）： No.e0169355. 10.1371/journal.pone.0169355
13	MA Y L， ZHAO Y K， WANG J W， et al. Modularity-based incremental label propagation algorithm for community detection［J］. Applied Sciences， 2020， 10（12）： No.4060. 10.3390/app10124060
14	WEISS R， VÉLEZ B， SHELDON M A. HyPursuit： a hierarchical network search engine that exploits content-link hypertext clustering［C］// Proceedings of the 7th ACM Conference on Hypertext. New York： ACM， 1996： 180-193. 10.1145/234828.234846
15	黄新宇，陈东明，任涛.多关系网络社团发现算法［J］.东北大学学报（自然科学版），2018，39（10）：1375-1379.
	HUANG X Y， CHEN D M， REN T. Community discovery algorithm for multi-relationship networks［J］. Journal of Northeastern University （Natural Science）， 2018， 39（10）： 1375-1379.
16	邱少明，於涛，杜秀丽，等.基于节点多属性相似性聚类的社团划分算法［J］. 计算机工程， 2020， 46（7）：84-90， 97. 10.19678/j.issn.1000-3428.0055070
	QIU S M， YU T， DU X L， et al. Community division algorithm based on similarity clustering of node multiple attribute［J］. Computer Engineering， 2020， 46（7）： 84-90， 97. 10.19678/j.issn.1000-3428.0055070
17	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， 2008（10）： No.P10008. 10.1088/1742-5468/2008/10/p10008
18	NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review E， 2004， 69（2）：026113. 10.1103/physreve.69.026113
19	DANON L， DÍAZ-GUILERA A， DUCH J， et al. Comparing community structure identification［J］. Journal of Statistical Mechanics： Theory and Experiment， 2005， 2005（9）： No.P09008. 10.1088/1742-5468/2005/09/p09008
20	HUBERT L， ARABIE P. Comparing partitions［J］. Journal of Classification， 1985， 2（1）： 193-218. 10.1007/bf01908075
21	郭世泽，陆哲明. 复杂网络基础理论［M］. 北京：科学出版社， 2012：29-33.
	GUO S Z， LU Z M. Basic Theory of Complex Networks［M］. Beijing： Science Press， 2012： 29-33.
22	NEWMAN M E J. Clustering and preferential attachment in growing networks［J］. Physical Review E， 2001， 64（2）： No.025102. 10.1103/physreve.64.025102
23	LEICHT E A， HOLME P， NEWMAN M E J. Vertex similarity in networks［J］. Physical Review E， 2006， 73（2）： No.026120. 10.1103/physreve.73.026120
24	乔虹，田玉玲，马建芬. 基于多属性融合策略的复杂网络社团划分算法［J］. 科学技术与工程， 2018， 18（32）： 51-57. 10.3969/j.issn.1671-1815.2018.32.009
	QIAO H， TIAN Y L， MA J F. Community detection algorithm based on multi-attribute fusion strategy［J］. Science Technology and Engineering， 2018， 18（32）： 51-57. 10.3969/j.issn.1671-1815.2018.32.009

[1]	李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
[2]	李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 104-110.
[3]	孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2823-2829.
[4]	郝志刚, 秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1178-1185.
[5]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[6]	陈广福, 王海波, 连雁平. 基于高阶自包含协同过滤的有向网络链路预测[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3060-3068.
[7]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[8]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[9]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[10]	陈献, 胡丽莹, 林晓炜, 陈黎飞. 基于核非负矩阵分解的有向图聚类算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3447-3454.
[11]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[12]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[13]	刘昱阳, 李龙杰, 单娜, 陈晓云. 融合聚集系数的链接预测方法[J]. 计算机应用, 2020, 40(1): 28-35.
[14]	王西龙, 王继成, 罗成, 田秀霞. 时间尺度与选择倾向性协同作用下的演化博弈模型[J]. 计算机应用, 2019, 39(6): 1824-1828.
[15]	张希, 朱利, 刘路辉, 詹杭龙, 卢艳民. 基于多层网络的银行间市场信用拆借智能风险传染机制[J]. 计算机应用, 2019, 39(5): 1507-1511.

基于节点多关系的社团挖掘算法及其应用

Community mining algorithm based on multi-relationship of nodes and its application

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 24

相关文章 15

编辑推荐

Metrics