基于随机游走的社区发现方法综述

doi:10.11959/j.issn.1000-436x.2023108

摘要/Abstract

摘要：

随机游走技术可实现准确、高效的社区发现。为总结分析基于随机游走的社区发现方法，将随机游走技术细分为个性化网页排名方法、热核扩散方法和其他随机游走方法，将社区发现问题分为局部社区发现和全局社区结构识别两类任务。详细综述了不同类型的随机游走技术及其在2种社区发现任务中的应用方式，并分析了现有方法存在的问题，对未来研究方向进行了展望。最后，针对不同社区发现任务从相似性标准与结构性标准两方面总结了社区发现准确性的评价指标，为相关研究提供便利。

关键词: 局部社区发现, 全局社区结构识别, 随机游走, 图扩散

Abstract:

Random walk techniques achieve high accuracy and efficiency in community detection.To summarize and analyze community detection methods based on random walk, the random walk technique was classified into personalized PageRank, heat kernel diffusion and other random walk methods, and community detection was classified into tasks of local community detection and global community structure identification.A detailed overview of different techniques based on random walk and their application to the tasks of community detection was provided, problems in existing methods were analyzed, and future research directions were pointed out.Finally, evaluation metrics of community detection accuracy for different community detection tasks were summarized in terms of similarity and structure respectively to facilitate research in community detection.

Key words: local community detection, global community structure identification, random walk, graph diffusion

中图分类号:

TP391

高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.

Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk[J]. Journal on Communications, 2023, 44(6): 198-210.

图/表 6

表1

主要符号及其含义"

符号	含义
G(V, E)	包含节点集V和边集E的网络
$A$	网络的邻接矩阵
$D$	节点度的对角矩阵
$P$	随机游走的转移矩阵
$s$	图扩散的起始向量
$h$	图扩散向量
$\tilde{h}$	近似图扩散向量
ID(C)	社区C的内部密度
AD(C)	社区C的平均度
TPR(C)	社区C的三角形参与率
Ex(C)	社区C的延展
CR(C)	社区C的切率
Co(C)	社区C的导率
$x (s)$	相对于起始向量 $s$ 的个性化网页排名向量
$\tilde{x} (s)$	相对于起始向量 $s$ 的近似个性化网页排名向量
$h (s)$	相对于起始向量 $s$ 的热核向量

表1

图1

图2

图3

表2

表3

参考文献 68

[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.

分类	方法	核心思想
基于PPR	APPR^[22]	PPR向量的局部计算，清扫技术
	MWC^[34]	动态起始向量，幂迭代方法
	PP^2[36]	二阶个性化网页排名方法
	MRW^[37]	面向多种子问题，动态起始向量
	CRW^[38]	面向多种子问题，动态转移矩阵
	RWM^[39]	面向多层网络的局部社区发现问题
基于热核扩散	hk-relax^[23]	松弛法
	TEA^[28]	确定性图遍历，蒙特卡罗随机游走
	文献[41]	子图抽样
高阶方法	MAPPR^[42]	基于模体的个性化网页排名方法
	HOSPLOC^[46]	近似计算高阶随机游走分布
	L-MEGA^[47]	跟踪高阶随机游走的稳态分布

分类	方法	核心思想
局部扩展	NISE^[21]	网络修剪，计算近似PPR向量
	LECM^[56]	计算近似PPR向量，社区优化
	CPPR^[57]	在转移矩阵中引入强化矩阵
	BTLCD^[54]	定义多类型高阶单元
	BPPR^[55]	定义混合超图
其他方法	C_PPR^[58]	捕获节点间的长距离相似性
	RR^[61]	利用受限随机游走相似性
	PPNP^[62]	将神经网络与传播方案分离