Seeded PageRank solution paths

DOI10.1017/S0956792516000280zbMATH Open1380.68313arXiv1503.00322OpenAlexW3123252484MaRDI QIDQ4594615FDOQ4594615

David F. Gleich, Kyle Kloster

Publication date: 24 November 2017

Published in: European Journal of Applied Mathematics (Search for Journal in Brave)

Abstract: We study the behavior of network diffusions based on the PageRank random walk from a set of seed nodes. These diffusions are known to reveal small, localized clusters (or communities) and also large macro-scale clusters by varying a parameter that has a dual-interpretation as an accuracy bound and as a regularization level. We propose a new method that quickly approximates the result of the diffusion for all values of this parameter. Our method efficiently generates an approximate $extitsolutionpath$ or $extitregularizationpath$ associated with a PageRank diffusion, and it reveals cluster structures at multiple size-scales between small and large. We formally prove a runtime bound on this method that is independent of the size of the network, and we investigate multiple optimizations to our method that can be more practical in some settings. We demonstrate that these methods identify refined clustering structure on a number of real-world networks with up to 2 billion edges.

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

Recommendations

• Strong localization in personalized PageRank vectors
• \texttt{PageRank} and random walks on graphs
• Non-backtracking PageRank
• Multilinear PageRank
• Multiscale matrix sampling and sublinear-time PageRank computation

zbMATH Keywords

social networkscomplex networksrandom walks on graphsgraphs and linear algebraprogramming involving graphs or networks

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Cites Work

• Least angle regression. (With discussion)
• Graph clustering
• Overlapping community detection in networks
• Google's PageRank and beyond. The science of search engine rankings
• PageRank beyond the web
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Extrapolation methods for PageRank computations
• Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm
• Title not available (Why is that?)

Cited In (3)

• Network analysis and modelling: Special issue ofEuropean Journal of Applied Mathematics
• Title not available (Why is that?)
• A framework for second-order eigenvector centralities and clustering coefficients

Uses Software

• ElemStatLearn

This page was built for publication: Seeded PageRank solution paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594615)