On Scaling Social-Network Algorithms

Siddhartha Banerjee
postdoctoral researcher, Stanford University
Given on: Oct. 17th, 2014

Abstract

The large scale of online social networks is an important consideration for the design of inference and control algorithms in such settings. In different contexts, however, scaling often results in very different behavior -- it sometimes elevates simple solutions for seemingly-intractable problems to near-optimality, while at other times, it renders intractable algorithms which are efficient at smaller scales.

In the first part of the talk, I will consider the problem of enhancing viral spreading on social networks using external interventions (for example, via advertising). Though there is a large literature on controlling spreading processes by optimizing the choice of initial seed-nodes, a more natural model in many settings is to consider the presence of a dynamic external controller -- one which possesses a limited infection rate, but is otherwise unconstrained by the network. Finding efficient algorithms in this setting appears intractable; however, as the network scales, the problem often admits near-optimal solutions. In particular, using ideas from Markov chain phase-transition phenomena and percolation theory, I'll discuss how in large networks, external agents can significantly enhance the spreading process, and more surprisingly, how simple random external-infection policies are near-optimal for bringing about this change.

In the second part, I'll consider the problem of personalized search and recommendation in social networks. Personalized PageRank, an ego-centric generalization of PageRank, has long been recognized as an effective measure for sorting search results. However, for Personalized PageRank estimation, the scale of the network turns out to be a major bottleneck -- existing algorithms, though based on simple techniques such as the power iteration or Monte Carlo, have a running time which scales linearly in the network size, thereby rendering them infeasible for real-time social search in large-scale networks. I will talk about a recent breakthrough, wherein we developed the first algorithm for PageRank estimation with a sublinear running-time guarantee. This speedup is achieved via a new approach which combines linear algebraic techniques with random walks, and I'll discuss how this may prove useful in other stochastic estimation problems.

This talk is based on joint work with Avhishek Chatterjee, Peter Lofgren, C. Seshadri, Sanjay Shakkottai and Ashish Goel.

Bio

Siddhartha Banerjee is a postdoctoral researcher in the Department of Management Science and Engineering at Stanford. He received a PhD in Electrical and Computer Engineering from the University of Texas at Austin in 2013. He is interested in stochastic modeling and algorithm design for large-scale settings, with applications in communications and social networks, matching markets and social computing.