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)

• Mixing local and global information for community detection in large networks
• Observer-based lag synchronization between two different complex networks
• Community detection in networks via a spectral heuristic based on the clustering coefficient
• Cluster synchronization induced by one-node clusters in networks with asymmetric negative couplings
• Independence versus indetermination: basis of two canonical clustering criteria
• Cluster synchronization in colored community network with different order node dynamics
• Efficient methods for the distance-based critical node detection problem in complex networks
• Improving heuristics for network modularity maximization using an exact algorithm
• A reductive approach to hypergraph clustering: an application to image segmentation
• Nested hierarchies in planar graphs
• Parameter identification of dynamical networks with community structure and multiple coupling delays
• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• Communities in Large Networks: Identification and Ranking
• Generation of arbitrary two-point correlated directed networks with given modularity
• Pinning controllability of complex networks with community structure
• Epidemic behaviors in weighted networks with core-periphery structure
• Global and local targeted immunization in networks with community structure
• A combinatorial model and algorithm for globally searching community structure in complex networks
• Spike phase synchronization in multiplex cortical neural networks
• Epidemic control analysis: designing targeted intervention strategies against epidemics propagated on contact networks
• On the complexity of Newman's community finding approach for biological and social networks
• Learning overlapping communities in complex networks via non-negative matrix factorization
• Weighted phase lag index and graph analysis: preliminary investigation of functional connectivity during resting state in children
• Bayesian degree-corrected stochastic blockmodels for community detection
• Modified modularity density maximization and density ratio heuristic
• A multidimensional and multimembership clustering method for social networks and its application in customer relationship management
• Optimal control strategy for traffic driven epidemic spreading based on community structure
• Detecting and preventing error propagation via competitive learning
• A simple and efficient algorithm for modeling modular complex networks
• Recent advances on failure and recovery in networks of networks
• Community detection method based on robust semi-supervised nonnegative matrix factorization
• Modularized tri-factor nonnegative matrix factorization for community detection enhancement
• Nonnegative matrix factorization with mixed hypergraph regularization for community detection
• Scalably revealing the dynamics of soft community structure in complex networks
• Random walk with restart: fast solutions and applications
• Hearing the clusters of a graph: A distributed algorithm
• Nash stability in additively separable hedonic games and community structures
• Data mining of social networks represented as graphs
• Assessing the quality of multilevel graph clustering
• Traffic dynamics on complex networks: a survey
• Community detection by modularity maximization using GRASP with path relinking
• Spectral bounds for the betweenness of a graph
• Centrality measure in graphs
• Dynamical distance: coarse grains, pattern recognition, and network analysis
• Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that
• Clustering of high throughput gene expression data
• The enumeration of vertex induced subgraphs with respect to the number of components
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• Divisive heuristic for modularity density maximization
• Social structure optimization in team formation
• Local law and Tracy-Widom limit for sparse stochastic block models
• Reformulation of a model for hierarchical divisive graph modularity maximization
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• Dynamical robustness and firing modes in multilayer memristive neural networks of nonidentical neurons
• Finding community structures in complex networks using mixed integer optimisation
• Community structures of networks
• Cluster synchronization in community networks with nonidentical nodes via edge-based adaptive pinning control
• Unbalanced graph partitioning
• Social centrality using network hierarchy and community structure
• Identification of functional modules in a PPI network by clique percolation clustering
• Cluster lag synchronisation in community networks via linear pinning control with local intermittent effect
• Outer synchronization between drive-response networks with nonidentical nodes and unknown parameters
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Synchronization of discrete dynamical networks with non-delayed and delayed coupling
• Clustering as a dual problem to colouring
• Characterization of symmetry of complex networks
• Dynamics of an alcoholism model on complex networks with community structure and voluntary drinking
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Large dicliques in a directed inhomogeneous random graph
• Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering
• Networks beyond pairwise interactions: structure and dynamics
• Edge intensity-based community measurement in complex networks
• Randomly stopped extreme Zipf extensions
• Distributed Community Detection in Dynamic Graphs
• Directed Community Detection With Network Embedding
• ON SUCCINCT REPRESENTATION OF KNOWLEDGE COMMUNITY TAXONOMIES WITH FORMAL CONCEPT ANALYSIS
• A spectral clustering-based framework for detecting community structures in complex networks
• Detecting community structure: from parsimony to weighted parsimony
• On the connectivity and the diameter of betweenness-uniform graphs
• Modularity density of network community divisions
• Statistical physics approaches to the complex Earth system
• Bounds and relations involving adjusted centrality of the vertices of a tree
• A measure for a balanced workload and its extremal values
• Network robustness to targeted attacks. The interplay of expansibility and degree distribution
• Fundamentals of spreading processes in single and multilayer complex networks
• An algorithm J-SC of detecting communities in complex networks
• Cluster synchronisation of directed complex dynamical networks with nonidentical nodes via pinning control
• Bayesian community detection
• Configuring random graph models with fixed degree sequences
• The information transmission in community networks
• Analysis of attachment models for directory and file trees
• Structural and functional clusters of complex brain networks
• On betweenness-uniform graphs.
• The k-Dense Method to Extract Communities from Complex Networks
• Core-periphery structure in networks (revisited)
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Evidential identification of influential nodes in network of networks
• EPIDEMIOLOGY MODEL ON SHORTCUT AND SMALL WORLD NETWORKS
• The community structure of human cellular signaling network

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)