Research On Community Detection Algorithm Of Complex Network Based On Common Neighbors

As the information technology rapidly develops,many complex systems in the real world can be presented in the form of networks.Nodes in networks represent entities in systems,and links between nodes represent connections between entities.Since the statistical characteristics of real-world networks are different from that of regular network and random network,the theoretical model describing them is called complex network.The community structure of complex network displays as that local nodes belonging to the same community are connected to each other closely,and there are fewer links between nodes belonging to different communities.Researches on the community structure are conducted to the analysis about structural characteristics,functional modules,information transfer,evolution process of networks,and problems solving in engineering applications.Therefore,community detection in complex network has always been a hot issue.Hierarchical clustering methods can detect community in multi-granularity and reveal the hierarchical structure of networks.However,in some applications,a specific community partition given by non-hierarchical clustering methods is sufficient to solve problems.The quality and speed of community partition has always been the key to evaluating community detection methods.In order to mine the community structure with high quality and ensure faster execution speed,this thesis proposes two community detection algorithms,hierarchical community structure detection algorithms based on common neighbors and community detection algorithm based on label propagation constrained by common neighbors.The innovations of this thesis are as follows:1)According to the basic idea of k-means clustering,the information about common neighbors is extracted from the simple adjacency relationship,and the affinity of nodes is defined to measure the similarity of adjacent nodes.Based on the affinity of nodes,this thesis proposes a divisive algorithm to analyze the community structure of networks hierarchicaly.The algorithm uses heap storage data and indexes to quickly search for minimum affinity and update local affinity.Experimental results demonstrate that the algorithm can detect the hierarchical community structure with high quality,and the execution speed is faster in networks with relatively uniform degree distribution.2)The community detection problem can be described by two optimization objectives: keep the links within communities as many as possible,and keep the nodes within the same community share neighbors as much as possible.On this basis,this thesis proposes an algorithm that uses label propagation strategy to optimize two objectives.In order to reduce the tendency that too many labels of nodes become consistent,the existing constraint about number of links within communities and the proposed constraint about number of common neighbors within communities are introduced.The appropriate constraint strength and weighting coefficient are selected based on experimental comparison results and theoretical analysis.Experimental results demonstrate algorithm anvantages in the quality and speed of community partition,especially in the case of ambiguous community structure.