Coarse-Grained Topology Estimation via Graph Sampling

Details Coarse-Grained Topology Estimation via Graph Sampling Coarse-Grained Topology Estimation via Graph Sampling

2011-05-27

arxiv.org/abs/1105.5488v1

Computer Science

Social and Information Networks

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Coarse-Grained Topology Estimation via Graph Sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coarse-Grained Topology Estimation via Graph Sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coarse-Grained Topology Estimation via Graph Sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664803