Social significance of community structure: Statistical view

Abstract

Community structure analysis is a powerful tool for social networks, which can simplify their topological and functional analysis considerably. However, since community detection methods have random factors and real social networks obtained from complex systems always contain error edges, evaluating the significance of community structure partitioned is an urgent and important question. In this paper, integrating the specific characteristics of real society, we present a novel framework analyzing the significance of social community specially. The dynamics of social interactions are modeled by identifying social leaders and corresponding hierarchical structures. Instead of a direct comparison with the average outcome of a random model, we compute the similarity of a given node with the leader by the number of common neighbors. To determine the membership vector, an efficient community detection algorithm is proposed based on the position of nodes and their corresponding leaders. Then, using log-likelihood score, the tightness of community can be derived. Based on the distribution of community tightness, we establish a new connection between $p$-value theory and network analysis and then get a novel statistical form significance measure. Finally, the framework is applied to both benchmark networks and real social networks. Experimental results show that our work can be used in many fields, such as determining the optimal number of communities, analyzing the social significance of a given community, comparing the performance among various algorithms and so on.

arXiv commentThis paper has been withdrawn by the author due to a crucial sign error in equation (17) and high overlapping rate

References in corpus (36)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical Organization in Complex Networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Finding statistically significant communities in networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Detect overlapping and hierarchical community structure in networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Extracting the hierarchical organization of complex systems
• Finding Communities in Linear Time: A Physics Approach
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Robustness of community structure in networks
• Graph spectra and the detectability of community structure in networks
• Assessing the relevance of node features for network structure
• Network Landscape from a Brownian Particle's Perspective
• Statistical significance of communities in networks
• Phase transitions in semisupervised clustering of sparse networks
• Potts model based on a Markov process computation solves the community structure problem effectively
• A testing based extraction algorithm for identifying significant communities in networks
• Identifying communities by influence dynamics in social networks
• Analysis of stability of community structure across multiple hierarchical levels
• Random Stable Matchings

Cited by in corpus (3)

• Local dominance unveils clusters in networks
• Local Graph Clustering with Network Lasso
• A General Definition of Network Communities and the Corresponding Detection Algorithm