Sharp Davies-Gaffney-Grigor'yan Lemma on Graphs
In this note, we prove the sharp Davies-Gaffney-Grigor'yan lemma for minimal heat kernels on graphs.
Source author record
Frank Bauer
Frank Bauer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
13works
14topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
13 published item(s)
preprint2015arXiv
Davies-Gaffney-Grigor'yan Lemma on Graphs
We prove a variant of the Davies-Gaffney-Grigor'yan Lemma for the continuous time heat kernel on graphs. We use it together with the Li-Yau inequality to obtain strong heat kernel estimates for graphs satisfying the exponential curvature dimension inequality.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Li-Yau inequality on graphs
We prove the Li-Yau gradient estimate for the heat kernel on graphs. The only assumption is a variant of the curvature-dimension inequality, which is purely local, and can be considered as a new notion of curvature for graphs. We compute this curvature for lattices and trees and conclude that it behaves more naturally than the already existing notions of curvature. Moreover, we show that if a graph has non-negative curvature then it has polynomial volume growth. We also derive Harnack inequalities and heat kernel bounds from the gradient estimate, and show how it can be used to strengthen the classical Buser inequality relating the spectral gap and the Cheeger constant of a graph.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
We prove the following estimate for the spectrum of the normalized Laplace operator $Δ$ on a finite graph $G$, \begin{equation*}1- (1- k[t])^{\frac{1}{t}}\leq λ_1 \leq \cdots \leq λ_{N-1}\leq 1+ (1- k[t])^{\frac{1}{t}}, \,\forall \,\,\text{integers}\,\, t\geq 1. \end{equation*} Here $k[t]$ is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph $G[t]$, which was introduced by Bauer-Jost. In particular, when $t=1$ this is Ollivier's estimates $k\leq λ_1\leq \ldots \leq λ_{N-1}\leq 2-k$. For sufficiently large $t$ we show that, unless $G$ is bipartite, our estimates for $λ_1$ and $λ_{N-1}$ are always nontrivial and improve Ollivier's estimates for all graphs with $k\leq 0$. By definition neighborhood graphs are weighted graphs which may have loops. To understand the Ollivier-Ricci curvature on neighborhood graphs, we generalize a sharp estimate of the Ricci curvature given by Jost-Liu to weighted graphs with loops and relate it to the relative local frequency of triangles and loops.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian
We study the spectrum of the normalized Laplace operator of a connected graph $Γ$. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose $Γ$ into two large pieces, whereas the largest eigenvalue controls how close $Γ$ is to being bipartite. The smallest eigenvalue can be controlled by the Cheeger constant, and we establish a dual construction that controls the largest eigenvalue. Moreover, we find that the neighborhood graphs $Γ[l]$ of order $l\geq2$ encode important spectral information about $Γ$ itself which we systematically explore. In particular, the neighborhood graph method leads to new estimates for the smallest nontrivial eigenvalue that can improve the Cheeger inequality, as well as an explicit estimate for the largest eigenvalue from above and below. As applications of such spectral estimates, we provide a criterion for the synchronizability of coupled map lattices, and an estimate for the convergence rate of random walks on graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Cheeger inequalities for unbounded graph Laplacians
We use the concept of intrinsic metrics to give a new definition for an isoperimetric constant of a graph. We use this novel isoperimetric constant to prove a Cheeger-type estimate for the bottom of the spectrum which is nontrivial even if the vertex degrees are unbounded.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
We introduce a new method to efficiently approximate the number of infections resulting from a given initially-infected node in a network of susceptible individuals. Our approach is based on counting the number of possible infection walks of various lengths to each other node in the network. We analytically study the properties of our method, in particular demonstrating different forms for SIS and SIR disease spreading (e.g. under the SIR model our method counts self-avoiding walks). In comparison to existing methods to infer the spreading efficiency of different nodes in the network (based on degree, k-shell decomposition analysis and different centrality measures), our method directly considers the spreading process and, as such, is unique in providing estimation of actual numbers of infections. Crucially, in simulating infections on various real-world networks with the SIR model, we show that our walks-based method improves the inference of effectiveness of nodes over a wide range of infection rates compared to existing methods. We also analyse the trade-off between estimate accuracy and computational cost, showing that the better accuracy here can still be obtained at a comparable computational cost to other methods.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Normalized graph Laplacians for directed graphs
We consider the normalized Laplace operator for directed graphs with positive and negative edge weights. This generalization of the normalized Laplace operator for undirected graphs is used to characterize directed acyclic graphs. Moreover, we identify certain structural properties of the underlying graph with extremal eigenvalues of the normalized Laplace operator. We prove comparison theorems that establish a relationship between the eigenvalues of directed graphs and certain undirected graphs. This relationship is used to derive eigenvalue estimates for directed graphs. Finally we introduce the concept of neighborhood graphs for directed graphs and use it to obtain further eigenvalue estimates.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On the $l^p$ spectrum of Laplacians on graphs
We study the $p$-independence of spectra of Laplace operators on graphs arising from regular Dirichlet forms on discrete spaces. Here, a sufficient criterion is given solely by a uniform subexponential growth condition. Moreover, under a mild assumption on the measure we show a one-sided spectral inclusion without any further assumptions. We study applications to normalized Laplacians including symmetries of the spectrum and a characterization for positivity of the Cheeger constant. Furthermore, we consider Laplacians on planar tessellations for which we relate the spectral $p$-independence to assumptions on the curvature.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
The dual Cheeger constant and spectra of infinite graphs
In this article we study the top of the spectrum of the normalized Laplace operator on infinite graphs. We introduce the dual Cheeger constant and show that it controls the top of the spectrum from above and below in a similar way as the Cheeger constant controls the bottom of the spectrum. Moreover, we show that the dual Cheeger constant at infinity can be used to characterize that the essential spectrum of the normalized Laplace operator shrinks to one point.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Applying Lepskij-Balancing in Practice
In a stochastic noise setting the Lepskij balancing principle for choosing the regularization parameter in the regularization of inverse problems is depending on a parameter $τ$ which in the currently known proofs is depending on the unknown noise level of the input data. However, in practice this parameter seems to be obsolete. We will present an explanation for this behavior by using a stochastic model for noise and initial data. Furthermore, we will prove that a small modification of the algorithm also improves the performance of the method, in both speed and accuracy.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Parameter Choice by Fast Balancing
Choosing the regularization parameter for inverse problems is of major importance for the performance of the regularization method. We will introduce a fast version of the Lepskij balancing principle and show that it is a valid parameter choice method for Tikhonov regularization both in a deterministic and a stochastic noise regime as long as minor conditions on the solution are fulfilled.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Synchronized chaos in networks of simple units
We study synchronization of non-diffusively coupled map networks with arbitrary network topologies, where the connections between different units are, in general, not symmetric and can carry both positive and negative weights. We show that, in contrast to diffusively coupled networks, the synchronous behavior of a non-diffusively coupled network can be dramatically different from the behavior of its constituent units. In particular, we show that chaos can emerge as synchronized behavior although the dynamics of individual units are very simple. Conversely, individually chaotic units can display simple behavior when the network synchronizes. We give a synchronization criterion that depends on the spectrum of the generalized graph Laplacian, as well as the dynamical properties of the individual units and the interaction function. This general result will be applied to coupled systems of tent and logistic maps and to two models of neuronal dynamics. Our approach yields an analytical understanding of how simple model neurons can produce complex collective behavior through the coordination of their actions.
0 citations0 reviewsNo code linkedOpen access