Research On Mining Compact Substructures And Communities Of Complex Networks

In the real world,many systems can be abstractly represented as complex networks,compact substructure mining and community detection are important part of complex network research.Compact substructures and communities help people better understand the organization structure and internal dynamics of the network,so as to realize the key protection of network function modules and the planning of the actual network structure,such as the optimal allocation of resources,the prevention and control of infectious diseases,and the recommendation of commodity chains.Therefore,the study of compact substructure mining and community detection has great theoretical and practical research significance.Obtaining compact substructures through expansion strategies and detecting community structures using genetic algorithms are the current main algorithms.The main problems of these algorithms are:(1)The expansion strategy usually uses the core node as the expansion source,and the evaluation of the core node usually adopts the degree of nodes as the evaluation criterion.Therefore,the marginal nodes and connected nodes with a larger degree value will also be selected as the core nodes,and the compact substructure obtained accordingly has a large error rate;(2)Community detection algorithms based on genetic algorithms often have large populations,high computational cost,premature convergence and other issues.This article takes compact substructure mining and community detection as the research goal.Obtain the approximate skeleton and compact substructure of the network by analyzing the edges between nodes and using the edge intensity as a measure of local density,and designed the Improved Group Genetic Algorithm for community detection based on the compact substructure.The main research work is as follows:(1)Compact substructure mining algorithm based on the network skeleton:Calculate the edge intensity of each edge in the network and assign weights to it,and retain the edge with the strongest edge intensity of each node in the network to form an approximate network skeleton.It contains compact substructures and marginal nodes.By truncating the edges with lower edge intensity in the approximate network skeleton,the nodes and edges are sequentially added to the compact substructure set.(2)Community detection algorithm based on improved grouping genetic algorithm: the obtained compact substructure is used as the basis of population initialization,the size of the population is reduced during encoding,the calculation cost is reduced,and the diffusion process is added to the mutation operator to increase The diversity of the population is avoided,premature convergence is avoided and the overall optimization is facilitated.Both algorithms have been tested on real networks and artificial reference networks,which prove the effectiveness of the method proposed in this article.