Line graphs, link partitions, and overlapping communities.

In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm that produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this.

• Publication year

  2009

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2009-03-12

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.80.016105arXiv 0903.2181PMID 19658772
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• THE AMERICAN JOURNAL OF SOCIOLOGY

  2010cited by this paper
• Communities in Networks

  2009cited by this paper
• Communities, knowledge creation, and information diffusion

  2009cited by this paper
• Towards an explanatory and computational theory of scientific discovery

  2009cited by this paper
• Fast unfolding of communities in large networks

  2008cited by this paper
• Fault-tolerant computing with biased-noise superconducting qubits: a case study

  2008cited by this paper
• Extending the definition of modularity to directed graphs with overlapping communities

  2008cited by this paper
• Detecting the overlapping and hierarchical community structure in complex networks

  2008cited by this paper
• Multi-level Algorithms for Modularity Clustering

  2008cited by this paper
• Analysis of the structure of complex networks at different resolution levels

  2007cited by this paper
• Modularity-maximizing graph communities via mathematical programming

  2007cited by this paper
• Bipartite network projection and personal recommendation.

  2007cited by this paper
• Statistical mechanics of community detection.

  2006cited by this paper
• Uncovering the overlapping community structure of complex networks in nature and society

  2005cited by this paper
• Uncovering collective listening habits and music genres in bipartite networks.

  2005cited by this paper
• The University of South Florida free association, rhyme, and word fragment norms

  2004cited by this paper
• Structural Holes and Good Ideas1

  2004cited by this paper
• Modularity from fluctuations in random graphs and complex networks.

  2004cited by this paper
• Fast algorithm for detecting community structure in networks.

  2003cited by this paper
• Assortative mixing in networks.

  2002cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Scientific collaboration networks. I. Network construction and fundamental results.

  2001cited by this paper
• Random graphs with arbitrary degree distributions and their applications.

  2000cited by this paper
• An Information Flow Model for Conflict and Fission in Small Groups

  1977cited by this paper
• A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory

  1975cited by this paper
• American Journal of Mathematics

  year unknowncited by this paper

• Link Fraction Mixed Membership Reveals Community Diversity in Aggregated Social Networks

  2026cites this paper
• Edge-dynamics consensus of matrix-weighted multi-agent systems

  2026cites this paper
• Designing topological cluster synchronization patterns with the Dirac operator.

  2025cites this paper
• A Novel Method for Community Detection in Bipartite Networks

  2025cites this paper
• Controllability analysis of macaque structural connectome from an edge centric perspective

  2025cites this paper
• Introducing and evaluating SWI-FEED: A smart water IoT framework designed for large-scale contexts

  2025cites this paper
• ComVis: a four-level prompt model for overlapping community detection with graph visualization

  2025cites this paper
• Succinct Link Transformation-Based Overlapping Community Detection Framework for Social Network Analysis

  2025cites this paper
• Clustering Edges Reveals How Vertices Exert Influence in Graph Data

  2025cites this paper
• Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering

  2025cites this paper
• Scaling Up k-Clique Percolation Community Detection

  2025cites this paper
• Edge-centric Brain Connectome Representations Reveal Increased Brain Functional Diversity of Reward Circuit in Patients with Major Depressive Disorder.

  2025cites this paper
• A cellular automaton towards structural balance - Long cycles of link dynamics

  2025cites this paper
• Controllability analysis of macaque structural connectome from an edge centric perspective

  2025cites this paper
• Hierarchical Single-Linkage Clustering for Community Detection with Overlaps and Outliers

  2025cites this paper
• Community detection for directed networks revisited using bimodularity

  2025cites this paper
• Model-based edge clustering for weighted networks with a noise component

  2025cites this paper
• Binary Flaw Detection: A Security Analysis Paper

  2025cites this paper
• Graph neural networks to model and optimize the operation of Water Distribution Networks: A review

  2025cites this paper
• From homophily to exclusion in small social systems.

  2025cites this paper
• Line Graph is the Key: An Exploration of Line Graph on Link Prediction with Social Networks

  2024cites this paper
• Intelligent mesh generation for crack simulation using graph neural networks

  2024cites this paper
• Hybrid Recommendation Algorithm based on Product Popularity and User Preference

  2024cites this paper
• GraphSmart: A Method for Green and Accurate IoT Water Monitoring

  2024cites this paper
• Optimization of Graph Clustering Inspired by Dynamic Belief Systems

  2024cites this paper
• Imputation of Time-varying Edge Flows in Graphs by Multilinear Kernel Regression and Manifold Learning

  2024cites this paper
• Hybrid of node and link communities for graphon estimation

  2024cites this paper
• RETRACTED: Survey on graph neural network-based community detection and its applications

  2024cites this paper
• Edge-centric network control on the human brain structural network

  2024cites this paper
• Exploring community detection methods and their diverse applications in complex networks: a comprehensive review

  2024cites this paper
• Automated detection of edge clusters via an overfitted mixture prior

  2024cites this paper
• Time Series Overlapping Clustering Based on Link Community Detection

  2024cites this paper
• Detecting communities in higher-order networks by using their derivative graphs

  2023cites this paper
• Application of a Dynamic Line Graph Neural Network for Intrusion Detection With Semisupervised Learning

  2023cites this paper
• The Map Equation Goes Neural

  2023cites this paper
• Encapsulation structure and dynamics in hypergraphs

  2023cites this paper
• Node Overlapping Detection for Draggable Node-Based Applications

  2023cites this paper
• Overlapping Graph Clustering in Attributed Networks via Generalized Cluster Potential Game

  2023cites this paper
