Community structures in complex networks : detection and modeling

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2008
Major/Subject
Mcode
Degree programme
Language
en
Pages
Verkkokirja (1632 KB, 53 s.)
Series
Abstract
Complex systems are composed of a large number of interacting elements such that the system as a whole exhibits emergent properties not obvious from the properties of its individual parts. In the network approach, complex systems are represented as networks whose vertices and edges correspond to the elements and their interactions, respectively. Many networks, such as networks of protein interactions or social relationships, contain sets of densely interconnected nodes, communities, which play a concrete functional role in the original system, such as the group of proteins related to cancer metastasis. Detecting such communities in large networks has rapidly become one of the focal topics in the science of complex networks. The challenge in community detection is to define what constitutes a community in such a way that this definition not only yields meaningful communities but also allows for sufficiently fast algorithmic implementation to find them. This thesis contributes to our understanding of community detection in complex networks in three ways. 1) The limitations of global optimization based community detection methods are analyzed. Here, the focus is on the dependence of the lower size limit of detectable communities on the tuning parameters of the methods. 2) This thesis significantly improves two community detection methods by extending their applicability domain: the Potts method is extended such that it can be applied to dense weighted networks, and a new algorithmic implementation for the k-clique percolation method is presented. The main advantage of the first method is that it allows analysis of dense weighted networks without discarding any of the link weights, whereas the advantage of the second method is its speed especially in the community analysis of weighted networks. 3) This thesis attempts to shed light on the formation of communities in networks. This is done by introducing a weighted model for social networks, whose mechanisms are based on empirical observations of social tie formation as well as observations on the topological role of tie strengths. In this model, communities emerge only if nodes sufficiently favor their strong connections in the process of establishing new ones. The model is also utilized in studies of the effects of correlations of link weights and community structure on dynamics taking place on networks. Simulations of an opinion formation model show that the dynamics is significantly slowed down due to trapping of opinions in homogenized regions corresponding to communities.
Description
Keywords
complex networks, community detection, network dynamics, social networks
Other note
Parts
  • [Publication 1]: J. M. Kumpula, J. Saramäki, K. Kaski, J. Kertész, Limited resolution in complex network community detection with Potts model approach, The European Physical Journal B 56, 41-45 (2007). © 2007 The European Physical Journal (EPJ). By permission.
  • [Publication 2]: J. M. Kumpula, J. Saramäki, K. Kaski, J. Kertész, Limited resolution and multiresolution methods in complex network community detection, Fluctuation and Noise Letters 7, L209-L214 (2007). © 2007 by authors and © 2007 World Scientific Publishing Company. By permission.
  • [Publication 3]: R. Toivonen, J. M. Kumpula, J. Saramäki, J.-P. Onnela, J. Kertész, K. Kaski, The role of edge weights in social networks: modelling structure and dynamics, Proceedings of SPIE 6601, 66010B (2007). © 2007 Society of Photo-Optical Instrumentation Engineers (SPIE). By permission.
  • [Publication 4]: J. M. Kumpula, J.-P. Onnela, J. Saramäki, K. Kaski, J. Kertész, Emergence of communities in weighted networks, Physical Review Letters 99, 228701 (2007). © 2007 American Physical Society. By permission.
  • [Publication 5]: J. M. Kumpula, M. Kivelä, K. Kaski, J. Saramäki, Sequential algorithm for fast clique percolation, Physical Review E 78, 026109 (2008). © 2008 American Physical Society. By permission.
  • [Publication 6]: T. Heimo, J. M. Kumpula, K. Kaski, J. Saramäki, Detecting modules in dense weighted networks with the Potts method, Journal of Statistical Mechanics: Theory and Experiment 2008, P08007 (2008). © 2008 Institute of Physics Publishing. By permission.
Citation