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 or 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6276186 (Why is no real title available?)
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm
- Extrapolation methods for PageRank computations
- Google's PageRank and beyond. The science of search engine rankings
- Graph clustering
- Least angle regression. (With discussion)
- Overlapping community detection in networks
- PageRank beyond the web
Cited in
(3)
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)
