  We study the power of \textit{local information algorithms} for optimization
problems on social networks. We focus on sequential algorithms for which 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.
The distinguishing feature of this setting is that locality is necessitated by
constraints on the network information visible to the algorithm, rather than
being desirable for reasons of efficiency or parallelizability. In this sense,
changes to the level of network visibility can have a significant impact on
algorithm design.
  We study a range of problems under this model of algorithms with local
information. We first consider the case in which 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 algorithm that repeatedly queries the visible node of maximum
degree. This addresses an open question of Bollob{\'a}s and Riordan. In
contrast, local information algorithms require a linear number of queries to
solve the problem on arbitrary networks.
  Motivated by problems faced by recruiters in online networks, we also
consider network coverage problems such as finding a minimum dominating set.
For this optimization problem we show that, if each node added to the output
set reveals sufficient information about the set's neighborhood, then it is
possible to design randomized algorithms for general networks that nearly match
the best approximations possible even with full access to the graph structure.
We show that this level of visibility is necessary.
  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.
