Community detection with attributed random walk via seed replacement  

作　　者：Yang CHANG Huifang MA Liang CHANG Zhixin LI 

机构地区：[1]College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China [2]Guangxi Key Lab of Multi-source Information Mining and Security,Guangxi Normal University,Guilin 541004,China [3]Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China

出　　处：《Frontiers of Computer Science》2022年第5期45-56,共12页中国计算机科学前沿（英文版）

基　　金：This work is supported by the National Natural Science Foundation of China(Grant Nos.61762078,61363058,61966004,61966009,U1711263,U1811264);Natural Science Foundation of Gansu Province(21JR7RA114);Northwest Normal University Young Teachers Research Capacity Promotion Plan(NWNU-LKQN2019-2);Research Fund of Guangxi Key Laboratory of Trusted Software(kx202003).

摘　　要：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 characteristics,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.

关 键 词：community detection SEEDS colored random walk parallel conductance 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]