The Power of Local Information in Network Algorithms

Speaker: Michael Brautbar , MIT

Date: Friday, May 09, 2014

Time: 1:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G882

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Algorithms & Complexity Seminars-Michael Brautbar

Abstract: We study the power of 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. 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 prove that one can find the node of maximum degree in the network in a polylogarithmic number of steps, using a local algorithm that repeatedly queries the visible node of maximum degree. This addresses a decade-old open question of Bollobá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 advertizers 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.

Joint work with Christian Borgs, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Rebecca Yadegar Email at Wednesday, May 07, 2014 at 1:25 PM.