Computing heat kernel PageRank and a local clustering algorithm

DOI10.1016/j.ejc.2017.07.013zbMath1373.05188arXiv1503.03155OpenAlexW2749605325MaRDI QIDQ1678092

Olivia Simpson, Fan R. K. Chung

Publication date: 14 November 2017

Published in: Lecture Notes in Computer Science, European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.03155

zbMATH Keywords

heat kernellocal algorithmslocal clustering algorithmPersonalized PageRankheat kernel PageRank

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Computing heat kernel PageRank and a local clustering algorithm ⋮ Matrix functions in network analysis ⋮ Sublinear Algorithms for Local Graph-Centrality Estimation ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Compressive Sensing for Cut Improvement and Local Clustering

Uses Software

• NetworkX
• SNAP
• IsoRankN

Cites Work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Computing heat kernel PageRank and a local clustering algorithm
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• A Sublinear Time Algorithm for PageRank Computations
• A Nearly-Sublinear Method for Approximating a Column of the Matrix Exponential for Matrices from Large, Sparse Networks
• Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Emergence of Scaling in Random Networks
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On clusterings
• Random walks in a convex body and an improved volume algorithm
• Comparing Top k Lists
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Finding sparse cuts locally using evolving sets
• Collective dynamics of ‘small-world’ networks
• A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm
• Machine Learning: ECML 2004

This page was built for publication: Computing heat kernel PageRank and a local clustering algorithm