Speaker: Brendan Lucier
Microsoft Research, New England
Title: The Power of Local Information in Social Networks
Imagine an external user trying to solve an optimization problem on an extremely large network. For example, a recruiter may wish to strategically form connections in a social networking application (such as LinkedIn) in order to maximize the number of potential job candidates that are at most two hops away. This is a well-studied coverage problem, but with a twist: the structure of the graph is not known in advance, and is only revealed locally as nodes are added to the recruiter's set of connections. Given this limited information, how should the recruiter choose which connections to form?
More generally, we consider coverage problems on graphs in which local information about a node (such as the graph structure up to some number of hops away) is revealed only after that node has been added to the output set. For a number of optimization problems (including minimum dominating set and minimum partial coverage) we show that, if each query reveals graph structure up to two hops away, then it is possible to design randomized algorithms that nearly match the best approximations possible even with full access to the graph structure. We also show that this level of visibility is necessary: it is impossible to design non-trivial algorithms if less information is revealed on each query. We conclude that a network provider's decision of how much structure to make visible to its users can have a profound effect on the range of behaviors it can support.
We also design local algorithms specifically for preferential attachment networks, which model the structure of social networks. We resolve an open question by Bollobas and Riordan by showing that finding a path between two nodes, or finding the highest-degree node in the network, can be accomplished by a simple local algorithm (in which each query reveals graph structure up to one hop away) in polylogarithmic time.
Based on joint work with Christian Borgs, Michael Brautbar, Jennifer Chayes, and Sanjeev Khanna.