  Many online networks are measured and studied via sampling techniques, which
typically collect a relatively small fraction of nodes and their associated
edges. Past work in this area has primarily focused on obtaining a
representative sample of nodes and on efficient estimation of local graph
properties (such as node degree distribution or any node attribute) based on
that sample. However, less is known about estimating the global topology of the
underlying graph.
  In this paper, we show how to efficiently estimate the coarse-grained
topology of a graph from a probability sample of nodes. In particular, we
consider that nodes are partitioned into categories (e.g., countries or
work/study places in OSNs), which naturally defines a weighted category graph.
We are interested in estimating (i) the size of categories and (ii) the
probability that nodes from two different categories are connected. For each of
the above, we develop a family of estimators for design-based inference under
uniform or non-uniform sampling, employing either of two measurement
strategies: induced subgraph sampling, which relies only on information about
the sampled nodes; and star sampling, which also exploits category information
about the neighbors of sampled nodes. We prove consistency of these estimators
and evaluate their efficiency via simulation on fully known graphs. We also
apply our methodology to a sample of Facebook users to obtain a number of
category graphs, such as the college friendship graph and the country
friendship graph; we share and visualize the resulting data at
www.geosocialmap.com.
