Studies On Methods For Identifying Community Structure In Complex Networks

Many complex systems in the real world exist in the form of networks, such as socialnetworks, biological networks, Web networks, etc., which are collectively referred to ascomplex networks. One of the main problems in the study of complex networks is thedetection of community structure, a subject that keeps attracting a great deal of interest.Although no common definition has been agreed upon, a community within a network isusually defined as a group of nodes that are densely connected with respect to the rest of thenetwork.In the past few years, many different approaches have been proposed to uncovercommunity structure in networks. Although previous research towards community detectionmainly focused on the community of nodes, several recent works begin to switch the attentionto community of links. The motivation is that link communities are more intuitive than nodecommunities in many real-world networks. This is due to the link usually having a uniqueidentity, while the node tends to have multiple roles. In a social network, for instance, mostindividuals belong to multiple communities such as families, friends, and co-workers, whilethe link between a pair of individuals often exists for a dominant reason which may representfamily ties, friendship, or professional relationships, et al. Furthermore, the links connected toa single node may belong to several different link communities, thus the node can be assignedto multiple communities of links. Accordingly, overlapping communities of nodes, which isanother attractive topic in community detection, could be detected as a natural byproduct oflink communities.Based on the above discussion, in this work we carry out research from the perspectivesof node community detection and link community detection, respectively. They includes:node community detection in large networks using ant-based optimization, link communitydetection by exploiting link dynamics, and link community detection via generative modeland nonnegative matrix factorization, which will be introduced as follows.Firstly, we propose a multi-layer ant-based algorithm MABA, which detects nodecommunities from networks by means of locally optimizing modularity using individual ants.The basic version of MABA, namely SABA, combines a self-avoiding label propagationtechnique with a simulated annealing strategy for ant diffusion in networks. Once thecommunities are found by SABA, this method can be reapplied to a higher level networkwhere each obtained community is regarded as a new vertex. The aforementioned process isrepeated iteratively, and this corresponds to MABA. Thanks to the intrinsic multi-level nature of our algorithm, it possesses the potential ability to unfold multi-scale hierarchical structures.Furthermore, MABA has the ability that mitigates the resolution limit of modularity. Theproposed MABA has been evaluated on both computer-generated benchmarks and widelyused real-world networks, and has been compared with a set of competitive algorithms.Experimental results demonstrate that MABA is both effective and efficient (in near lineartime with respect to the size of network) for discovering node communities.Secondly, we propose a link dynamics based algorithm, called UELC, for identifyinglink communities of networks. In UELC, the stochastic process of a link-node-link randomwalk is employed to unfold an embedded bipartition structure of links in a network. The localmixing properties of the Markov chain underlying the random walk are then utilized to extracttwo emerged link communities. Further, the random walk and the bipartitioning processes arewrapped in an iterative subdivision strategy to recursively identify link partitions thatsegregate the network links into multiple subdivisions. We evaluate the performance of thenew method on synthetic benchmarks and demonstrate its utility on real-world networks. Ourexperimental results show that our method is highly effective for discovering linkcommunities in complex networks. As a comparison, we also extend UELC to extractingcommunities of node, and show that it is effective for node community identification.At last, we propose a generative model, which is based on the importance of each nodewhen forming links in each community, to describe the structure of link communities. Weproceed to fit the model parameters by taking it as an optimization problem, and solve it usingnonnegative matrix factorization. Thereafter, in order to automatically determine the numberof communities, we extend the above method by introducing a strategy of iterative bipartition.This extended method not only finds the number of communities all by itself, but also obtainshigh efficiency, and thus it is more suitable to deal with large and unexplored real networks.We test this approach on both synthetic benchmarks and real-world networks including anapplication on a large biological network, and compare it with two highly related methods.Results demonstrate the superior performance of our approach over competing methods forthe detection of link communities.The study result of this thesis, especially of the node and/or link community detectionbased on ant-based optimization, link dynamics and generative model, are of both theoreticaland practical benefit to further researches on the analysis of complex networks.