PageRank Nibble on the sparse directed stochastic block model

DOI10.1007/978-3-031-32296-9_10MaRDI QIDQ6057302zbMATH OpenOpenAlexFDO

Authors Sayan Banerjee, Prabhanka Deka, Mariana Olvera-Cravioto

Publication date 4 October 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

community detectiondirected stochastic block modellocal weak convergencePageRank Nibble

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We present new results on community recovery based on the PageRank Nibble algorithm on a sparse directed stochastic block model (dSBM). Our results are based on a characterization of the local weak limit of the dSBM and the limiting PageRank distribution. This characterization allows us to estimate the probability of misclassification for any given connection kernel and any given number of seeds (vertices whose community label is known). The fact that PageRank is a local algorithm that can be efficiently computed in both a distributed and asynchronous fashion, makes it an appealing method for identifying members of a given community in very large networks where the identity of some vertices is known.

Recommendations

• PageRank in Undirected Random Graphs
• PageRank in Scale-Free Random Graphs
• Pagerank asymptotics on directed preferential attachment networks
• PageRank on inhomogeneous random digraphs
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• A note on the PageRank of undirected graphs
• PageRank for networks, graphs, and Markov chains
• Targeted sampling from massive block model graphs with personalized PageRank
• Generalized PageRank on directed configuration networks
• On Local Estimations of PageRank: A Mean Field Approach

Cites work

• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• Community detection thresholds and the weak Ramanujan property
• Local Partitioning for Directed Graphs Using PageRank
• Local weak convergence for PageRank
• Mean field analysis of personalized PageRank with implications for local graph clustering
• PageRank on inhomogeneous random digraphs
• PageRank's behavior under degree correlations
• Reconstruction and estimation in the planted partition model

Cited in

(3)

• On Local Estimations of PageRank: A Mean Field Approach
• Attribute network models, stochastic approximation and network sampling
• Almost exact recovery in noisy semi-supervised learning

This page was built for publication: PageRank Nibble on the sparse directed stochastic block model

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