• Hypotheses in urban ecology: building a common knowledge base

  2023cites this paper
• Hyperlink communities in higher-order networks

  2023cites this paper
• The structure and dynamics of networks with higher order interactions

  2023cites this paper
• Robust, scalable, and informative clustering for diverse biological networks

  2023cites this paper
• Edge-centric functional network analyses reveal disrupted network configuration in autism spectrum disorder.

  2023cites this paper
• A Heuristic Approach to Identify Influential Node in Complex Social Networks

  2023cites this paper
• DINE: Dimensional Interpretability of Node Embeddings

  2023cites this paper
• Overlapping communities and roles in networks with node attributes: Probabilistic graphical modeling, Bayesian formulation and variational inference

  2022cites this paper
• Detecting hierarchical organization of pervasive communities by modular decomposition of Markov chain

  2022influential citation
• Community detection algorithms for recommendation systems: techniques and metrics

  2022cites this paper
• Stratified Graph Spectra

  2022cites this paper
• CLCLP: Overlapping Community Detection in Networks Using a Combination of Link Community and Label Propagation Algorithm

  2022cites this paper
• Local dominance unveils clusters in networks

  2022cites this paper
• System-level high-amplitude co-fluctuations

  2022cites this paper
• Characterizing the fuzzy community structure in link graph via the likelihood optimization

  2022cites this paper
• IR Theory and the Core–Periphery Structure of Global IR: Lessons from Citation Analysis

  2022cites this paper
• An attentional-walk-based autoencoder for community detection

  2022cites this paper
• LazyFox: fast and parallelized overlapping community detection in large graphs

  2022cites this paper
• Link Partitioning on Simplicial Complexes Using Higher-Order Laplacians

  2022cites this paper
• A review of clique-based overlapping community detection algorithms

  2022cites this paper
• Derivative of a hypergraph as a tool for linguistic pattern analysis

  2022cites this paper
• AOC: Assembling overlapping communities

  2022cites this paper
• An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs

  2022cites this paper
• Modelling and Analysis of Probabilistic Networks

  2022cites this paper
• Rapid Detection of Local Communities in Graph Streams

  2022cites this paper
• OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree

  2022influential citation
• On Toeplitz graphs being line graphs

  2022cites this paper
• Unifying pairwise interactions in complex dynamics

  2022cites this paper
• Uncovering Local Hierarchical Overlapping Communities at Scale

  2022influential citation
• Know thy tools! Limits of popular algorithms used for topic reconstruction

  2022cites this paper
• Identifying Protein Complexes in Protein-protein Interaction Data using Graph Convolution Network

  2021cites this paper
• Sequential Motifs in Observed Walks

  2021cites this paper
• Overlapping Community Detection Based on Node Importance and Adjacency Information

  2021cites this paper
• Community Detection Algorithm Based on Intelligent Calculation of Complex Network Nodes

  2021cites this paper
• Efficient and accurate identification of protein complexes from protein-protein interaction networks based on the clustering coefficient

  2021cites this paper
• A new approach to combine multiplex networks and time series attributes: Building intrusion detection systems (IDS) in cybersecurity

  2021cites this paper
• Providing an Approach to Predicting Customer Quality in E-Commerce Social Networks Based on Big Data and Unsupervised Learning Method

  2021cites this paper
• APAL: Adjacency Propagation Algorithm for overlapping community detection in biological networks

  2021cites this paper
• Spatiotemporal analysis and the characteristics of the case transmission network of 2019 novel coronavirus disease (COVID-19) in Zhejiang Province, China

  2021cites this paper
• Identifying Protein Complexes in Protein-Protein Interaction Data Using Graph Convolutional Network

  2021cites this paper
• Toward Structural Controllability and Predictability in Directed Networks

  2021cites this paper
• Livestock Network Analysis for Rhodesiense Human African Trypanosomiasis Control in Uganda

  2021cites this paper
• Modularity maximization as a flexible and generic framework for brain network exploratory analysis

  2021cites this paper
• Edges in brain networks: Contributions to models of structure and function

  2021cites this paper
• Interacting brains revisited: A cross‐brain network neuroscience perspective

  2021cites this paper
• Network embedding from the line graph: Random walkers and boosted classification

  2021cites this paper
• Random line graphs and edge-attributed network inference

  2021cites this paper
• Multi-label classification and label dependence in in silico toxicity prediction.

  2021cites this paper
• Network of

  2021cites this paper
• A Local-Neighborhood Information Based Overlapping Community Detection Algorithm for Large-Scale Complex Networks

  2021cites this paper
• An edge-centric model for harmonizing multi-relational network datasets

  2021cites this paper
• FAIMCS: A fast and accurate influence maximization algorithm in social networks based on community structures

  2021cites this paper
• Nature inspired link prediction and community detection algorithms for social networks: a survey

  2021cites this paper
• Center–periphery structure in research communities

  2021cites this paper
• Overlapping community detection in complex networks using fuzzy theory, balanced link density, and label propagation

  2021cites this paper
• Finding the root graph through minimum edge deletion

  2021cites this paper
• Uncovering local community structure on line graph through degree centrality and expansion

  2021cites this paper
• Edge-centric network analysis

  2021influential citation
• The Online Social Networks Analysis: State of the Art

  2020cites this paper
• Persona2vec: a flexible multi-role representations learning framework for graphs

  2020cites this paper
• Hypergraph Learning with Line Expansion

  2020cites this paper
• Node-community membership diversifies community structures: An overlapping community detection algorithm based on local expansion and boundary re-checking

  2020cites this paper