Source-linked AI summary
Line Graphs of Weighted Networks for Overlapping Communities
T. S. Evans, R. Lambiotte
TL;DR
Node partitions cannot represent networks in which vertices belong to multiple communities. The paper partitions edges by applying traditional vertex-partitioning methods to weighted line graphs, and its examples show overlapping communities in social and geographical networks.
Problem
Node partitioning assigns each vertex to one community, so it cannot represent networks where vertices belong to several communities.
Source: §1 · p. 1Method
The approach constructs weighted line graphs, whose nodes represent original links, and applies vertex partitioning to partition the original network's edges.
Source: §1 · pp. 1–2Results
The character and Aegean-site examples produce overlapping communities, including five geographical groups and a distinct role for Akrotiri not apparent in the distance dendrogram.
Source: Literary Characters Coappearance · p. 5, Clustering Non Negative Matrices · pp. 5–6Takeaways & Limitations
Edge partitions naturally yield overlapping communities and can reveal hierarchical organization through nested partitions at different dendrogram levels.
Source: §1 · p. 2The standard unweighted line graph overrepresents hubs: a degree-k vertex contributes k(k −1)/2 edges rather than a number proportional to k.
Source: Random walk on the edges and weighted… · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
The paper shifts network analysis from vertices to edges, proposing weighted line graphs as a way to avoid high-degree bias. It uses edge partitions to detect overlapping communities that node partitions cannot represent.
An edge-centric representation
- Weighted line graphs retain the topology of standard line graphs while using weights to avoid bias toward high-degree vertices in the original graph.The authors present them as a general framework for shifting from a vertex-centric to an edge-centric view.Source: §1 · p. 1
Motivation and prior approaches
- The paper frames community detection as a way to find highly connected modules, which may correspond to functional sub-units.It also describes prior approaches to overlapping communities, including limitations of k-clique percolation on weighted and multi-scale networks.Source: §1 · pp. 1–2
The limits of node partitioning
- Node partitions assign each vertex to one module, making them unsuitable when nodes belong to multiple communities, as often occurs at module interfaces or throughout a network.The paper notes examples in social and biological networks, where relationships or proteins can span several communities.Source: §1 · p. 1
Edge partitions and overlap
- Because links often represent one interaction type, partitioning links lets incident edges belong to different modules and thus yields overlapping node communities.The framework applies standard vertex-partitioning methods to weighted line graphs and can be generalized to weighted or directed networks.Source: §1 · p. 2
- Dendrogram levels provide nested edge partitions, making the approach capable of revealing hierarchical, overlapping structure at multiple scales.The paper motivates community detection by noting that network modules can themselves be modular.Source: §1 · pp. 1–2
2 Simple Graphs G
The section introduces line graphs as edge-centric representations and relates their random walks to processes on the original graph. It contrasts the standard line graph's hub bias with a weighted construction designed to represent edge relations more appropriately.
Overview
- The overview uses the incidence-matrix representation of G and random walks to motivate line-graph weights; Newman-Girvan modularity is also interpreted through walker probabilities.The modularity interpretation compares the probability that a walker remains in a community over two successive steps with the corresponding independent-walker probability.Source: Overview · p. 2
Random walk on the edges and weighted line graphs
- The standard line graph maps original edges to vertices, but a degree-k original vertex contributes k(k −1)/2 line-graph edges, overemphasizing hubs relative to their degree k.The usual random walk on this line graph corresponds to a link-link random walk on original edges.Source: Random walk on the edges and weighted… · p. 3
- D(G) is proposed as a weighted line graph whose usual vertex random walk corresponds to a link-node-link walk on the original graph.That walk moves from an edge to one of its endpoints and then to another incident edge; Fig. 1 depicts the equivalence.Source: Random walk on the edges and weighted… · p. 3, Figure 1 · p. 3
Central idea
- Choosing a projection is essential because different line graphs encode different edge relations and dynamics; for simple graphs, D(G) is preferred to C(G) to avoid node bias.Fig. 2 illustrates a weighted, undirected network transformed into a weighted, directed line graph.Source: Central idea · p. 3, Figure 2 · p. 4
3 Undirected Weighted Graphs G
The section extends line-graph construction to weighted undirected graphs, then corrects a weighted projection that overemphasizes high-strength vertices. The chosen adjacency represents edge-to-edge random-walker transitions.
3 Undirected Weighted Graphs G
- The weighted incidence matrix ˜B records edge weights alongside binary incidence B, generalizing the line-graph construction to weighted graphs.The usual unweighted line graph uses B alone and records only the original graph’s topology.Source: §3 · p. 4
- The logical weighted generalization C(G) is directed even when G is undirected; E(G) reduces to the weighted line graph in for unweighted G and is directed and weighted for weighted G.If the original graph is ergodic, E(G) is also ergodic.Source: §3 · p. 4
- The initial weighted projection makes a vertex of degree k and strength s contribute O(ks), overemphasizing high-degree, high-strength vertices; the correction reduces assigned link weights by O(s^-1).This strength-based reduction motivates the subsequent adjacency definition.Source: §3 · p. 4
- The chosen adjacency models a walker moving from edge β to an endpoint and then to edge α, with transition probability proportional to the target edge’s weight and independent of the current edge’s weight.The walker first chooses either endpoint of edge β with equal probability; the target edge is then chosen in proportion to its weight.Source: §3 · p. 4
4 Applications
The applications partition vertices of weighted line graphs to identify communities of original edges, allowing original nodes to participate in multiple communities. Examples on Aegean sites, literary characters, and coauthorship networks illustrate this perspective.
4 Applications
- The method partitions weighted-line-graph vertices to partition original edges, approximately maximizing random-walk modularity with Louvain; directed line graphs require a nontrivial equilibrium walker distribution.The equilibrium distribution is computed with the power method.Source: §4 · pp. 4–5
Literary Characters Coappearance
- Valjean connects to all but one community, while the edge partition shows that the strength of his connections varies significantly.Edges link characters appearing together, weighted by the number of chapters in which they both appear.Source: Literary Characters Coappearance · p. 5, Figure 3 · p. 5
Clustering Non Negative Matrices
- The distance-weighted Aegean graph yields five communities, with Akrotiri in both Cycladean and Cretan groups; that role is absent from the distance-matrix dendrogram.The graph uses distances between sites to assign edge weights, while the dendrogram groups sites by average distance.Source: Clustering Non Negative Matrices · pp. 5–6, Figure 4 · p. 6, Figure 5 · p. 6
Academic Coauthorship
- In the coauthorship network, productive scientists focus on one community, while less prominent researchers often link groups, recalling Granovetter’s strength of weak links.The network weights each coauthorship by (k −1)−1 for a paper with k authors.Source: Academic Coauthorship · p. 6, Figure 6 · p. 6
5 Possible generalisations
The paper outlines extensions of its line-graph formalism to self-loops, multigraphs, and directed graphs. For directed graphs, the described construction makes link-node-link walks correspond to usual vertex walks.
5 Possible generalisations
- Self-loops in line graphs let a random walker return to the edge it started from; whether this is preferable depends on context.The authors note that self-loops are also used to alter community-detection resolution.Source: §5 · p. 7
- Multigraphs can represent a relationship belonging to multiple communities by splitting it into edges whose weights sum to the original edge’s weight.For example, two colleagues may share both a work connection and a hobby.Source: §5 · p. 7
- For directed graphs without self-loops, the link-node-link walk matches the usual vertex walk, making modularities for D(G), E(G), and F(G) identical.The authors note that whether the small differences in implicit random walks affect network analysis is unclear.Source: §5 · p. 7
6 Conclusion
The paper extends line graphs from unweighted to weighted graphs, shifting attention from vertices to edges. In community detection, partitioning a line graph’s vertices yields an edge partition that can represent overlapping communities.
6 Conclusion
- The authors extend line graphs from unweighted to weighted graphs, constructing line graphs that are both weighted and directed.The procedure shifts focus from vertices to edges for graph-based problems.Source: §6 · p. 7
- Partitioning line-graph vertices with a standard algorithm directly produces an optimal edge partition of the original graph, naturally allowing overlapping communities.The stated cost is roughly O(⟨k^2⟩/⟨k⟩) in memory and time, with minimal code-development effort.Source: §6 · p. 7
- Codes for constructing weighted line graphs and optimising modularity are freely available.The paper provides download locations for both tasks.Source: §6 · p. 7