Research On Community Detection Algorithms Based On Distance Dynamics

Social network analysis consists of different approaches for analyzing and mining the social network.It tries to analyze the social network from many aspects,revealing the information about the topological structure.Community detection is one of the most fundamental techniques in the social network analysis.Based on the connections in the topological structure,it clusters densely connected nodes into communities.Community detection can reveal the hidden topological information so that the social network can be better analyzed.With the advance of the social network,community detection and other analytical techniques are developing,and are also applied in many aspects.With the growing size of social networks,the community detection algorithm is required to be both accurate and scalable.Besides,the data structure also becomes increasingly complicated.Sometimes the nodes can have their attributes,and then the network develops into the attributed network,which requires the community detection algorithm to take advantage of both topology and attributes.Neither the current topological community detection algorithms nor the current attributed network algorithms are satisfying when it comes to accuracy,stability,or scalability.Thus it is important to design an accurate and scalable algorithm that can utilize not only the topological information but the attribute information as well.The algorithm named Attractor,which is based on the distance dynamics,is drawing more and more attention because of its high accuracy and satisfying scalability.This algorithm,however,has an abstract parameter,which is hard to determine its value.Users may determine the parameter blindly,which brings about some problem such as the monster community,or generally fragmentary communities in the result.Even if the parameter is properly determined,there are still some remaining fragmentary communities.Since the algorithm lacks the mechanism to eliminate the fragments,the result is deteriorated.Furthermore,the algorithm is merely topological,so it cannot utilize the attribute information when it comes to the attributed networks,which limits the performance and application of the algorithm.We design an automatic parameter adjusting mechanism for the new algorithm to solve the problems caused by the abstract parameter.Based on the relationship between the parameter and the result,two quality constraints are introduced.The algorithm can judge whether the parameter is properly determined by examining the two constraints,and then updates the parameter.The algorithm designs a mechanism to eliminate the remaining fragments.Inspired by the Label Propagation Algorithm,we cluster the fragmentary nodes into the community nearby,and preserve the scalability at the same time.We also introduce an optional and intuitive parameter,which is the wanted number of communities.A legality judgment is produced to prevent the optional parameter from deteriorating the result.We bring all the new functions together and get the modified Attractor.Experiments show that the modified algorithm can achieve a maximum promotion of 14.3% in Rand Index and 17.2% in Modulariy.This paper also gives another algorithm to deal with attributed networks,which redefines the old kernel of Attractor.We construct the heterogeneous network from the attributed network,and regulate the node behaviors.By redefining the interactions between the vertices,we make it possible for the algorithm to utilize both topological information and attribute information and to reach a balanced result with the interaction between two kinds of information.Experiments show that the new algorithm HAttrator can promote the accuracy performance(by 3.2%-46.3%)as well as the stability by utilizing the attributes.We combine two new algorithms into a unified algorithm called HMAttractor,which has all the new functions mentioned above.Data experiments show that HMAttractor outperforms other attributed community detection algorithms a lot.It also achieves a satisfying scalability at the same time and has an advantage over other algorithms when it comes to large-scale networks.