Methods Of Community Detection In Complex Networks And Their Responses To Perturbations

One of the fundamental scientific problems of understanding and controllingcomplex systems is the identification of community structures in complex networks.This problem has attracted more and more researchers from various disciplines. Inrecent years, the literatures published in Nature and some other top journals show thatthe hot research topics in community identification still focus on community detectionalgorithms in scenarios of specific community structure with specific assumptions.This thesis proposes several community structure detection methods fornon-overlapping communities and overlapping communities. Furthermore, this thesisanalyzes the impact of network perturbation on community detection methods. Theinnovative achievements of this thesis are as follows:1) A novel class of semi-suprvised methods for discovering non-overlappingcommunity is proposed, which achieves higher accuracy compared with othernon-overlapping community detection methods, especially in the situation where thecommunity structure is obscure. The methods proposed here include semi-supervisedmethod based on label propagation and semi-supervised method based on discretepotential theory. The former via label propagation simulates the dynamic processes ofcomplex networks, and makes the vertices of the same community have the samelabel. While the latter through potential simulates the delivery processes of circuitnetworks so that the vertices of the same community have similar potentials. Theabove two algorithms are both tested on artificial benchmark networks and realnetworks, the experimental results demonstrate that they are more efficient both onaccuracy and time complexity.2) We propose a novel algorithm for overlapping community detection based onlocal random walk, which owns higher accuracy and lower time complexity comparedwith other traditional overlapping community detection methods. The basic idea ofthis algorithm is converting the community detection of complex networks into theproblem of data clustering. In this algorithm, a tradeoff strategy between accuracy andcomputational complexity based on local random walk is used to calculate thedistance matrix of nodes in networks. Then in order to keep the original node distanceas much as possible, the network structure is mapped into low-dimensional space by the multidimensional scaling. Finally, the fuzzy c-means clustering is employed tofind fuzzy communitiesin a network. The experimental results show that the proposedalgorithm is effective and efficient to identify the fuzzy overlapping communities inboth artificial networks and realworld networks.3) We also raise two network disturbance models based on nodes removal andedges removal respectively, and simulate the existing of noise in the networks fromthe perspective of node perturbation and edge perturbation. We try to apply thecurrently common used community detection methods in the above two types ofdisturbance network models. Then we analyze the impacts of noise from theperspective of size and type according to experimental results, and it is furtherverified that the new proposed semi-supervised non-overlapping community detectionmethods are with high noise immunity.In this thesis, the new proposed two types of community detection methods arethe effective exploration and expansion for the methods of community detection. Inaddition, we also quantitatively analyze the relevance between network noise andcommunity structure significance, which could provide theoretical guidance forcommunity structure detection in real networks that are generally with noise.