Research On Community Structure Detection In Complex Social Networks

Community structure is one of the most important characteristics in complex network. Identifying the community structure in complex network is important to analyze the topology of the network and understand the function of complex network and discover the hidden pattern behind the network. There are three important problems in community detection algorithms:(1) The traditional community detection algorithms can hardly identify the stable overlapping community structures rapidly in complex network.(2) Identifying the community structure in complex network becomes more complicated with considering the dynamic property in real networks.(3) There are noises in real networks which affect the accuracy and efficiency of the dynamic community detection algorithmsTo solve these problems, we study the static network firstly and consider the link information in network and identify the overlapping community in static network with the combination of label propagation algorithm. And then, we propose the dynamic commun ity detection algorithms respectively based on the hidden markov model and link clustering. In order to avoid the influence of the noise to the algorithms, we propose a new incremental community detection algorithm based on the dynamic noised network. The researches in the dissertation are as follows:1. Considering the traditional node-based overlapping community detection algorithms’ deficiency of identifying the stable overlapping community, a novel algorithm called L2 PA is presented. A new label propaga tion method is proposed which update the labels quickly and get more stable overlapping community structure. The new label propagation method can get stable overlapping community without extra information. The experiment result shows that the proposed algorithm can detect the overlapping community structure effectively in networks.2. In order to improve the accuracy of the dynamic community detection algorithms, a new algorithm called HMM_DC is proposed based on the Hidden Markov Model to detect the community in dynamic social network. The algorithm uses the observed chain and status chain to represent the community structure and node information. The algorithm transforms the community detection problem to get the optimal status chain in Hidden Markov Model with considering the history information and characteristics in dynamic social network.. The experiment results show that HMM_DC algorithm is available and performs effectively and accurately in identifying the community structure in the dynamic social network and the value of modularity and NMI can raise 28% and 20% at least.3. In order to improve the stability of the dynamic community detection algorithms, a link-based dynamic community detection algorithm called LDC is presented to identify the community structure in the dynamic social networks with the improved link partition density and link modularity. The algorithm simplifies the complex incremental information as New Link and Removal Link information in dynamic social network. The experiment results show that the LDC algorithm can detect the community structure effectively in both dynamic artificial and real social networks and the value of modularity and NMI can raise 19% and 13%.4. Considering there are noises in dynamic social network which affect the accuracy and efficiency of the dynamic community detection algorithms, a new algorithm called pre Filter is proposed to solve this problem. The algorithm use the relative entropy to filtering the noise in dynamic social network, then an improved increment algorithm is proposed to identify community structure. The experiment results show that pre Filter can identify the community structure effectively when compared with the other algorithms. The modularity of the algorithm can reach at 0.8 and the NMI varies steadily.