[edit]

# Network Completion and Survey Sampling

*Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics*, PMLR 5:209-215, 2009.

#### 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.