Research On The Community Discovery Algorithm Based On Tightness

The huge number of nodes and the complex interactions between them constitutecomplex networks[1], such as social networks, Internet, transportation networks andso on. Community phenomenon of complex networks is a universal phenomenon,which expresses the nature of individuals in the same community with commoncharacteristics in some particular aspects. Contact between nodes that in samecommunity are tight, and contact between the nodes in different communities isrelatively sparse. Community detection is of great importance for analysis on complexnetwork topology, discover implied patterns and information and predict theirbehavior.This article reviews some of the typical community detection algorithms, such asKernighan-Lin algorithm, spectral bisection; GN algorithm and Radicchi algorithmbased on betweenness; some based on simulated annealing, genetic algorithms andgreedy algorithm; hierarchical clustering method and W-H algorithm. Analyze thetime complexity of these algorithms, pointing out their strengths and weaknesses, andalso gives the scope of these algorithms.In current, in some popular networks such as dating networks and instantmessaging networks, dialogue between two nodes more frequent indicates that contactbetween these two nodes more closely, we use weights between two nodes on behalfof frequency of communication, the greater the weight the closer the relationshipbetween the two nodes. However, currently many community detection algorithms arenot considered weights which between nodes, this paper proposes a hierarchicalclustering community detection algorithm based on tightness of weights that betweennodes of complex networks.In the hierarchical clustering algorithm, the computing of traditional method oftightness between nodes is mainly based on the topology of the network, such ascosine similarity, Euclidean distance and Pearson coefficient and so on. This paper isbased on the network topology, and adds the weights between nodes to computetightness. More frequent communication between nodes, the larger the weight, themore tightness between the nodes, and the higher the possibility of belonging to the same community. This paper not only to calculate the value of the tightness betweennodes, but also extend the tightness computing between communities, combinecommunities based on tightness value, the result of community combination until thetermination condition is met. Experiments show that the method can find communitystructure good and reasonable.