Optimally learning social networks with activations and suppressions

Dana Angluin, James Aspnes, and Lev Reyzin. Optimally learning social networks with activations and suppressions. Nineteenth International Conference on Algorithmic Learning Theory, Lecture Notes in Computer Science 5254, Springer-Verlag, October 2008, pp. 272–286. Theoretical Computer Science 411(29–30):2729–2740. (ALT 2008 special issue).

Abstract

In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in the target network. We develop an algorithm that optimally learns an arbitrary social network of size n using O(n²) queries, matching the information theoretic lower bound we prove for this problem. We also consider the case when the target social network forms a tree, and we show that the learning problem takes Θ(n log n) queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used.

BibTeX

Download
@article{AngluinAR2010networks,
author = {Dana Angluin and James Aspnes and Lev Reyzin},
title = {Optimally learning social networks with activations and suppressions},
month=jun,
year = 2010,
journal = {Theoretical Computer Science},
volume = 411,
number = {29--30},
pages = {2729--2740}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page