Community detection methods based on random walks are widely adopted in various network analysis tasks.It could capture structures and attributed information while alleviating the issues of noises.Though random walks on plain networks have been studied before,in real-world networks,nodes are often not pure vertices,but own different character-istics,described by the rich set of data associated with them.These node attributes contain plentiful information that often complements the network,and bring opportunities to the random-walk-based analysis.However,node attributes make the node interactions more complicated and are heterogeneous with respect to topological structures.Accordingly,attributed community detection based on random walk is challenging as it requires joint modelling of graph structures and node attributes.To bridge this gap,we propose a Community detection with Attributed random walk via Seed replacement(CAS).Our model is able to conquer the limitation of directly utilize the original network topology and ignore the attribute information.In particular,the algorithm consists of four stages to better identify communities.(1)Select initial seed nodes in the network;(2)Capture the better-quality seed replacement path set;(3)Generate the structure-attribute interaction transition matrix and perform the colored random walk;(4)Utilize the parallel conductance to expand the communities.Experiments on synthetic and real-world networks demonstrate the effectiveness of CAS.

Yang CHANG;Huifang MA;Liang CHANG;Zhixin LI

College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China;Guangxi Key Lab of Multi-source Information Mining and Security,Guangxi Normal University,Guilin 541004,China;Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China

计算机科学前沿

[1]Yang CHANG;Huifang MA;Liang CHANG;Zhixin LI-.Community detection with attributed random walk via seed replacement)[J].计算机科学前沿,2022(05):42-53

Utilize

Community,detection,attributed,random,seed,replacement,methods,walks,are,widely,adopted,various,analysis,tasks,It,could,capture,structures,information,while,alleviating,issues,noises,Though,plain,networks,have,been,studied,before,real,world,nodes,often,not,pure,vertices,own,different,character,istics,described,by,rich,set,data,associated,them,These,attributes,contain,plentiful,that,complements,bring,opportunities,However,make,interactions,more,complicated,heterogeneous,respect,topological,Accordingly,community,challenging,requires,joint,modelling,graph,To,bridge,this,gap,propose,Attributed,Seed,CAS,Our,able,conquer,limitation,directly,utilize,original,topology,ignore,In,particular,algorithm,consists,four,stages,better,identify,communities,Select,initial,Capture,quality,path,Generate,transition,matrix,perform,colored,parallel,conductance,expand,Experiments,synthetic,demonstrate,effectiveness

0.58347