Design And Implementation Of The Improved Label Propagation Algorithms For Network Data

There is a great deal of information existing complex systems in our life.As the size of system grows,the complexity of network system is becoming more and more common.For example,traffic network becomes more complicated with the increase of vehicles and roads;large-scale power grids also become more complicated due to the increase of users' power demand,and so on.It is crucial to detect the inner structure of network so that network can be analyzed and used.Community detection is one of the popular researches mining complex network and is also an important method to explore and comprehend how to work about network.At present,many community detection algorithms have been proposed.The Label Propagation Algorithm(LPA)is an important algorithm for dealing to large-scale network which gets extensive attention due to nearly-linear running time and easy implementation.Because the label of each node relies on the label of its neighbor nodes in the LPA,the iteration speed and result of ensemble of this algorithm are sensitive to the updating order of label.Therefore,it leads to the outcome of algorithm unstable and inaccurate.In order to improve the performance of community detection,we propose two new algorithms that based on label propagation algorithm.Specific contents are presented as follows.(1)Firstly,this paper proposes a label propagation algorithm based on weighted clustering ensemble.In the new algorithm,we run the multiple times of label propagation algorithms to obtain several partition results which can be seen as a base clustering set.Furthermore,we use the modularity measure to evaluate the importance of each clustering.Based on the evaluation results,we define a weighted similarity measure between nodes to get a weighted similarity matrix of pairwise nodes.Finally,we use hierarchical clustering on the similarity matrix to obtain a final communitydetection result which can have better robustness than each detection result of the original LPA algorithm.In the experimental analysis,the new algorithm is compared with several other improved label propagation algorithms on five real network data set.The experimental results show that the new algorithm is more effective to improve the robustness of community detection,compared to other algorithms.(2)This paper also proposes a label propagation algorithm based on the importance of nodes.The algorithm is mainly to evaluate the importance of nodes by combining information entropy and modularity and sorts the nodes according to the importance of nodes from high to low.Then,the label is propagated starting from key nodes and updating the label by selecting the label of its most critical neighbor nodes so that the precision of community detection can be improved.Finally,the performance of new algorithm in five real network data shows it can detect the community of networks more effectively than other improved label propagation algorithms which have been proposed in recent years.This paper proposes two improved label propagation algorithms from two different perspectives.New algorithm provides novel technical support for analyzing network data.Furthermore,it supplies the effective application value for mining networks communities.