Research And Implementation Of Community Detection Algorithm In Weighted Network

With the rapid development of Web 3.0,the scale of social networks grows rapidly,and shows the more obvious characteristic of community structure.Therefore,many scholars conducted the study of community detection.The community detection algorithms emerged in an endless stream.Among them,the LPA label propagation algorithm was widely used because it had linear time complexity and there was no need to pre-define the number and size of communities.However,the traditional label propagation algorithm treated each neighbour node as equal status,and updated labels only according to the number of labels of the neighbour nodes,which led to the uncertainty of the results of community partitioning.In addition,the existing research of community detection mostly focused on weightless networks and did not consider the importance that the weights of edges in weighted networks could express.Therefore,in order to solve the problem that the accuracy and stability of the label propagation algorithm was not high,we studied the community detection of weighted networks and improved the label propagation algorithm step by step:(1)Firstly,we put forward the label propagation algorithm that incorporated node-to-node compactness,which took the weights of edges into account,calculated the label influence according to node-to-node compactness expressed by the weights of edges,and then updated labels;(2)Secondly,we continued to put forward the first-order label propagation algorithm that incorporated node influence and node-to-node compactness,which took the weights of nodes into account in addition to the weights of edges,calculated node influence by the first-order PageRank algorithm,and calculated the label influence of the immediate neighbour nodes according to node influence and node-to-node compactness,and then updated labels;(3)Thirdly,we continued to put forward the second-order label propagation algorithm that incorporated node influence and node-to-node compactness,which took the second-order neighbour nodes into account in addition to the immediate neighbour nodes,calculated node influence by the second-order PageRank algorithm,and calculated label influence of the immediate neighbour nodes and the second-order neighbour nodes according to node influence and node-to-node compactness,and then updated labels;(4)Lastly,we attempted to continue to extend to the third-order label propagation algorithm.By using several algorithms on several datasets with different scales respectively,the accuracy and stability of each algorithm were verified by comparing the average of modules and the average pairwise probabilities of the nodes.The following conclusions were drawn:(1)The label propagation algorithm that incorporated node-to-node compactness,and the first-order label propagation algorithm that incorporated node influence and node-to-node compactness could improve the accuracy and stability in turn;(2)The second-order label propagation algorithm could further improve the accuracy and stability in large-scale weighted networks,but its performance might or might not be as good as the first-order label propagation algorithm in small-scale weighted networks,which depended on the actual situation.In general,the first-order and second-order label propagation algorithms had relatively good performance.Therefore,we finally used the first-order label propagation algorithm and the second-order label propagation algorithm comprehensively to accomplish the dynamic community detection of the multi-path transmission system.The better first-order label propagation algorithm or the second-order label propagation algorithm could be selected for community detection according to the network structure in different time periods.It was further verified that the first-order label propagation algorithm and the second-order label propagation algorithm also had practical application value.