Community structure in social and biological networks

DOI10.1073/PNAS.122653799zbMATH Open1032.91716arXivcond-mat/0112110OpenAlexW1971421925WikidataQ24534298 ScholiaQ24534298MaRDI QIDQ4547718FDOQ4547718

Authors: Michelle Girvan, M. E. J. Newman 

Publication date: 11 September 2002

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Abstract: A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.

Full work available at URL: https://arxiv.org/abs/cond-mat/0112110

Recommendations

• Fast unfolding of communities in large networks
• Detecting network communities: a new systematic and efficient algorithm
• Mixing patterns and community structure in networks
• Algorithms and Models for the Web-Graph
• Community discovery algorithms: an overview

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30)

Cites Work

• Emergence of Scaling in Random Networks
• A new status index derived from sociometric analysis
• Collective dynamics of `small-world' networks
• Exploring complex networks

Cited In (only showing first 100 items - show all)

• Role models for complex networks
• Anti-modularity and anti-community detecting in complex networks
• Remotely sensed image classification by complex network eigenvalue and connected degree
• On the approximability of positive influence dominating set in social networks
• Exact and approximate algorithms for computing betweenness centrality in directed graphs
• Community detection in node-attributed social networks: a survey
• Phase transitions in semidefinite relaxations
• On the statistical detection of clusters in undirected networks
• Synchronizing Hindmarsh-Rose neurons over Newman-Watts networks
• Dynamic Bayesian combination of multiple imperfect classifiers
• Epidemic process on activity-driven modular networks
• Beyond the expanders
• Coexistence of opposite opinions in a network with communities
• Link prediction via convex nonnegative matrix factorization on multiscale blocks
• Finding groups with maximum betweenness centrality
• Variable neighborhood search approach to community detection problem
• Optimal partition and effective dynamics of complex networks
• Spectral coarse graining for random walks in bipartite networks
• Effects of the network structural properties on its controllability
• Finding clique clusters with the highest betweenness centrality
• Topological aspects of the multi-language phases of the naming game on community-based networks
• Community structures in classical network models
• Remarks on network community properties
• Optimal map of the modular structure of complex networks
• Network-based identification of reliable bio-markers for cancers
• A fast and efficient algorithm to identify clusters in networks
• Metastability and chimera states in modular delay and pulse-coupled oscillator networks
• Reverse engineering of complex dynamical networks in the presence of time-delayed interactions based on noisy time series
• Spectral coarse graining of complex clustered networks
• Traveling salesman problems with PageRank distance on complex networks reveal community structure
• Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks
• Identifiability and parameter estimation of the overlapped stochastic co-block model
• A note on the Estrada-Hatano communicability algorithm for detecting community structure in complex networks
• Enhancing synchrony in asymmetrically weighted multiplex networks
• Communicability graph and community structures in complex networks
• Finding critical links for closeness centrality
• Synchronization in complex networks with a modular structure
• Modularity revisited: a novel dynamics-based concept for decomposing complex networks
• Clusters from higher order correlations
• A testing based extraction algorithm for identifying significant communities in networks
• A one-parameter family of stationary solutions in the susceptible-infected-susceptible epidemic model
• Inevitable self-similar topology of binary trees and their diverse hierarchical density
• Maximizing modularity intensity for community partition and evolution
• Generation of networks with prescribed degree-dependent clustering
• Modularity of directed networks: cycle decomposition approach
• Clustering and community detection in directed networks: a survey
• GRAPH ZETA FUNCTION AND DIMENSION OF COMPLEX NETWORK
• Scale-free network clustering in hyperbolic and other random graphs
• Contagion dynamics in multilayer networks with community structure
• USING GRAPH CONCEPTS TO UNDERSTAND THE ORGANIZATION OF COMPLEX SYSTEMS
• A classification for community discovery methods in complex networks
• An almost-solvable model of complex network dynamics
• Spectral clustering methods for multiplex networks
• A tabu-search heuristic for deterministic two-mode blockmodeling of binary network matrices
• Snapshot centrality indices in dynamic FIFO networks
• Chimera state and route to explosive synchronization
• Cluster synchronization in community network with hybrid coupling
• Spreading dynamics in complex networks
• Randomized shortest paths with net flows and capacity constraints
• The Kuramoto model in complex networks
• Overlapping community detection in complex networks using multi-objective evolutionary algorithm
• Statistical physics of vaccination
• Clustering of sparse data via network communities -- a prototype study of a large online market
• Auxiliary parameter MCMC for exponential random graph models
• General results on preferential attachment and clustering coefficient
• Probabilistic SimRank computation over uncertain graphs
• A framework of mapping undirected to directed graphs for community detection
• SOCIAL DILEMMAS AND COOPERATION IN COMPLEX NETWORKS
• Using Community Structure to Detect Relevant Learnt Clauses
• DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems
• ChordLink: a new hybrid visualization model
• Community detection and stochastic block models: recent developments
• Consistency of community detection in networks under degree-corrected stochastic block models
• Community discovery using nonnegative matrix factorization
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Model selection in overlapping stochastic block models
• A review of dynamic network models with latent variables
• \(k\)-core architecture and \(k\)-core percolation on complex networks
• A new modularity measure for fuzzy community detection problems based on overlap and grouping functions
• Consistency of spectral clustering in stochastic block models
• Uncovering space-independent communities in spatial networks
• Complex networks: structure and dynamics
• A branch-and-bound approach for maximum quasi-cliques
• Optimal adaptivity of signed-polygon statistics for network testing
• Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks
• Improved Bayesian inference for the stochastic block model with application to large networks
• The dynamic random subgraph model for the clustering of evolving networks
• Mining hidden links in social networks to achieve equilibrium
• The random subgraph model for the analysis of an ecclesiastical network in Merovingian Gaul
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Spectral redemption in clustering sparse networks
• Mathematical programming formulations for the collapsed k-core problem
• Link removal for the control of stochastically evolving epidemics over networks: a comparison of approaches
• Extracting backbones from weighted complex networks with incomplete information
• Fractional integral transform and application
• Modeling gene networks in \textit{Saccharomyces cerevisiae} based on gene expression profiles
• Impact of regularization on spectral clustering
• Community detection in dense random networks
• Mixture models and exploratory analysis in networks
• SAT-based models for overlapping community detection in networks

This page was built for publication: Community structure in social and biological networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4547718)