Algebraic connectivity of graphs

By Miroslav Fiedler. 1973

How researchers see this paper

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

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “In this case p = ρ ( G ) / | E | , where ρ ( G ) denotes the algebraic connectivity of the network (Fiedler, 1973; Boyd et al., 2006; Loizou & Richt´arik, 2016).”
A tutorial on spectral clustering (2007, methodology): “For a proof using first step analysis for random walks see Fouss et al. (2006). There also exist other ways to express the commute distance with the help of graph Laplacians. For example a method in terms of eigenvectors of the normalized Laplacian Lsym can be found as Corollary 3.2 in Lovász (1993)”
Kernel methods in machine learning (2007, neutral): “Fiedler [49] showed that, the second largest eigenvector of L approximately decomposes the graph into two parts according to their sign.”
Community detection in graphs (2009, methodology): “In this case, if one aims at a split in n1 and n2 = n−n1 vertices, the best strategy is to order the components of the Fiedler vector from the lowest to the largest values and to put in one group the vertices corresponding to the first n1 components from the top or the bottom, and the remaining vert”
Modularity and community structure in networks. (2006, neutral): “Conflict of interest statement: No conflicts declared.”
Algebraic connectivity of directed graphs (2005, background): “Proof As in [1], the proof follows from the facts that LðGÞ þ LðGÞ 1⁄4 LK and xLKx 1⁄4 n for all x2P.”
On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs (2013, background): “As graphs are related to matrices [2,5,7–9], hypergraphs are related to tensors [11,13,16,20,21] which could reveal more higher order structures than matrices.”
Kernelized Sorting (2008, background): “, [21], [22], that local smoothness functionals on graphs can be expressed in terms of L.”
Spatial Networks (2010, background): “• The eigenvalue λ1 is called the algebraic connectivity [128] and plays an important role in the characterization of the graph and, roughly speaking, the larger λ1, the more connected the graph.”
Spectral clustering and the high-dimensional stochastic blockmodel (2010, methodology): “The algorithm has been redis-covered and reapplied in numerous diﬀerent ﬁelds since the initial work of Donath and Hoﬀman (1973) and Fiedler (1973).”
Learning with Hypergraphs: Clustering, Classification, and Embedding (2006, background): “One may construct an undirected graph in which two vertices are joined together by an edge if there is at least one common author of their corresponding articles (Figure 1), and then an undirected graph based clustering approach is applied, e.g. spectral graph techniques [7] [11] [16].”
Some necessary and sufficient conditions for second-order consensus in multi-agent dynamical systems (2010, methodology): “The consensus problem has attracted much attention partly because tools from algebraic graph theory (Fiedler, 1973) have been introduced successfully to construct conditions under which agents can reach an agreement on certain global criteria of common interest by sharing information locally with…”
Characterization of complex networks: A survey of measurements (2005, methodology): “, L = D −A, (63) or the Normal matrix, A˜ = D−1A, (64) where D is the diagonal matrix of vertex degrees with elements dii = P j aij, dij = 0 for i 6= j. A particular method, called spectral bisection [131, 132, 130], is based on the diagonalization of the Laplacian matrix. If the network is separate”