Overlapping modularity at the critical point of k-clique percolation

Abstract

One of the most remarkable social phenomena is the formation of communities in social networks corresponding to families, friendship circles, work teams, etc. Since people usually belong to several different communities at the same time, the induced overlaps result in an extremely complicated web of the communities themselves. Thus, uncovering the intricate community structure of social networks is a non-trivial task with great potential for practical applications, gaining a notable interest in the recent years. The Clique Percolation Method (CPM) is one of the earliest overlapping community finding methods, which was already used in the analysis of several different social networks. In this approach the communities correspond to k-clique percolation clusters, and the general heuristic for setting the parameters of the method is to tune the system just below the critical point of k-clique percolation. However, this rule is based on simple physical principles and its validity was never subject to quantitative analysis. Here we examine the quality of the partitioning in the vicinity of the critical point using recently introduced overlapping modularity measures. According to our results on real social- and other networks, the overlapping modularities show a maximum close to the critical point, justifying the original criteria for the optimal parameter settings.

20 pages, 6 figures

References in corpus (21)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Resolution limit in community detection
• Collective motion
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Structure and tie strengths in mobile communication networks
• Quantifying social group evolution
• CFinder: Locating cliques and overlapping modules in biological networks
• An information-theoretic framework for resolving community structure in complex networks
• Detect overlapping and hierarchical community structure in networks
• Clique percolation in random networks
• Geographical dispersal of mobile communication networks
• Analysis of a large-scale weighted network of one-to-one human communication
• Extending the definition of modularity to directed graphs with overlapping communities
• Complexity: The bigger picture
• Folks in Folksonomies: Social Link Prediction from Shared Metadata
• Multifractal Network Generator
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Link creation and profile alignment in the aNobii social network
• Rotated multifractal network generator