Community structures in complex networks : detection and modeling

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