Community structure in directed networks.

By Elizabeth A. Leicht, Mark Newman. Physical Review Letters, 2007

1,126 citations recorded by the source corpus.

We consider the problem of finding communities or modules in directed networks. In the past, the most common approach to this problem has been to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used community finding technique of modularity maximization can be generalized in a principled fashion to incorporate information contained in edge directions. We describe an explicit algorithm based on spectral optimization of the modularity and show that it gives demonstrably better results than previous methods on a variety of test networks, both real and computer generated.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

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

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

Illuminating search spaces by mapping elites (2015, methodology): “…so, we can create a 2D feature space where the ﬁrst feature dimension ( x axis) is connection cost (the sum of the squared length of the connections in a network 32 ), and the second feature dimension is network modularity (computed using an efﬁcient approximation of Newman’s modularity score 45 ).”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “For instance, although it has been argued [64], [65] that the null configuration model in modularity should become dind T out=2m in order to account for the directionality of the links, this choice and justification of the null model for directed graphs is not unique.”
Dispersal connectivity and reserve selection for marine conservation (2011, background): “Algorithms that attempt to split a network into a series of structural units, are based on a heuristic mechanism that seeks to formalise the basis of what constitutes a ‘good’ community (Newman, 2006; Leicht and Newman, 2008; Butts, 2009).”
Network-Based Functional Regions (2011, methodology): “Again, this can be extended to directed networks (which will be the focus for the remainder of this paper) by symmetrising B using the procedure presented in Leicht and Newman (2008) to obtain Q 1 4w sT Bÿ BT s .”
A classification for community discovery methods in complex networks (2011, methodology): “In [88] the modularity maximization approach is adapted to the case of a directed network.”
A smart local moving algorithm for large-scale modularity-based community detection (2013, background): “These variants for instance deal with directed or weighted networks (Leicht & Newman, 2008; Newman, 2004b), or they offer a resolution parameter (Reichardt & Bornholdt, 2006) that makes it possible to customize the granularity level at which communities are detected and to mitigate the so-called…”
Modular Brain Networks (2015, background): “Whereas this description of Q is suitable for undirected networks, the form of the quality function Q can be easily adapted to work for weighted and directed networks (Leicht & Newman 2008).”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “Newman and Leicht [94] proposed an approach for community detection in directed networks based on mixture models for statistical inference.”
Communities in Networks (2009, methodology): “on bipartite networks rather than on their unipartite projections [10,53,71,100]. Even fewer community-detection methods are able to handle directed networks (whose adjacency matrices are asymmetric) [53,72] or signed networks (whose connections might be “attracting” or “repelling”) [121]. Moreover,”
Diffusion-based neuromodulation can eliminate catastrophic forgetting in simple neural networks (2017, methodology): “Structural modularity is quantified with the Q-Score metric [40].”
Small and flat worlds: A complex network analysis of international trade in crude oil (2015, background): “Up to a multiplicative constant, modularity Q refers to the number of edges falling within a group minus the expected number in an equivalent network with edges placed at random [28].”
The evolutionary origins of modularity (2012, methodology): “Network modularity is evaluated with an efficient approximation [33,34] of the widely used modularity metric Q, which first optimally divides networks into modules then measures the difference between the number of edges within each module and the number expected for random networks with the same nu”
Conserved and variable architecture of human white matter connectivity (2011, neutral): “…local efficiency (Latora and Marchiori, 2001; Achard and Bullmore, 2007; Bassett et al., 2009), betweenness centrality (Freeman, 1977), modularity (Leicht and Newman, 2008; Meunier et al., 2009b), hierarchy (Ravasz and Barabasi, 2003; Bassett et al., 2008), synchronizability (Barahona and Pecora,…”
Complex network measures of brain connectivity: Uses and interpretations (2010, background): “Weighted modularity (Newman, 2004), P (cid:8) (cid:9) Directed modularity (Leicht and Newman, 2008),”
Extending the definition of modularity to directed graphs with overlapping communities (2008, background): “Initially deﬁned for undirect networks, the deﬁnition of modularity has been subsequently extended to capture community structure in directed networks ([9], [1], [12]).”
Altered Resting State Complexity in Schizophrenia (2011, background): “125 Hz) oscillations in the BOLD signal which have previously been shown to be particularly sensitive to disease-related alterations in schizophrenia (Lynall et al., 2010). Consistent with Lynall et al. (2010), our data revealed that this frequency band was most sensitive to group differences in ave”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “Moreover, by ignoring edge directedness important information may be lost, especially if relationships are predominantly non-reciprocal as in predator-prey networks [26] or in social networks like Twitter.”