Graph Identification

There is a growing amount of observational data describing networks — exam-ples include social networks, communication networks, and biological networks. As the amount of available data increases, so has our interest in analyzing these networks in order to uncover (1) general laws that govern their structure and evolution, and (2) patterns and predictive models to develop better policies and practices. However, a fundamental challenge in dealing with this newly avail-able observational data describing networks is that the data is often of dubious quality—it is noisy and incomplete—and before any analysis method can be applied, the data must be cleaned, missing information inferred and mistakes corrected. Skipping this cleaning step can lead to flawed conclusions for things as simple as degree distribution and centrality measures; for more complex an-alytic queries, the results are even more likely to be inaccurate and misleading. In this work, we introduce the notion of graph identification, which explicitly models the inference of a “cleaned ” output graph from a noisy input graph. We show how graph identification can be thought of as a series of probabilisti