Network Completion and Survey Sampling
Abstract
We study the problem of learning the topology of an undirected network by observing a random subsample. Specifically, the sample is chosen by randomly selecting a fixed number of vertices, and for each we are allowed to observe all edges it is incident with. We analyze a general formalization of learning from such samples, and derive confidence bounds on the number of differences between the true and learned topologies, as a function of the number of observed mistakes and the algorithm’s bias. In addition to this general analysis, we also analyze a variant of the problem under a stochastic block model assumption.
Cite
Text
Hanneke and Xing. "Network Completion and Survey Sampling." Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009.Markdown
[Hanneke and Xing. "Network Completion and Survey Sampling." Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009.](https://mlanthology.org/aistats/2009/hanneke2009aistats-network/)BibTeX
@inproceedings{hanneke2009aistats-network,
title = {{Network Completion and Survey Sampling}},
author = {Hanneke, Steve and Xing, Eric P.},
booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics},
year = {2009},
pages = {209-215},
volume = {5},
url = {https://mlanthology.org/aistats/2009/hanneke2009aistats-network/}
}