Research On Community Detection Based On Improved Label Propagation Algorithm

Research shows that there always are community structures in complex networks, nodes which are inside communities have closer connection between each other. The purpose of community mining is to detect community structure from complex networks, understand more about the topological structure and function, explore the dynamics and evolutionary mechanism of networks. Community mining possesses very important theoretical significance and practical application value.Aming at the low accuracy and unstability of label propagation based community mining algorithm, this topic come up with two improved label propagation algorithm, which effectively use the affect that node centrality produces during community mining, so as to reduce the community division error rate and unstability, which casused by treating every node on an equal footing and updating labels randomly. Main works of this thesis include:(1) We gave a local key nodes based label propagation algorithm. This method used the degree centrality to define local key nodes, assigned the same label to this nodes and there neighbors respectively, then proceeded traditional label propagation program. Through experiments proved that this algorithm can effectively improve the quality and stablility of LPA, meanwhile, maintained the near linear time complexity.(2) We gave the definition of Leader Rank centrality and Leader Rank central nodes, and propose a Leader Rank central node extending based label propagation algorithm. This method found all Leader Rank central nodes firstly, then considered them as label propagating sources, used Leader Rank centrality to measure the priority of label propagation, and adopt a new strategy to update the label of every node, and then detected community structure of this network. At last, lots of experiments shows that, comparing with secceral other representative improved method, this method promotes the accuracy and stability more significantly.