[Dmbu-l] [Econcs-general] [Econcs] Friday 10/4: Michael Brautbar on Power of Local Information in Social Networks, MD 123, 2:30-4pm (fwd)

Evimaria Terzi evimaria at bu.edu
Mon Sep 30 14:10:24 EDT 2013

"Everything should be made as simple as possible, but no simpler"
(A. Einstein)

---------- Forwarded message ----------
Date: Mon, 30 Sep 2013 16:55:32 +0000
From: "Yin, Ming" <mingyin at fas.harvard.edu>
To: "econcs-general at eecs.harvard.edu" <econcs-general at eecs.harvard.edu>
Subject: [Econcs-general] [Econcs] Friday 10/4: Michael Brautbar on Power of
     Local Information in Social Networks, MD 123, 2:30-4pm

Hi all,
For this week's EconCS Seminar, Michael Brautbar from MIT will give us a talk on the power of local information in social networks.

Friday, 10/4
Maxwell-Dworkin 123

The Power of Local Information in Social Networks
Joint work with Christian Borgs, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier

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
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 a decade-old 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 advertisers 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
-------------- next part --------------
Econcs-general mailing list
Econcs-general at eecs.harvard.edu

More information about the Dmbu-l mailing list