Research On The Local Community Detection Algorithm Based On Random Walk

In recent years,with the rapid development of the Internet,computer technology and communication industries,the amount of network data has grown rapidly,and the scale of community networks has become increasingly large.It has become increasingly difficult to obtain global information of community networks.At the same time,in the field of network research such as personalized commodity recommendation and prevention of disease transmission,it is only need to find out the local community where single or multiple individuals are located,so the research on local community detection has gradually gained people's attention.Related research shows that in many local community detection algorithms,the Random Walk with Restart(RWR)algorithm has higher accuracy,but there are still some problems,such as initial node sensitivity and incomplete search range.In order to improve the accuracy of local community detection,this paper proposes a multi-strategy local community detection algorithm based on RWR.The main research is as follows:Firstly,to solve the initial node sensitivity problem of RWR algorithm in solving local community detection,an initial node optimization strategy based on local maximum clique is proposed.The largest clique structure where the initial node is located is called the local maximum clique,and two optimization methods are proposed based on the local maximum clique: The first one is based on the local maximum clique optimization method,and the initial node is replaced by the local maximum clique as the restart node of the random walk;The second one is based on the optimization method of the maximum degree node,and the initial node is replaced by the node with the largest degree in the local maximum clique as the restart node of the random walk.The experimental results show that both optimization methods can effectively solve the sensitivity problem of the initial node.Because the second method can find more nodes,the second method is used as the final optimization strategy to improve the accuracy of local community detection.Then,in view of the incomplete search range of RWR algorithm in solving local community detection,a search range optimization strategy based on graph conductance is proposed.According to the size of the community,a appropriate search range is selected,and the minimum graph conductance is used as the objective function of solving the local community detection.At the same time,the size of current node set is compared with the search range,to find correct nodes as many as possible among the decreasing-conductance node interval.The experimental results show that the optimization strategy can find more correct nodes and improve the recall rate of local community nodes.Finally,the multi-strategy local community detection algorithm based on restart random walk is convergent when the ranking of node jump probability is invariant,so the correct order of nodes joining the local community can be obtained in fewer iterations.Our algorithm is compared with Clauset algorithm,Luo algorithm,RWR algorithm and MWC algorithm,and the experimental results show that the algorithm of multi-strategy local community detection algorithm based on RWR has the highest accuracy.