Community Detection In Complex Networks

Complex networks are kind of abstraction of complex systems for the individuals in a system can be modeled as nodes, and relations or links among individuals in the system as edges in the graph. In other words, numerous systems in real world can be considered as complex networks. Typical cases are listed below: from WWW to worldwide traffic networks in the area of technology, from metabolic networks to ecological webs in the area of biology, and from scientific collaboration network to on-line communities(e.g. Facebook) in the area of society.A common characteristic of above networks is that subgroup of nodes consisting of tightly connected units, named"communities". However, these communities are sparsely linked to each other. Dividing a network into communities is a crucial and efficient way to obtain the organization (or structure), virtue, and development of the entire network. Convincing detection of communities not only simplifies but stresses the potential structures and the relationships. For instance, it is possible to classify proteins with unknown function by deciding what module they belong to, since modules are sets of genes or proteins that perform biological processes together. And detecting the community structure in information networks allows one to mine information in a more efficient way, narrowing the exploration of a network as large as the World Wide Web to a limited portion of it. Therefore the division of the individuals or nodes into communities is a fundamental aspect of complex networks.In this thesis, we first introduce some significant theory of community detection, and then review some traditional methods and several modern ones. For each algorithm, we understand its idea, analyze its pros and cons and present its complexity and application. Unfortunately, most of these approaches are highly time-consuming and cannot be applied into large networks. At the same time, most of them can not detect all division levels of networks but only obtain a single one, which prevent us from further understanding the organization of networks and analyzing the networks because each division level may imply some useful and important information of the networks. In addition, the results are not so satisfying when apply these methods to detect overlapping communities since nodes in overlapping regions are always wrongly classified. Moreover, characteristics of those nodes lack of quantitative analysis which also lowers the division quality of the networks. With this background, we provide following two methods,"fast hierarchical agglomerative algorithm based on community closeness (FHACC)"and"Community structures detection based on random movement Strategy (RMS)", respectively. FHACC is very effective and faster than lots of well-known methods for its complexity is near to a linear time. And RMS can both find overlapping communities and observe the whole range of topological scales. We adopt the statistics of the frequency of nodes in different communities and offer a new measure, named Community Tendency (CT) of nodes, to quantitatively describe this overlapping characteristic of community structures. And the resolution can be tuned by a multi-scale parameter enabling to investigate different hierarchical levels of organization. In other words, RMS can help us understand and analyze networks on multi-aspects, and then obtain the most exhaustive information about the modular structure of them.