Research On Overlapping Community Detection Based On Local Center Of Gravity

Complex networks spread all over the human society, which generally has the wholeor parts of the following characteristics: self-organization, self-similar attractor,small-world, scale-free and so on. Community structure detection is the hot spot in thecomplex networks research. In complex networks with the community structure, nodes inthe same community are connected closely while links between communities are sparse. Inthis thesis, we first introduced the research status of community structure detection, andhad a detailed analysis of the merits, demerits and scope of application of each algorithm.Considering the problem of overlapping community detection in large-scale directed andweighted network, we proposed a method based on the local center of gravity to detect theoverlapping communities. The main research is outlined as follows:i. Considering the problem of community detection in large-scale directed andweighted networks, we proposed the concept of the local center of gravity and thealgorithm named local center detection (LCGD) based on local features of the network.This algorithm considered the node weight, the edge direction, the edge weight. Takinginto account the influence of the scale of node on the local center of gravity, we putforward another algorithm named LCGD2which is improved from LCGD algorithm.Effectiveness of the algorithms is verified by experiments.ii. Traditional algorithms based on modularity optimization can not discover the smallcommunities. In response to this problem, we integrated weighting mechanism into themodularity function, and proposed the improved version of the multistep expansion (IMSG)algorithm. In each iteration of the algorithm, there are multi communities in accordancewith the conditions to be mergered, which can avoid network premature contraction to bigcommunities, so that the algorithm can effectively find small communities.iii. In order to solve the problem of overlapping community detection in directed and weighted networks, we proposed an overlapping community building strategy and anoverlapping community detection algorithm (LCG-IMSG) based on the local center ofgravity. This algorithm reduced the time complexity by analyzing the local information ofnetwork and detected overlapping community in directed and weighted network byoverlapping community building strategies. We verified this algorithm on directed andweighted e-mail network. We evaluated the quality of community by modularity,community density, and community strength.