Line Graphs of Weighted Networks for Overlapping Communities

Abstract

In this paper, we develop the idea to partition the edges of a weighted graph in order to uncover overlapping communities of its nodes. Our approach is based on the construction of different types of weighted line graphs, i.e. graphs whose nodes are the links of the original graph, that encapsulate differently the relations between the edges. Weighted line graphs are argued to provide an alternative, valuable representation of the system's topology, and are shown to have important applications in community detection, as the usual node partition of a line graph naturally leads to an edge partition of the original graph. This identification allows us to use traditional partitioning methods in order to address the long-standing problem of the detection of overlapping communities. We apply it to the analysis of different social and geographical networks.

8 Pages. New title and text revisions to emphasise differences from earlier papers

References in corpus (18)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Line Graphs, Link Partitions and Overlapping Communities
• Analysis of the structure of complex networks at different resolution levels
• Extending the definition of modularity to directed graphs with overlapping communities
• Random planar graphs and the London street network
• Quantifying and identifying the overlapping community structure in networks
• Majority Model on a network with communities
• Detection of node group membership in networks with group overlap
• Two complementary representations of a scale-free network
• Clustering under the line graph transformation: Application to reaction network

Cited by in corpus (28)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Uncovering space-independent communities in spatial networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Higher-order simplicial synchronization of coupled topological signals
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
• Local dominance unveils clusters in networks
• Graph-based Semi-Supervised & Active Learning for Edge Flows
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Universality of Performance Indicators based on Citation and Reference Counts
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping Community Discovery Methods: A Survey
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Discovering link communities in complex networks by exploiting link dynamics
• Fragmentation transition in a coevolving network with link-state dynamics
• Dynamics of link states in complex networks: The case of a majority rule
• Link community detection through global optimization and the inverse resolution limit of partition density
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels
• Derivative of a hypergraph as a tool for linguistic pattern analysis
• Beyond Node Embedding: A Direct Unsupervised Edge Representation Framework for Homogeneous Networks
• Designing topological cluster synchronization patterns with the Dirac operator
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Model-based edge clustering for weighted networks with a noise component
• Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering
• Time and Citation Networks