text: Many real-world networks are prohibitively large for data retrieval, storage and analysis of all of its nodes and links. Understanding the structure and dynamics of these networks entails creating a smaller representative sample of the full graph while preserving its relevant topological properties. In this report, we show that graph sampling algorithms currently proposed in the literature are not able to preserve network properties even with sample sizes containing as many as 20 of the nodes from the original graph. We present a new sampling algorithm, called Tiny Sample Extractor, with a new goal of a sample size smaller than 5 of the original graph while preserving two key properties of a network, the degree distribution and its clustering co- efficient. Our approach is based on a new empirical method of estimating measurement biases in crawling algorithms and compensating for them accordingly. We present a detailed comparison of best known graph sampling algorithms, focusing in particular on how the properties of the sample subgraphs converge to those of the original graph as they grow. These results show that our sampling algorithm extracts a smaller subgraph than other algorithms while also achieving a closer convergence to the degree distribution, measured by the degree exponent, of the original graph. The subgraph generated by the Tiny Sample Extractor, however, is not necessarily representative of the full graph with regard to other proper ties such as assortativity. This indicates that the problem of extracting a truly representative small subgraph from a large graph remains unsolved.
  @cite_27: While data mining in chemoinformatics studied graph data with dozens of nodes, systems biology and the Internet are now generating graph data with thousands and millions of nodes. Hence data mining faces the algorithmic challenge of coping with this significant increase in graph size: Classic algorithms for data analysis are often too expensive and too slow on large graphs. While one strategy to overcome this problem is to design novel efficient algorithms, the other is to 'reduce' the size of the large graph by sampling. This is the scope of this paper: We will present novel Metropolis algorithms for sampling a 'representative' small subgraph from the original large graph, with 'representative' describing the requirement that the sample shall preserve crucial graph properties of the original graph. In our experiments, we improve over the pioneering work of Leskovec and Faloutsos (KDD 2006), by producing representative subgraph samples that are both smaller and of higher quality than those produced by other methods from the literature.
  @cite_13: Online networks occupy an increasingly larger position in how we acquire information, how we communicate with one another, and how we disseminate information. Frequently, small sets of vertices dominate various graph and statistical properties of these networks and, because of this, they are relevant for structural analysis and efficient algorithms and engineering. For the web overall, and specifically for social linking in blogs and instant messaging, we provide a principled, rigorous study of the properties, the construction, and the utilization of subsets of special vertices in large online networks. We show that graph synopses defined by the importance of vertices provide small, relatively accurate portraits, independent of the importance measure, of the larger underlying graphs and of the important vertices. Furthermore, they can be computed relatively efficiently.
  @cite_3: We present a detailed statistical analysis of the characteristics of partial Web graphs obtained by sub-sampling a large collection of Web pages. We show that in general the macroscopic properties of the Web are better represented by a shallow exploration of a large number of sites than by a deep exploration of a limited set of sites. We also describe and quantify the bias induced by the different sampling strategies, and show that it can be significant even if the sample covers a large fraction of the collection.
  @cite_11: In mining information from very large graphs, processing time as well as system memory become computational bottlenecks as the properties of large graphs must be compared through each iteration of an algorithm. This is a particularly pronounced problem for complex properties. For example, distance metrics are used in many fundamental data mining algorithms including k-nearest neighbors for the classification task. Even the relatively efficient distance and similarity heuristics for large inputs, though, often require processing and memory well beyond linear with respect to the size of the input, and this rapidly becomes intractable with very large inputs. Complex properties such as the distance between two graphs can be extremely costly, but using samples of these large graphs to calculate the same properties proves to reduce memory requirements and processing time significantly without sacrificing quality of classification. Because the vast amount of Web data is easily and robustly represented with graphs, a data reduction technique that preserves the accuracy of mining algorithms on such inputs is important. The sampling techniques presented here show that very large graphs of Web content can be condensed into significantly smaller yet equally expressive graphs that lead to accurate but more efficient classification of Web content
summary: A sample subgraph induced by a randomly selected set of nodes has been discussed in several works on graph sampling @cite_3 @cite_11 @cite_27 @cite_13 . Selecting nodes randomly ensures that nodes of a given degree are chosen with probability proportional to the number of such nodes in the network. The selected set of nodes have a degree distribution very similar to that of the original graph, but these degrees are the degrees of the nodes in the original graph @math and not the degrees in the induced subgraph @math . There are at least two additional problems with such a sampling strategy: (i) when the desired sample size is as small as 5 is highly likely to be a disconnected graph even if @math is connected and thus, unrepresentative; and (ii) in real networks that have to be crawled, it is usually very hard or infeasible to generate a statistically valid set of uncorrelated random nodes from the full graph @math given that the full graph is not known (even though a few random nodes can always be selected from within the known portion of the graph).