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 (8)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of 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

Cited by in corpus (24)

• Finding statistically significant communities in networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• A Classification for Community Discovery Methods in Complex Networks
• Characterizing the community structure of complex networks
• Clique Graphs and Overlapping Communities
• Brain Network Adaptability Across Task States
• Quantifying and identifying the overlapping community structure in networks
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping Community Discovery Methods: A Survey
• Discovering link communities in complex networks by exploiting link dynamics
• Dynamics of link states in complex networks: The case of a majority rule
• Assortativity in random line graphs
• Modeling Social Networks with Overlapping Communities Using Hypergraphs and Their Line Graphs
• Theory of Interface: Category Theory, Directed Networks and Evolution of Biological Networks
• The adjacency matrix and the discrete Laplacian acting on forms
• Clustering evolving data using kernel-based methods
• Identifying edge clusters in networks via edge graphlet degree vectors (edge-GDVs) and edge-GDV-similarities
• Percolation Computation in Complex Networks
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Overlapping Community Detection Optimization and Nash Equilibrium
• Time and Citation Networks
• A Threshold For Clusters in Real-World Random Networks