Journal on Communications ›› 2023, Vol. 44 ›› Issue (6): 198-210.doi: 10.11959/j.issn.1000-436x.2023108
• Comprehensive Review • Previous Articles Next Articles
Yang GAO1,2, Hongli ZHANG2
Revised:
2023-05-11
Online:
2023-06-25
Published:
2023-06-01
Supported by:
CLC Number:
Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk[J]. Journal on Communications, 2023, 44(6): 198-210.
[1] | WATTS D J , STROGATZ S H . Collective dynamics of small-world networks[J]. Nature, 1998,393(6684): 440-442. |
[2] | BARABASI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512. |
[3] | JIN D , YU Z Z , JIAO P F ,et al. A survey of community detection approaches:from statistical modeling to deep learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2023,35(2): 1149-1170. |
[4] | SU X , XUE S , LIU F Z ,et al. A comprehensive survey on community detection with deep learning[J]. IEEE Transactions on Neural Networks and Learning Systems. 2022,doi.org:10.1109/TNNLS.2021.3137396. |
[5] | HE D X , LIU H X , FENG Z Y ,et al. A joint community detection model:integrating directed and undirected probabilistic graphical models via factor graph with attention mechanism[J]. IEEE Transactions on Big Data, 2022,8(4): 994-1006. |
[6] | MAGNANI M , HANTEER O , INTERDONATO R ,et al. Community detection in multiplex networks[J]. ACM Computing Surveys, 2021,54(3): 1-35. |
[7] | ZAREZADEH M , NOURANI E , BOUYER A . DPNLP:distance based peripheral nodes label propagation algorithm for community detection in social networks[J]. World Wide Web, 2022,25(1): 73-98. |
[8] | LIU A , MOITRA A . Minimax rates for robust community detection[C]// Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS). Piscataway:IEEE Press, 2022: 823-831. |
[9] | STEPHAN L , ZHU Y Z . Sparse random hypergraphs:non-backtracking spectra and community detection[C]// Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS). Piscataway:IEEE Press, 2022: 567-575. |
[10] | WU X X , XIONG Y , ZHANG Y ,et al. CLARE:a semi-supervised community detection algorithm[C]// Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2022: 2059-2069. |
[11] | 史艳翠, 王嫄, 赵青 ,等. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019,40(1): 149-162. |
SHI Y C , WANG Y , ZHAO Q ,et al. Research status of community detection based on local expansion[J. Journal on Communications, 2019,40(1): 149-162. | |
[12] | 刘强, 贾焰, 方滨兴 ,等. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018,39(4): 13-20. |
LIU Q , JIA Y , FANG B X ,et al. Research on the scalability of parallel community detection algorithms[J. Journal on Communications, 2018,39(4): 13-20. | |
[13] | COSCIA M , ROSSETTI G , GIANNOTTI F ,et al. DEMON:a local-first discovery method for overlapping communities[C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2012: 615-623. |
[14] | LU M L , ZHANG Z L , QU Z H ,et al. LPANNI:overlapping community detection using label propagation in large-scale complex networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2019,31(9): 1736-1749. |
[15] | PALLA G , DERéNYI I , FARKAS I ,et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005,435(7043): 814-818. |
[16] | YANG J , LESKOVEC J . Overlapping community detection at scale:a nonnegative matrix factorization approach[C]// Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. New York:ACM Press, 2013: 587-596. |
[17] | SU S X , GUAN J W , CHEN B L ,et al. Nonnegative matrix factorization based on node centrality for community detection[J]. ACM Transactions on Knowledge Discovery from Data, 2022,17: 1-21. |
[18] | HE D X , SONG Y , JIN D ,et al. Community-centric graph convolutional network for unsupervised community detection[C]// Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. California:International Joint Conferences on Artificial Intelligence Organization, 2021: 3515-3521. |
[19] | JIN D , LIU Z Y , LI W H ,et al. Graph convolutional networks meet Markov random fields:semi-supervised community detection in attribute networks[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019,33(1): 152-159. |
[20] | LIU Q , ZHAO M J , HUANG X ,et al. Truss-based community search over large directed graphs[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2020: 2183-2197. |
[21] | WHANG J J , GLEICH D F , DHILLON I S . Overlapping community detection using neighborhood-inflated seed expansion[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,28(5): 1272-1284. |
[22] | ANDERSEN R , CHUNG F , LANG K . Local graph partitioning using PageRank vectors[C]// Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS). Piscataway:IEEE Press, 2006: 475-486. |
[23] | KLOSTER K , GLEICH D F . Heat kernel based community detection[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2014: 1386-1395. |
[24] | RADICCHI F , CASTELLANO C , CECCONI F ,et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004,101(9): 2658-2663. |
[25] | CHAKRABORTY T , DALMIA A , MUKHERJEE A ,et al. Metrics for community analysis[J]. ACM Computing Surveys, 2018,50(4): 1-37. |
[26] | PAGE L , BRIN S , MOTWANI R ,et al. The PageRank citation ranking:bringing order to the Web[R]. 1999. |
[27] | LOFGREN P A , GARCIA-MOLINA H , GOEL A , et al . Efficient algorithms for personalized PageRank[D]. California:Stanford University, 2015. |
[28] | YANG R C , XIAO X K , WEI Z W ,et al. Efficient estimation of heat kernel PageRank for local clustering[C]// Proceedings of the 2019 International Conference on Management of Data. New York:ACM Press, 2019: 1339-1356. |
[29] | HOU G H , CHEN X G , WANG S B ,et al. Massively parallel algorithms for personalized PageRank[J]. Proceedings of the VLDB Endowment, 2021,14(9): 1668-1680. |
[30] | KLOUMANN I M , KLEINBERG J M . Community membership identification from small seed sets[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2014: 1366-1375. |
[31] | MEHLER A , SKIENA S . Expanding network communities from representative examples[J]. ACM Transactions on Knowledge Discovery from Data, 2009,3(2): 1-27. |
[32] | CLAUSET A . Finding local community structure in networks[J]. Physical Review E, 2005,72(2): 026132. |
[33] | MISLOVE A , VISWANATH B , GUMMADI K P ,et al. You are who you know:inferring user profiles in online social networks[C]// Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. New York:ACM Press, 2010: 251-260. |
[34] | BIAN Y C , NI J C , CHENG W ,et al. Many heads are better than one:local community detection by the multi-walker chain[C]// Proceedings of 2017 IEEE International Conference on Data Mining (ICDM). Piscataway:IEEE Press, 2017: 21-30. |
[35] | JI P Y , GUO K , YU Z Y . Local community detection algorithm based on core area expansion[C]// Proceedings of Computer Supported Cooperative Work and Social Computing. Singapore:Springer Nature Singapore, 2022: 238-251. |
[36] | WU Y B , ZHANG X , BIAN Y C ,et al. Second-order random walk-based proximity measures in graph analysis:formulations and algorithms[J]. The VLDB Journal, 2018,27(1): 127-152. |
[37] | BIAN Y C , YAN Y W , CHENG W ,et al. On multi-query local community detection[C]// Proceedings of IEEE International Conference on Data Mining (ICDM). Piscataway:IEEE Press, 2018: 9-18. |
[38] | YAN Y W , BIAN Y C , LUO D S ,et al. Constrained local graph clustering by colored random walk[C]// Proceedings of The World Wide Web Conference. New York:ACM Press, 2019: 2137-2146. |
[39] | LUO D S , BIAN Y C , YAN Y W ,et al. Local community detection in multiple networks[C]// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM Press, 2020: 266-274. |
[40] | LIU J X , SHAO Y X , SU S . Multiple local community detection via high-quality seed identification over both static and dynamic networks[J]. Data Science and Engineering, 2021,6(3): 249-264. |
[41] | LU Z Q , WAHLSTR?M J , NEHORAI A . Local clustering via approximate heat kernel PageRank with subgraph sampling[J]. Scientific Reports, 2021,11:15786. |
[42] | YIN H , BENSON A R , LESKOVEC J ,et al. Local higher-order graph clustering[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2017: 555-564. |
[43] | BENSON A R , GLEICH D F , LESKOVEC J . Higher-order organization of complex networks[J]. arXiv Preprint,arXiv:1612.08447, 2016. |
[44] | HUANG L , CHAO H Y , XIE Q . MuMod:a micro-unit connection approach for hybrid-order community detection[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020,34(1): 107-114. |
[45] | LI P Z , HUANG L , WANG C D ,et al. EdMot:an edge enhancement approach for motif-aware community detection[C]// Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM Press, 2019: 479-487. |
[46] | ZHOU D W , ZHANG S , YILDIRIM M Y ,et al. A local algorithm for structure-preserving graph cut[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2017: 655-664. |
[47] | FU D Q , ZHOU D W , HE J R . Local motif clustering on time-evolving graphs[C]// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM Press, 2020: 390-400. |
[48] | LANCICHINETTI A , FORTUNATO S , KERTéSZ J . Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009:doi.org/ 10.1088/1367-2630/11/3/033015. |
[49] | 陈俊宇, 周刚, 南煜 ,等. 一种半监督的局部扩展式重叠社区发现方法[J]. 计算机研究与发展, 2016,53(6): 1376-1388. |
CHEN J Y , ZHOU G , NAN Y ,et al. Semi-supervised local expansion method for overlapping community detection[J. Journal of Computer Research and Development, 2016,53(6): 1376-1388. | |
[50] | YANG J X , ZHANG X D . Finding overlapping communities using seed set[J]. Physica A:Statistical Mechanics and Its Applications, 2017,467: 96-106. |
[51] | 杨贵, 郑文萍, 王文剑 ,等. 一种加权稠密子图社区发现算法[J]. 软件学报, 2017,28(11): 3103-3114. |
YANG G , ZHENG W P , WANG W J ,et al. Community detection algorithm based on weighted dense subgraphs[J. Journal of Software, 2017,28(11): 3103-3114. | |
[52] | LIU Z H , WANG H M , WANG G S ,et al. Link community detection combined with network pruning and local community expansion[J]. Modern Physics Letters B, 2021:doi.org/10.1142/S0217984921500986. |
[53] | GAO Y , YU X Z , ZHANG H L . Uncovering overlapping community structure in static and dynamic networks[J]. Knowledge-Based Systems, 2020:doi.org/10.1016/j.knosys.2020.106060. |
[54] | GAO Y , YU X Z , ZHANG H L . Graph clustering using triangle-aware measures in large networks[J]. Information Sciences, 2022,584: 618-632. |
[55] | GAO Y , ZHANG H L , YU X Z . Higher-order community detection:on information degeneration and its elimination[J]. IEEE/ACM Transactions on Networking, 2023,31(2): 891-903. |
[56] | GAO Y , ZHANG H L , YU X Z . Overlapping community detection based on conductance optimization in large-scale networks[J]. Physica A:Statistical Mechanics and Its Applications, 2019,522: 69-79. |
[57] | GAO Y , YU X Z , ZHANG H L . Overlapping community detection by constrained personalized PageRank[J]. Expert Systems with Applications, 2021,173:114682. |
[58] | ZHANG Y L , XIA X W , XU X ,et al. Robust hierarchical overlapping community detection with personalized PageRank[J]. IEEE Access, 2020,8: 102867-102882. |
[59] | FU S , WANG G Y , XU J ,et al. IbLT:an effective granular computing framework for hierarchical community detection[J]. Journal of Intelligent Information Systems, 2022,58(1): 175-196. |
[60] | JEH G , WIDOM J . SimRank:a measure of structural-context similarity[C]// Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2002: 538-543. |
[61] | OKUDA M , SATOH S , SATO Y ,et al. Community detection using restrained random-walk similarity[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021,43(1): 89-103. |
[62] | GASTEIGER J , BOJCHEVSKI A , GüNNEMANN S . Predict then propagate:graph neural networks meet personalized PageRank[J]. arXiv Preprint,arXiv:1810.05997, 2018. |
[63] | BOJCHEVSKI A , GASTEIGER J , PEROZZI B ,et al. Scaling graph neural networks with approximate PageRank[C]// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM Press, 2020: 2464-2473. |
[64] | DANON L , DíAZ-GUILERA A , DUCH J ,et al. Comparing community structure identification[J]. Journal of Statistical Mechanics:Theory and Experiment, 2005:doi.org/10.1088/1742-5468/2005/ 09/P09008. |
[65] | MCDAID A F , GREENE D , HURLEY N . Normalized mutual information to evaluate overlapping community finding algorithms[J]. arXiv Preprint,arXiv:1110.2515, 2011. |
[66] | LI Y X , HE K , KLOSTER K ,et al. Local spectral clustering for overlapping community detection[J]. ACM Transactions on Knowledge Discovery from Data, 2018,12(2): 1-27. |
[67] | NEWMAN M E J . Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006,103(23): 8577-8582. |
[68] | BIAN Y C , HUAN J , DOU D J ,et al. Rethinking local community detection:query nodes replacement[C]// Proceedings of IEEE International Conference on Data Mining (ICDM). Piscataway:IEEE Press, 2021: 930-935. |
[1] | Xin-heng WANG,Qian-yun WANG,Jia-jie WANG,Guo-feng ZHAO,Wen-qiang JIN. RW-MC:self-adaptive random walk based matrix completion algorithm [J]. Journal on Communications, 2017, 38(9): 95-105. |
[2] | Shu-kui ZHANG,Sheng-rong GONG,Zhi-ming CUI,Jian-xi FAN. Energy-balance data transmission algorithm with biased random walk [J]. Journal on Communications, 2011, 32(2): 18-26. |
[3] | Xiao-ping ZENG,Yi LIU,Guo-jin LIU. Image denoising based on spectral graph theory and random walk kernel [J]. Journal on Communications, 2010, 31(7): 117-121. |
[4] | Sen XU,Zhi-mao LU,Guo-chang GU. Spectral clustering algorithms for document cluster ensemble problem [J]. Journal on Communications, 2010, 31(6): 0-66. |
[5] | Yong LIU,Xu-cheng LUO,Zhi-guang QIN. Biased random walk-based replication and search [J]. Journal on Communications, 2009, 30(12): 93-98. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||
|