Laplacians and the Cheeger Inequality for Directed Graphs

By Fan Chung. 2005

612 citations recorded by the source corpus.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

How researchers see this paper

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

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, background): “Some clear extensions of this framework include: 1) considering directed graphs, as is done for example in [66]; 2) considering time series of data on each vertex in a graph; 3) considering a time-varying series of underlying graphs, as is done for example in [67]; or any combination of these.”
Spectral Graph Theory (2012, methodology): “Using this Laplacian, she derives analogs of Cheeger’s inequality, defining conductance by counting edges by the probability they appear in a random walk [95].”
Interlacing for weighted graphs using the normalized Laplacian (2007, background): “For instance it can be shown that the Cheeger inequality established for the directed graph $ G in Chung [3] is equivalent to the already known Cheeger inequality for the undirected graph H defined in Lemma 4.”
Mathematical Aspects of Mixing Times in Markov Chains (2006, result): “This gives an alternate proof of a result of [17], which argued as in a standard proof of Cheeger’s inequality but with a specialized Laplacian for non-reversible chains.”
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, background): “One can then define the following variation functional for signals on directed graphs [27], [28]:”
An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification (2012, background): “The resulting kernel on graphs is a normalized version of the ‘‘regularized Laplacian kernel’’ involving the extension of the Laplacianmatrix for directed graphs (Chung, 2005).”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “to introduce definitions appropriate for directed graphs as well [89], [90].”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “The authors are based on the extension of Laplacian matrix for directed networks proposed by Chung [17] (see 4.4.3 for more details on the Laplacian matrix) L = Π− ΠP + P TΠ 2 , (7) where P is the transition matrix of the random walk and Π = diag(π1, π2, . . . , πn) the diagonal matrix with the prob”
Commute Times for a Directed Graph using an Asymmetric Laplacian (2011, methodology): “In [9], they use both L and L, referring to L as the “combinatorial Laplacian” and reserving the name of just “Laplacian” to our diagonally scaled version L.”
Learning from labeled and unlabeled data on a directed graph (2005, background): “which is just the Laplacian matrix for directed graphs proposed by Chung (2005) .”
PageRank beyond the Web (2014, methodology): “While these graphs were undirected, later work [Zhou et al., 2005] showed how to use PageRank with global teleportation, in concert with symmetric Laplacian structure deﬁned on a directed graph [Chung, 2005], to enable the same methodology on a general directed graph.”
Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks (2013, background): “We ﬁnally note that for | λ 2 | = | λ 3 | , a similar slow-down ratio can be derived for the chi-square distance based on the upper bounds on the second-largest eigenvalues for general directed networks with arbitrary eigenvalue spectra following the arguments put forth in [25].”
Non-backtracking random walks and a weighted Ihara's theorem (2016, background): “In [4], the Laplacian for a directed graph is defined as follows.”
Spectral Embedding of Signed Networks (2015, background): “Subsequently, many extensions of spectral clustering approaches have been developed, including directed spectral embedding based on a random walk strategy [3], and weighted cut clustering in directed graphs [12].”
Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes (2007, background): “It is possible to model non-symmetric actions and policies using more sophisticated symmetrization procedures (Chung, 2005), and we postpone discussion of this extension to Section 9.”
On the mathematics of emergence (2007, methodology): “Our use of the word “Laplacian” in this context follows the one in [1] rather than the one in [4].”
Eigenvalues and structures of graphs (2008, methodology): “Recently Chung [12] defined a Laplacian for aperiodic strongly connected directed graphs and showed connections of its spectrum to mixing rates of random walks and isoperimetric properties, and in a subsequent paper gave a further connection to the”
Signals on Graphs: Uncertainty Principle and Sampling (2015, background): “In the following, after introducing the notation, we brieﬂy recall the background of graph signal processing and then we highlight the speciﬁc contributions of this paper.”