Sublinear algorithms in social networks via core-periphery decomposition
summary
A practical pipeline builds a hierarchical core-periphery decomposition via greedy neighbor-list queries (API-style, rate-limited), producing a sublinearly sized L0 that dominates the core and fragments the periphery into tiny components (average component size <10 on million-node graphs). That decomposition supports a sampler taking ≈5 queries per sample (vs. much larger for random walks) and a truncated bidirectional-BFS + highway route giving fast distance answers on graphs up to 1.5B edges, returning ≥99% exact or within +1 additive error while using index space below graph storage.
AI-written summary · about