The Experts below are selected from a list of 18195 Experts worldwide ranked by ideXlab platform
Olivia Simpson - One of the best experts on this subject based on the ideXlab platform.
-
Computing Heat Kernel pagerank and a local clustering algorithm
European Journal of Combinatorics, 2018Co-Authors: Fan Chung, Olivia SimpsonAbstract:Abstract Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time O ( log ( ϵ − 1 ) log n ϵ 3 log log ( ϵ − 1 ) ) , assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with Heat Kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a Heat Kernel pagerank vector, using the Heat Kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio ϕ , many vertices in S may serve as seeds for a Heat Kernel pagerank vector which will find a cut of conductance O ( ϕ ) .
-
Computing Heat Kernel Pagerank and a Local Clustering Algorithm
arXiv: Data Structures and Algorithms, 2015Co-Authors: Fan Chung, Olivia SimpsonAbstract:Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time $O\big(\frac{\log(\epsilon^{-1})\log n}{\epsilon^3\log\log(\epsilon^{-1})}\big)$, assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with Heat Kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a Heat Kernel pagerank vector, using the Heat Kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset $S$ of Cheeger ratio $\phi$, many vertices in $S$ may serve as seeds for a Heat Kernel pagerank vector which will find a cut of conductance $O(\sqrt{\phi})$.
-
computing Heat Kernel pagerank and a local clustering algorithm
International Workshop on Combinatorial Algorithms, 2014Co-Authors: Fan Chung, Olivia SimpsonAbstract:Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time \(O\big (\frac{\log (\epsilon ^{-1})\log n}{\epsilon ^3\log \log (\epsilon ^{-1})}\big )\), assuming performing a random walk step and sampling from a distribution with bounded support take constant time.
Fan Chung - One of the best experts on this subject based on the ideXlab platform.
-
Computing Heat Kernel pagerank and a local clustering algorithm
European Journal of Combinatorics, 2018Co-Authors: Fan Chung, Olivia SimpsonAbstract:Abstract Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time O ( log ( ϵ − 1 ) log n ϵ 3 log log ( ϵ − 1 ) ) , assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with Heat Kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a Heat Kernel pagerank vector, using the Heat Kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio ϕ , many vertices in S may serve as seeds for a Heat Kernel pagerank vector which will find a cut of conductance O ( ϕ ) .
-
Computing Heat Kernel Pagerank and a Local Clustering Algorithm
arXiv: Data Structures and Algorithms, 2015Co-Authors: Fan Chung, Olivia SimpsonAbstract:Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time $O\big(\frac{\log(\epsilon^{-1})\log n}{\epsilon^3\log\log(\epsilon^{-1})}\big)$, assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with Heat Kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a Heat Kernel pagerank vector, using the Heat Kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset $S$ of Cheeger ratio $\phi$, many vertices in $S$ may serve as seeds for a Heat Kernel pagerank vector which will find a cut of conductance $O(\sqrt{\phi})$.
-
computing Heat Kernel pagerank and a local clustering algorithm
International Workshop on Combinatorial Algorithms, 2014Co-Authors: Fan Chung, Olivia SimpsonAbstract:Heat Kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the Heat Kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time \(O\big (\frac{\log (\epsilon ^{-1})\log n}{\epsilon ^3\log \log (\epsilon ^{-1})}\big )\), assuming performing a random walk step and sampling from a distribution with bounded support take constant time.
-
a local graph partitioning algorithm using Heat Kernel pagerank
Workshop on Algorithms and Models for the Web-Graph, 2009Co-Authors: Fan ChungAbstract:We give an improved local partitioning algorithm using Heat Kernel pagerank, a modified version of PageRank. For a subset S with Cheeger ratio (or conductance) h , we show that there are at least a quarter of the vertices in S that can serve as seeds for Heat Kernel pagerank which lead to local cuts with Cheeger ratio at most $O(\sqrt{h})$, improving the previously bound by a factor of $\sqrt{log|S|}$.
-
a local graph partitioning algorithm using Heat Kernel pagerank
Internet Mathematics, 2009Co-Authors: Fan ChungAbstract:Abstract We give an improved local partitioning algorithm using Heat Kernel pagerank, a modified version of PageRank. For a subset S with Cheeger ratio (or conductance) h, we show that at least a quarter of the vertices in S can serve as seeds for Heat Kernel pagerank that lead to local cuts with Cheeger ratio at most O(√h), improving the previous bound by a factor of √log s, where s denotes the volume of S.
Maria E. Gageonea - One of the best experts on this subject based on the ideXlab platform.
-
Monotonicity properties of the Neumann Heat Kernel in the ball
Journal of Functional Analysis, 2011Co-Authors: Mihai N. Pascu, Maria E. GageoneaAbstract:Abstract A well-known conjecture of R. Laugesen and C. Morpurgo asserts that the diagonal of the Neumann Heat Kernel of the unit ball U ⊂ R n is a strictly increasing radial function. In this paper we use probabilistic arguments to settle this conjecture and to prove some inequalities for the Neumann Heat Kernel in the ball.
Martin Slowik - One of the best experts on this subject based on the ideXlab platform.
-
Heat Kernel estimates for random walks with degenerate weights
Electronic Journal of Probability, 2016Co-Authors: Sebastian Andres, Jeandominique Deuschel, Martin SlowikAbstract:We establish Gaussian-type upper bounds on the Heat Kernel for a continuous-time random walk on a graph with unbounded weights under an integrability assumption. For the proof we use Davies’ perturbation method, where we show a maximal inequality for the perturbed Heat Kernel via Moser iteration.
Wu-sheng Dai - One of the best experts on this subject based on the ideXlab platform.
-
Heat-Kernel approach for scattering
The European Physical Journal C, 2015Co-Authors: Wu-sheng DaiAbstract:An approach for solving scattering problems, based on two quantum field theory methods, the Heat Kernel method and the scattering spectral method, is constructed. This approach converts a method of calculating Heat Kernels into a method of solving scattering problems. This allows us to establish a method of scattering problems from a method of Heat Kernels. As an application, we construct an approach for solving scattering problems based on the covariant perturbation theory of Heat-Kernel expansions. In order to apply the Heat-Kernel method to scattering problems, we first calculate the off-diagonal Heat-Kernel expansion in the frame of the covariant perturbation theory. Moreover, as an alternative application of the relation between Heat Kernels and partial-wave phase shifts presented in this paper, we give an example of how to calculate a global Heat Kernel from a known scattering phase shift.
-
Relation between Heat Kernel method and scattering spectral method
The European Physical Journal C, 2012Co-Authors: Hai Pang, Wu-sheng Dai, Mi XieAbstract:In the present paper, we establish the connection between the Heat Kernel method and the scattering spectral method in quantum field theory. First, we provide the relation between the Heat Kernel and the scattering phase shift. Then as applications, we derive a large-time approximation of the Heat Kernel through the low-energy approximation of the phase shift, and we also derive a high-energy expansion of the phase shift expressed with Heat Kernel coefficients. Finally, we compare the renormalization schemes in the Heat Kernel method with that in the scattering spectral method. Concretely, we calculate the first- and second-order contributions to the vacuum energy by Heat-Kernel and Feynman-diagram methods, respectively, and show the coincidence of the results. Especially, in the Heat-Kernel framework, we perform both dimensional and zeta-function regularization to calculate the vacuum energy, and the result shows that dimensional renormalization procedure works well in the Heat Kernel method.
