计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (6): 128-134.doi: 10.11896/jsjkx.231000142

• 数据库&大数据&数据科学 • 上一篇    下一篇

模体感知的自适应跨层游走社区检测

王贝贝1, 信俊昌2, 陈金义1, 王之琼3   

  1. 1 东北大学计算机科学与工程学院 沈阳 110819
    2 辽宁省大数据管理与分析重点实验室 沈阳 110819
    3 东北大学医学与生物信息工程学院 沈阳 110819
  • 收稿日期:2023-10-20 修回日期:2024-04-02 出版日期:2024-06-15 发布日期:2024-06-05
  • 通讯作者: 信俊昌(xinjunchang@mail.neu.edu.cn)
  • 作者简介:(wangbeibei@mail.neu.edu.cn)
  • 基金资助:
    国家重点研发计划(2021YFB3300900);国家自然科学基金(62072089);中央高校基本科研业务费专项资金(N2116016)

Motif-aware Adaptive Cross-layer Random Walk Community Detection

WANG Beibei1, XIN Junchang2, CHEN Jinyi1, WANG Zhiqiong3   

  1. 1 School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China
    2 Key Laboratory of Big Data Management and Analytics(Liaoning Province),Shenyang 110819,China
    3 College of Medicine and Biological Information Engineering,Northeastern University,Shenyang 110819,China
  • Received:2023-10-20 Revised:2024-04-02 Online:2024-06-15 Published:2024-06-05
  • About author:WANG Beibei,born in 1998,postgra-duate.Her main research interests include social network analysis and so on.
    XIN Junchang,born in 1977,Ph.D,professor,Ph.D supervisor,is a member of CCF(No.48169S).His main research interests include blockchain technology,medical informatics and big data management and analytics.
  • Supported by:
    National Key Research and Development Program of China(2021YFB3300900),National Natural Science Foundation of China(62072089) and Fundamental Research Funds for the Central Universities of Ministry of Education of China(N2116016).

PDF (PC)

548

摘要： 近年来,利用高阶交互信息进行多层网络社区检测已成为复杂网络分析领域的研究热点。尽管多层网络社区检测的研究已取得了一些进展,但大多数方法忽略了网络各层之间的联系。为了解决这一问题,提出了一种模体(motif)感知的自适应跨层游走社区检测算法(Motif-aware Adaptive Cross-Layer random walk Community Detection,MACLCD)。该算法充分考虑了多层网络各层内的高阶交互特性以及层间的相关性,有效整合了多层网络的结构信息,提高了社区检测结果的准确性。具体地,首先从网络和节点的角度进行综合度量,揭示网络层间相关性;其次,考虑了各层网络可能具有不同的局部和全局结构特征,利用motif识别各层网络特有的高阶交互结构,构建多层加权混合阶网络;进一步,设计了多层网络跨层游走模型,并引入跳转因子,以确保随机游走能够自适应地遍历多层网络,从而捕获更丰富的网络结构信息。在4个真实的网络数据集上进行实验比较分析,结果表明MACLCD算法在社区检测方面性能较优,相比目前表现最佳的对比算法在ACC和NMI上分别提高了10%和8.9%。

关键词: 社区检测, 多层网络, 高阶结构, 跨层随机游走, motif

Abstract: In recent years,multi-layer network community detection using high order interactive information has become a hot spot.In order to solve this problem,a MACLCD algorithm is proposed.The algorithm considers high order interaction and interlayer correlation in multi-layer network to improve the accuracy of community detection.Specifically,firstly,the inter-layer correlation is revealed through comprehensive measurement from the perspective of network and node.Secondly,considering that each layer network may have different local and global structural characteristics,motif is used to identify the unique high-order interaction structure of each layer network,and a multi-layer weighted hybrid order network is constructed.Furthermore,a cross-layer walking model is designed,and a jump factor is introduced to ensure that the random walk can traverse the multi-layer network adaptively,so as to capture more diverse network structural information.Experimental comparisons are conducted on four real-world network datasets,and the results demonstrate that the MACLCD algorithm outperforms the comparison algorithms in terms of community detection performance.

