We study the power of local information algorithms for optimization problems on social and technological 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. This framework captures situations in which the optimizer is an external agent that does not have direct access to the network data, but rather learns about the graph structure only via (costly) queries. For instance, a user may wish to strategically find, and form connections to, high-degree nodes in an online social network. An appropriate algorithm for this search problem must take into account the fact that the structure of the graph is not known in advance, and is only revealed locally as nodes are added to the user's set of connections. Given this limited network visibility, how should the user choose which connections to form? This question is relevant not only to the optimizer, but also to the designer of the social network platform who must decide how much network topology is revealed to individual users. 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, where we show that local information algorithms can perform surprisingly well at various tasks. 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ás and Riordan on the power of local algorithms on preferential attachment graphs. We also show that a polylogarithmic number of queries suffices to find a path between any two nodes in the network. In contrast, local information algorithms require a linear number of queries to solve these problems 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 * borgs@microsoft. 1 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 achieve a sublinear approximation for general graphs 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 significant effect on a user's ability to interact strategically with the network.
In REF traceroute algorithms are proposed to find the root node and to approximate several other characteristics in a preferential attachment graph.
The Power of Local Information in Social Networks
ArXiv
ArXiv
Computer Science Physics