Community detection method based on backbone network extension

Abstract

The invention discloses a community detection method based on backbone network extension, which is used for rapid community discovery in large-scale complex networks. The present invention mainly includes: use the improved PageRank algorithm (WP) based on node weight to calculate the input network, select the node whose WP value is greater than the threshold as the backbone node of the network; traverse the whole network, extract the backbone node and connect any two backbone nodes The edges of the nodes constitute the backbone network; the hierarchical clustering algorithm is run in the backbone network to obtain the backbone community structure; the extension algorithm is used to extend the backbone community to the entire network to obtain the community structure of the overall network. The invention narrows the operating range of the hierarchical clustering algorithm to the backbone network, avoids clustering in the whole network, has relatively small time complexity, and is suitable for community discovery in large-scale complex networks. In addition, the present invention can quickly capture the change details of the overall community by tracking the change of the backbone community, and is suitable for community discovery in a rapidly evolving network.

Description

technical field [0001] The invention relates to the fields of data mining and complex network analysis, in particular to the rapid division of communities under large-scale social networks, and in particular to an efficient community detection method based on backbone network expansion. Background technique [0002] There are a large number of complex systems in the real world, such as biomolecular systems, transportation systems, mail systems, and so on. In order to study the hidden laws in these complex systems and use these laws to serve the needs of human beings in the real world, these complex networks are usually modeled as networks. The entities in the system are regarded as nodes in the network, and the links between entities are regarded as connections or edges in the network. For example, the nodes in the transportation network correspond to intersections, and the edges represent the roads between intersections; the nodes in the protein interaction network represe...

AI Technical Summary

Problems solved by technology

[0016] 1. For a large-scale network, many algorithms need to introduce various node attribute measurement methods according to different scenarios, such as the number of paths between nodes and node similarity calculations. These measurements require multiple iterations, which will lead to low algorithm efficiency , with greater complexity

[0017] 2. Due to the different division criteria used by different algorithms, the results of community division are also different

[0018] 3. In most real-world networks, people cannot know the real number of communities in the network, and many algorithms need to specify the number of communities before dividing the communities

Images