Studies On Methods For Analyzing Community Structure In Complex Networks

As a new emerging discipline, research on complex networks attracts scientists from a varietyof different fields. In fact, studies that can qualitatively and quantitatively characterize complexnetworks will help to unveil the general laws regulating different real systems modeled by complexnetworks, and therefore will be relevant in a number of disciplines (biology, social sciences, etc).Community structure is one of the crucial structural characteristics of complex networks; therefore,accurately analyzing their community structure represents a very relevant topic.In the research related to the analysis of community structure in complex networks, a measurenamed modularity (and variants) plays a crucial role, and from it a large amount of importantapproaches for analyzing community structure have been derived. However, it has been foundthat the optimization of modularity (and of its variants) suffers from resolution limit. This greatlyreduces the effectiveness and the range of applicability of those modularity based methods.Additionally, current studies on community structure analysis are mainly focusing on undi-rected networks, thus analyzing community structure in directed networks represents a yet poorlyunexplored direction in this research area. Indeed, so far, the common approach to communitystructure analysis in directed networks has simply proceeded by discarding the direction of edgesand treating directed networks as undirected ones. Such type of approach frequently fails sincesimply discarding edges'direction removes valuable information and thus results in inaccuratecommunity partitions. Furthermore, very often, the extension of methods for community detectionin undirected networks to those for directed networks is far from trivial.Starting from the issues related to modularity, this thesis extends the analysis of the resolutionlimit from the case of binary undirected networks to that of weighted ones, and thus proposes an en-hanced modularity-based method for community structure analysis via network preprocessing. Byanalyzing the conditions relative to the resolution limit in undirected networks, it can be observedthat the problem can be effectively addressed by acquiring information on inter-community edges.Based on the fact that dynamics events occurring on a network will re?ect its underlying structure,random walks on undirected networks can be used as a surrogate to obtain effective informationon intra-community and inter-community edges. After such information is obtained, iteratively reweighting intra-community and inter-community edges will cause weights to concentrate moreand more into communities, while becoming very small or even vanishing among communities.As a result, the resolution limit problem can be effectively addressed when optimizing modularity.The applications of such a method on real and benchmark networks demonstrate that the effective-ness and the range of applications of using modularity based methods for detecting communitiesin undirected networks is greatly enhanced via network preprocessing.With respect to the problem of inaccurate communities partitioning by discarding the infor-mation contained in edges'direction, a method for analyzing community structure by directednetwork embedding is then proposed. By extending network embedding for undirected networksto directed ones, this method extracts a symmetric matrix from the Laplacian matrix associatedwith the target function for directed network embedding. Such a symmetric matrix can be re-garded as an adjacency matrix for a weighted undirected network that contains the informationon edge direction in the original directed network. Consequently, a new modularity definitionfor directed networks is derived by reformulating the modularity for undirected networks on theinduced adjacency matrix. This new modularity measure provides on one hand an additional phys-ical meaning of communities in directed networks: nodes in the same community are neighboringnodes that preserve as much as possible the local structure of a network. On the other hand, itdiscloses the relationship between the directed network under study and its induced undirectedone. Therefore, methods designed to partition undirected networks, can successfully, safely andefficiently be applied to directed ones, via the definition of the induced undirected network.By further extending this idea, another community analysis method for directed networks isproposed. This method is based on the fact that the ?ow on a directed network with a communitystructure will move more easily among nodes within the same community. It thus employs PageR-ank random walks on directed networks as a proxy of ?ow to effectively extract the informationcontained in edges'direction. By choosing a suitable similarity function, the obtained informationis transformed into edges'weight that will be integrated with edges'connectedness to define com-munity structure in directed networks. After the information contained in the edge directions hasbeen extracted iteratively following this procedure, the edge directions can be safely discarded, andthe community partitioning of a directed network can be obtained via partitioning the undirectedweighted network. This strategy simplifies the problem while retaining the accuracy in analyzingcommunity structure in directed networks.Based on the possible uniformity of the above methods for analyzing community structurein undirected and directed networks, a message passing based unified framework for communitydetection is proposed. In this frame, nodes in a network are expressed in terms of points in avectorial space via random walks on networks. Similarity between nodes can thus be effectivelydefined, and this similarity represents the likelihood of a pair of nodes to be in the same commu- nity. By using message passing mechanism from the affinity propagation method, the communitypartitioning can be regarded as the process of electing community leaders. The applications ofthis message passing based community detection method on real and benchmark networks demon-strate that this framework can effectively: (i) address the problem of the resolution limit, i.e., itcan effectively and correctly partition into communities those networks on which resolution limitwill occur by optimizing modularity; (ii) analyze community structure of undirected networks anddirected networks in a uniform way; (iii) uncover the possible hierarchical community structure innetworks.