Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (5): 1489-1496.DOI: 10.11772/j.issn.1001-9081.2022081218
Special Issue: 数据科学与技术
• Data science and technology • Previous Articles Next Articles
Lin ZHOU1,2,3, Yuzhi XIAO1,2,3(), Peng LIU1,2,3, Youpeng QIN1,2,3
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.Supported by:
周琳1,2,3, 肖玉芝1,2,3(), 刘鹏1,2,3, 秦有鹏1,2,3
通讯作者:
肖玉芝
作者简介:
周琳(1997—),女,辽宁大连人,硕士研究生,主要研究方向:社团划分基金资助:
CLC Number:
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.
周琳, 肖玉芝, 刘鹏, 秦有鹏. 基于节点多关系的社团挖掘算法及其应用[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1489-1496.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022081218
网络 | 节点数 | 边数 | 网络密度 | 平均路径长度 | 平均聚类系数 |
---|---|---|---|---|---|
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 |
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 |
网络 | 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 |
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 |
用户 ID | 是否 出差 | 出行 时长/d | 通话时 长/min | 使用流量/MB | ||
---|---|---|---|---|---|---|
出行类应用 | 通信类应用 | 视频类应用 | ||||
用户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) |
Tab. 3 User information
用户 ID | 是否 出差 | 出行 时长/d | 通话时 长/min | 使用流量/MB | ||
---|---|---|---|---|---|---|
出行类应用 | 通信类应用 | 视频类应用 | ||||
用户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) |
通话等级 | 标准化结果范围 |
---|---|
高于平均通话时长 | |
高于但接近平均通话时长 | |
低于但接近平均通话时长 | |
低于平均通话时长 |
Tab. 4 Call level setting
通话等级 | 标准化结果范围 |
---|---|
高于平均通话时长 | |
高于但接近平均通话时长 | |
低于但接近平均通话时长 | |
低于平均通话时长 |
算法 | Q | K |
---|---|---|
LSL-GN | 0.514 | 4 |
Louvain | 0.494 | 3 |
GN | 0.472 | 38 |
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 |
社团 | 应用平台 |
---|---|
1 | 携程旅行、QQ、钉钉、Bilibili、快手等 |
2 | 高德地图、易信、腾讯视频、爱奇艺等 |
3 | 去哪儿、优酷、凤凰电视、咪咕视频等 |
4 | 铁路12306、滴滴出行、微信、抖音、火山小视频等 |
Tab. 6 Community division results of LSL-GN algorithm
社团 | 应用平台 |
---|---|
1 | 携程旅行、QQ、钉钉、Bilibili、快手等 |
2 | 高德地图、易信、腾讯视频、爱奇艺等 |
3 | 去哪儿、优酷、凤凰电视、咪咕视频等 |
4 | 铁路12306、滴滴出行、微信、抖音、火山小视频等 |
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] | Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861. |
[2] | Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402. |
[3] | Zhongyu WANG, Xiaodong QIAN. Optimization of edge connection rules for supply chain network based on improved expectation maximization algorithm [J]. Journal of Computer Applications, 2024, 44(11): 3386-3395. |
[4] | Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539. |
[5] | Peng LI, Shilin WANG, Guangwu CHEN, Guanghui YAN. Key node mining in complex network based on improved local structural entropy [J]. Journal of Computer Applications, 2023, 43(4): 1109-1114. |
[6] | Xiangxi WEN, Yating PENG, Kexin BI, Yuming HENG, Minggong WU. Situation prediction of flight conflict network based on online fuzzy least squares support vector machine with optimal training set [J]. Journal of Computer Applications, 2023, 43(11): 3632-3640. |
[7] | Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance [J]. Journal of Computer Applications, 2023, 43(11): 3457-3463. |
[8] | LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110. |
[9] | Yuyu MENG, Jing GUO. Link prediction algorithm based on information entropy improved PCA model [J]. Journal of Computer Applications, 2022, 42(9): 2823-2829. |
[10] | Zhigang HAO, Li QIN. Method for discovering important nodes in food safety standard reference network based on multi-attribute comprehensive evaluation [J]. Journal of Computer Applications, 2022, 42(4): 1178-1185. |
[11] | Jun HU, Zhengkang XU, Li LIU, Fujin ZHONG. Network embedding method based on multi-granularity community information [J]. Journal of Computer Applications, 2022, 42(3): 663-670. |
[12] | Guangfu CHEN, Haibo WANG, Yanping LIAN. Link prediction in directed network based on high-order self-included collaborative filtering [J]. Journal of Computer Applications, 2022, 42(10): 3060-3068. |
[13] | Yang LI, Anbiao WU, Ye YUAN, Linlin ZHAO, Guoren WANG. Unsupervised attributed graph embedding model based on node similarity [J]. Journal of Computer Applications, 2022, 42(1): 1-8. |
[14] | CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577. |
[15] | LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||