2015/03/31 by Kyle Kloster, D. F. GLEICH, David F. Gleich +1 · 12 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Cluster (spacecraft) #Cluster analysis #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #PageRank #Random walk #Regularization (linguistics) #Set (abstract data type) #acm:91D30 #cs.SI #msc:91D30
paper · pdf · doi:10.1017/s0956792516000280
published in European Journal of Applied Mathematics 27(6), 812-845 (Cambridge University Press) · 29 pages, 8 figures
arxiv created 2015/12/11 · openalex created_date 2016/06/24 · openalex publication_date 2016/07/01 · arxiv updated 2016/07/06 · openalex updated_date 2026/08/05
We study the behaviour 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 solution path or regularization path 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.