A Community Detection Algorithm Based On Label Propagation And Deep Walk

Community detection is one of the most important researches in recent years.The main algorithm of community detection in the modern society is generally sorted into four types:the algorithm based on modularity,the algorithm based on spectrum analysis,the algorithm based on information theory and the algorithm based on label propagation.Among them,the algorithm based on label propagation has much higher efficiency,but it generates inaccurate results.Aimed at the inaccuracy of the LPA's result,this paper raised a new algorithm based on Deep Walk and label propagation.The experiment on the real datasets and synthesis dataset shows that the algorithm has improved the accuracy of the result.This paper's main innovations are as follows.(1)This paper mainly uses the Deep Walk model to train the nodes of the network.Based on this idea,the algorithm samples random sequences of the nodes by the Deep Walk model.And then take the sequences as SkipGram model's input and calculate the result by Hierarchical Softmax in order to get the representation of nodes.Finally it can get the improved adjacent matrix.(2)Being different from the traditional label propagation algorithm which allocates labels for every nodes in the network,the improved algorithm choose some nodes which have high influence in the network as the seeds,and then allocate the labels only for these nodes.(3)Last but not the least,after allocating labels,the algorithm save the nodes'similarity into the adjacent matrix and calculate the weighted result,which is the standard of the label propagation process.This process can finally get the result of community detection.The experiments are taken on 6 real datasets and 3 synthesis dataset.Compared with the result of LPA,CNM,and LPAp,the result of algorithm raised by this paper indicates that it has much more highly accuracy,especially for the networks which have more than 100 nodes,and the improvement rates of Q are above 10%.