##
* Michael Brautbar - The power of local information in social networks *

###

We study the power of local information algorithms for
optimization problems on social and technological networks. We focus on
sequential algorithms where the network topology is initially unknown
and is revealed only within a local neighborhood of vertices that have
been irrevocably added to the output set. This framework models the
behavior of an external agent that does not have direct access to the
network data, such as a user interacting with an online social network We study a range of problems under this model of algorithms with
local information. When the underlying graph is a preferential attachment
network, we show that one can find the node of maximum degree in the
network in a polylogarithmic number of steps, using an opportunistic
local algorithm that repeatedly queries the visible node of maximum degree.
This addresses an open question of Bollobas and Riordan. Moreover,
this result implies polylogarithmic approximations to problems such as
finding the smallest subgraph that connects a subset of nodes, finding
the highest-degree nodes, and finding a subgraph that maximizes vertex
coverage per subgraph size.
Motivated by problems faced by recruiters in online networks, we also
consider network coverage problems on arbitrary graphs. We demonstrate
a sharp threshold on the level of visibility required: at a certain
visibility level it is possible to design randomized algorithms that nearly
match the best approximation possible even with full access to the graph
structure, but with any less information it is impossible to achieve a non-
trivial approximation.
We conclude that a network provider's decision of
how much structure to make visible to its users can have a significant
effect on a user's ability to interact strategically with the network.