Line graphs, link partitions, and overlapping communities

2009/03/31 by Tim Evans, T. S. Evans, Renaud Lambiotte +1 · 10 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Caching and Content Delivery #Combinatorics #Community structure #Complex Network Analysis Techniques #Complex network #Computer network #Computer science #Engineering #Frequency partition of a graph #Graph #Graph partition #Line graph #Link (geometry) #Mathematics #Network partition #Node (physics) #Partition (number theory) #Peer-to-Peer Network Technologies #Theoretical computer science #World Wide Web #physics.data-an #physics.soc-ph

paper · pdf · doi:10.1103/physreve.80.016105

published as Phys.Rev.E, 2009, 80, 016105 · 9 pages, 7 figures. Version 2 includes minor changes to text and references and some improved figures

openalex publication_date 2009/07/09 · arxiv created 2009/07/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]
• Community structure in social and biological networks
• Structural Holes and Good Ideas
• Assortative Mixing in Networks
• Uncovering collective listening habits and music genres in bipartite networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maximal Flow Through a Network
• Congruent Graphs and the Connectivity of Graphs

Cited by

• Line graphs of weighted networks for overlapping communities
• Clique graphs and overlapping communities
• Connect and win: The role of social networks in political elections
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Fragmentation transition in a coevolving network with link-state dynamics
• Partitioning Breaks Communities
• Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian
• Communities as Well Separated Subgraphs with Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Line graph [wikipedia]

Related

• Line graphs of weighted networks for overlapping communities
• Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
• Partitioning Breaks Communities
• Map equation for link community
• Overlapping community detection in networks based on link partitioning and partitioning around medoids