The Power of Local Information in Social Networks
The Power of Local Information in Social Networks
复制标题
社交网络中本地信息的力量
DOI：
10.1007/978-3-642-35311-6_30
复制
发表时间：
2012
影响因子：
--
通讯作者：
Brendan Lucier
中科院分区：
文献类型：
--
作者：
C. Borgs;Mickey Brautbar;J. Chayes;S. Khanna;Brendan Lucier
我们研究的权力，本地信息算法的优化问题的社会和技术网络。我们专注于顺序算法的网络拓扑结构是最初未知的，只有在一个局部邻域内的顶点，已被添加到输出集。该框架对不能直接访问网络数据的外部代理的行为进行建模，例如与在线社交网络交互的用户。
我们研究了一系列的问题，在这种模式下的算法与本地信息。当底层图是一个优先连接网络，我们表明，可以找到根（即初始节点）在一个多对数的步骤数，使用本地算法，反复查询的最大程度的可见节点。这解决了Bollobas和Riordan的一个悬而未决的问题。这一结果的动机是它的影响：我们获得多对数近似的问题，如找到最小的子图，连接一个子集的节点，找到最高程度的节点，并找到一个子图，最大限度地提高每个子图大小的顶点覆盖。
出于在线网络招聘人员所面临的问题，我们也考虑网络覆盖问题的任意图。我们证明了一个尖锐的阈值的可见性水平所需的：在一定的可见性水平，它是可能的设计算法，几乎匹配的最佳近似可能的，即使完全访问的图形结构，但与任何较少的信息，它是不可能实现一个非平凡的近似。我们的结论是，网络提供商的决定有多少结构，使其用户可见，可以有一个显着的影响，用户的能力，与网络的战略互动。
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 root (i.e. initial node) in a polylogarithmic number of steps, using a local algorithm that repeatedly queries the visible node of maximum degree. This addresses an open question of Bollobas and Riordan. This result is motivated by its implications: we obtain 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 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.