Key words: Community detection, Multi-layer networks, High-order structure, Cross-layer random walk, motif

中图分类号: 

  • TP391
[1]MANSOUREH N,HOSSEIN F Z M,SUSAN B.A Multilayer General Type-2 Fuzzy Community Detection Model in Large-Scale Social Networks[J].IEEE Transactions on Fuzzy Systems,2022,30(10):4494-4503.
[2]WEN X,ZHANG D.A Multi-Layer Random Walk Method for Local Dynamic Community Detection in Brain Functional Network[C]//BIBM.2021:1098-1103.
[3]YU L,XIA M,AN Q.A network embedding framework based on integrating multiplex network for drug combination prediction[J].Briefings in bioinformatics,2022,23(1):bbab364.
[4]JIN D,YU Z,JIAO P,et al.A survey of community detection approaches:From statistical modeling to deep learning[J].IEEE Transactions on Knowledge and Data Engineering,2021,35(2):1149-1170.
[5]CHEN S,LIU S,MA Z.Global and individualized community detection in inhomogeneous multilayer networks[J].The Annals of Statistics,2022,50(5):2664-2693.
[6]QIU Z,WU J,HU W,et al.Temporal Link Prediction with Motifs for Social Networks[J].IEEE Transactions on Knowledge and Data Engineering,2021,35(3):3145-3158.
[7]LI C,TANG Y,TANG Z,et al.Motif-based embedding labelpropagation algorithm for community detection[J].Interna-tional Journal of Intelligent Systems,2022,37(3):1880-1902.
[8]CHEN K J,CHEN L M,WU T.Survey on Community Detection in Multi-layer Networks[J].Journal of Frontiers of Computer Science and Technology,2020,14(11):1801-1812.
[9]LI C,GUO X,LIN W,et al.Multiplex network community detection algorithm based on motif awareness[J].Knowledge-Based Systems,2023,260:110136.
[10]CHEN Y,MO D.Community detection for multilayer weighted networks[J].Information Sciences,2022,595:119-141.
[11]LV L,HU P,BARDOU D,et al.Community Detection in Multilayer Networks via Semi-supervised Joint Symmetric Nonnegative Matrix Factorization[J].IEEE Transactions on Network Science and Engineering,2022,10(3):1623-1635.
[12]LI B,WANG M,HOPCROFT J E,et al.HoSIM:Higher-order Structural Importance based method for multiple local community detection[J].Knowledge-Based Systems,2022,256:109853.
[13]GAO Y,ZHANG H,YU X.Higher-Order Community Detection:On Information Degeneration and Its Elimination[J].IEEE/ACM Transactions on Networking,2022,31(2):891-903.
[14]HUANG L,WANG C D,PHILIP S Y.Higher order connection enhanced community detection in adversarial multiview networks[J].IEEE Transactions on Cybernetics,2021,53(5):3060-3074.
[15]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online lear-ning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2014:701-710.
[16]GROVER A,LESKOVEC J.node2vec:Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.2016:855-864.
[17]ROSSI L,MAGNANI M.Towards effective visual analytics on multiplex and multilayer networks[J].Chaos Solitons & Fractals,2015,72:68-76.
[18]NIE F,TIAN L,LI X.Multiview clustering via adaptivelyweighted procrustes[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2018:2022-2030.
[19]XU P,DENG Z,CHOI K S,et al.Multi-view information-theoretic co-clustering for co-occurrence data[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2019,33(1):379-386.
[20]XU P,DENG Z,CHOI K S,et al.Multi-view information-theoretic co-clustering for co-occurrence data[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2019,33(1):379-386.
[21]LIU X,CHENG H M,ZHANG Z Y.Evaluation of community detection methods[J].IEEE Transactions on Knowledge and Data Engineering,2019,32(9):1736-1746.
[22]WANG C D,LAI J H,SUEN C Y,et al.Multi-exemplar affinity propagation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(9):2223-2237.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发