Line graphs, link partitions, and overlapping communities.

By Tim S. Evans, Renaud Lambiotte. Physical review. E, Statistical, nonlinear, and soft matter physics, 2009

606 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c374d289a3771ca88d0fa2bdd29399ca615ad30e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Memory in network flows and its effects on spreading dynamics and community detection (2013, methodology): “of flow were tracked for all journals in both M1 and M2: (1) quality flow from the top ten journals (green) or all other journals (yellow), (2) internal flow”
An efficient and principled method for detecting communities in networks (2011, methodology): “Previous approaches to the discovery of link communities have made use of heuristic quality functions optimized over possible partitions of a network’s edges [9, 10].”
Random walks and diffusion on networks (2016, methodology): “ijand # jito each pair of adjacent nodes v iand v jin the original network, because a memory node encodes the time ordering of visits. The number of edges in a memory network is proportional to hk2iN[254]. To improve accuracy, one can also examine memory networks in the form of higher-order Markov c”
A classification for community discovery methods in complex networks (2011, methodology): “L in k Link modularity X X X O(2mk logn) 20k 127k 2009 [50] HLC* X X X O(nK̄(2)) 885k 5.”
Modular Brain Networks (2015, methodology): “The simplest approach is the one advocated by Evans & Lambiotte (2009), which assigns weights to the connections via a normalization step and then applies nonoverlapping community detection methods (e.g., modularity maximization) to the resulting line graph's connectivity matrix.”
Modular and Hierarchically Modular Organization of Brain Networks (2010, methodology): “…modularity, let us also mention methods aiming at uncovering hierarchies made of overlapping communities by partitioning the links of the network (Evans and Lambiotte, 2009; Ahn et al., 2010), as well as methods based on the likelihood of hierarchical random graphs to have generated the system…”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, neutral): “ nodespace. On the one hand, we may dene a random walk on the edges, where the edges themselves are dened as the states of the Markov process, e.g., by invoking constructions such as the line-graph [1,30]. However, this means we eectively abandon the connection to algebraic topology and the Hodge La”
Scalable Learning of Collective Behavior (2012, methodology): “Recently, a simple scheme proposed to detect overlapping communities is to construct a line graph and then apply graph partition algorithms [16], [17].”
Communities in Networks (2009, methodology): “ oftechniques in oursurvey below, there are of course numerous other methods—including ones based on maximum likelihood [23], mathematical programming [1], block modeling [105,127], link partitioning [2,33], inference methods [56,91], latent space clustering [55], and more—that we unfortunately negl”
Multirelational organization of large-scale social networks in an online world (2010, background): “Most empirical studies of large-scale social networks focus on node properties [5], for instance to uncover the topological centrality of social agents or patterns of homophily between agents [40], while being blind to the multiple nature of the links connecting agents.”
Community detection in graphs (2009, background): “Evans and Lambiotte optimized the three corresponding modularity functions to look for partitions in two real networks, Zachary’s karate club (Zachary, 1977) (Section XV.”
Community detection in networks: A user guide (2016, background): “It has been pointed out that overlapping communities, especially in social networks, reflect different types of associations between people (Ahn et al., 2010; Evans and Lambiotte, 2009).”
Community detection in social networks (2016, background): “In an extension to this work, Evans et al. 79 used weighted line graphs.”
Finding Statistically Significant Communities in Networks (2010, neutral): “In such cases communities are overlapping (and partitions become covers) and very few methods account for this possibility [18–25], which considerably increases the complexity of the problem.”