Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Competitive Ratio
Hardness of Approximation
Satisfiability
Social Network
Upper and Lower Bounds
Lower Bound
Maximum Likelihood
Subscribe
Academic
Publications
Inferring Social Networks from Outbreaks
Inferring Social Networks from Outbreaks,10.1007/9783642161087_12,Dana Angluin,James Aspnes,Lev Reyzin
Edit
Inferring Social Networks from Outbreaks
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Dana Angluin
,
James Aspnes
,
Lev Reyzin
We consider the problem of inferring the most likely
social network
given connectivity constraints imposed by observations of outbreaks within the network. Given a set of vertices (or agents) V and constraints (or observations) S i ⊆ V we seek to find a minimum loglikelihood cost (or maximum likelihood) set of edges (or connections) E such that each S i induces a connected subgraph of (V,E). For the offline version of the problem, we prove an Ω(log(n))
hardness of approximation
result for uniform cost networks and give an algorithm that almost matches this bound, even for arbitrary costs. Then we consider the online problem, where the constraints are satisfied as they arrive. We give an O(nlog(n))competitive algorithm for the arbitrary cost online problem, which has an Ω(n)competitive lower bound. We look at the uniform cost case as well and give an O(n 2/3log2/3(n))competitive algorithm against an oblivious adversary, as well as an W</font >(Ö</font >n)\Omega(\sqrt{n})competitive
lower bound
against an adaptive adversary. We examine cases when the underlying network graph is known to be a star or a path, and prove matching
upper and lower bounds
of Θ(log(n)) on the
competitive ratio
for them.
Conference:
Algorithmic Learning Theory  ALT
, pp. 104118, 2010
DOI:
10.1007/9783642161087_12
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
References
(20)
Completing Networks Using Observed Data
(
Citations: 2
)
Tatsuya Akutsu
,
Takeyuki Tamura
,
Katsuhisa Horimoto
Conference:
Algorithmic Learning Theory  ALT
, pp. 126140, 2009
Learning a Hidden Subgraph
(
Citations: 20
)
Noga Alon
,
Vera Asodi
Journal:
Siam Journal on Discrete Mathematics  SIAMDM
, vol. 18, no. 4, pp. 697712, 2005
The online set cover problem
(
Citations: 45
)
Noga Alon
,
Baruch Awerbuch
,
Yossi Azar
,
Niv Buchbinder
,
Joseph Naor
Conference:
ACM Symposium on Theory of Computing  STOC
, vol. 39, no. 2, pp. 100105, 2003
A general approach to online network optimization problems
(
Citations: 42
)
Noga Alon
,
Baruch Awerbuch
,
Yossi Azar
,
Niv Buchbinder
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 577586, 2004
Learning a Hidden Matching
(
Citations: 19
)
Noga Alon
,
Richard Beigel
,
Simon Kasif
,
Steven Rudich
,
Benny Sudakov
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 197206, 2002
Sort by:
Citations
(1)
On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
Jun Hosoda
,
Juraj Hromkovič
,
Taisuke Izumi
,
Hirotaka Ono
,
Monika Steinová
,
Koichi Wada