Line Graphs, Link Partitions and Overlapping Communities

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 which 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.

9 pages, 7 figures. Version 2 includes minor changes to text and references and some improved figures

References in corpus (15)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• How to project a bipartite network?
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Analysis of the structure of complex networks at different resolution levels
• Extending the definition of modularity to directed graphs with overlapping communities
• Modularity-Maximizing Network Communities via Mathematical Programming
• Communities, Knowledge Creation, and Information Diffusion
• Uncovering collective listening habits and music genres in bipartite networks

Cited by in corpus (105)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Random walks and diffusion on networks
• Memory in network flows and its effects on spreading dynamics and community detection
• An efficient and principled method for detecting communities in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Explosive higher-order Kuramoto dynamics on simplicial complexes
• Fundamental structures of dynamic social networks
• A Classification for Community Discovery Methods in Complex Networks
• Characterizing the community structure of complex networks
• Topological Signal Processing over Simplicial Complexes
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Clique Graphs and Overlapping Communities
• Line Graphs of Weighted Networks for Overlapping Communities
• Brain Network Adaptability Across Task States
• Quantifying and identifying the overlapping community structure in networks
• Faster unfolding of communities: speeding up the Louvain algorithm
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Connect and win: The role of social networks in political elections
• Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction
• Flow graphs: interweaving dynamics and structure
• Map equation for link community
• Exploring the Evolution of London's Street Network in the Information Space: a Dual Approach
• Multilink Communities of Multiplex Networks
• The stability of a graph partition: A dynamics-based framework for community detection
• Local dominance unveils clusters in networks
• Individual Differences in Dynamic Functional Brain Connectivity Across the Human Lifespan
• Uncovering the community structure associated with the diffusion dynamics of networks
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Bloggers Behavior and Emergent Communities in Blog Space
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Communities in Networks
• Universality of Performance Indicators based on Citation and Reference Counts
• Using higher-order Markov models to reveal flow-based communities in networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• Quantitative Analysis of Bloggers Collective Behavior Powered by Emotions
• The Grand Canonical ensemble of weighted networks
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping Community Discovery Methods: A Survey
• Interactions In Space For Archaeological Models
• Memetic search for overlapping topics based on a local evaluation of link communities
• Clustering in random line graphs
• Organization of networks with tagged nodes and biased links: a priori distinct communities. The case of Intelligent Design Proponents and Darwinian Evolution Defenders
• Center-Periphery Structure in Communities: Extracellular Vesicles
• Hyperlink communities in higher-order networks
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Discovering link communities in complex networks by exploiting link dynamics
• Line graphs as social networks
• Emergence of Blind Areas in Information Spreading
• Finding overlapping communities in multiplex networks
• Fragmentation transition in a coevolving network with link-state dynamics
• Dynamics of link states in complex networks: The case of a majority rule
• Growing networks of overlapping communities with internal structure
• Perception, Prestige and PageRank
• Topics as Clusters of Citation Links to Highly Cited Sources: The Case of Research on International Relations
• Atomic subgraphs and the statistical mechanics of networks
• Link community detection through global optimization and the inverse resolution limit of partition density
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Generalized Markov stability of network communities
• Derivative of a hypergraph as a tool for linguistic pattern analysis
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree
• Criterions for locally dense subgraphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Community detection for directed networks revisited using bimodularity
• Assortativity in random line graphs
• The Limitations of Simple Gene Set Enrichment Analysis Assuming Gene Independence
• Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm
• Modeling Social Networks with Overlapping Communities Using Hypergraphs and Their Line Graphs
• AOC; Assembling Overlapping Communities
• On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
• The Atlas for the Aspiring Network Scientist
• Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
• Diffusion in Networks With Overlapping Community Structure
• Partitioning Breaks Communities
• The adjacency matrix and the discrete Laplacian acting on forms
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Theory of Interface: Category Theory, Directed Networks and Evolution of Biological Networks
• Providing an Approach to Predicting Customer Quality in E-Commerce Social Networks Based on Big Data and Unsupervised Learning Method
• Percolation Computation in Complex Networks
• Designing topological cluster synchronization patterns with the Dirac operator
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Clustering evolving data using kernel-based methods
• weg2vec: Event embedding for temporal networks
• Identifying edge clusters in networks via edge graphlet degree vectors (edge-GDVs) and edge-GDV-similarities
• Toward Edge-Centric Network Embeddings
• A Threshold For Clusters in Real-World Random Networks
• Identification of hybrid node and link communities in complex networks
• Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering
• Bayesian Modeling of Random Walker for Community Detection in Networks
• Coactivated Clique Based Multisource Overlapping Brain Subnetwork Extraction
• Time and Citation Networks
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Overlapping Community Detection Optimization and Nash Equilibrium
• Model-based edge clustering for weighted networks with a noise component