Optimally Learning Social Networks with Activations and Suppressions
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 ^2) 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 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.
Cite
Text
Angluin et al. "Optimally Learning Social Networks with Activations and Suppressions." International Conference on Algorithmic Learning Theory, 2008. doi:10.1007/978-3-540-87987-9_24Markdown
[Angluin et al. "Optimally Learning Social Networks with Activations and Suppressions." International Conference on Algorithmic Learning Theory, 2008.](https://mlanthology.org/alt/2008/angluin2008alt-optimally/) doi:10.1007/978-3-540-87987-9_24BibTeX
@inproceedings{angluin2008alt-optimally,
title = {{Optimally Learning Social Networks with Activations and Suppressions}},
author = {Angluin, Dana and Aspnes, James and Reyzin, Lev},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2008},
pages = {272-286},
doi = {10.1007/978-3-540-87987-9_24},
url = {https://mlanthology.org/alt/2008/angluin2008alt-optimally/}
}