Overview / Usage

When do we say that a graph has become large or the amount of data in the graph has become big? Why do we sample a graph? When do we say that a graph is sampled? What should be the size of our sampled graph? What difference does it make to work on the original graph and the sampled graph? These are some questions that are very common when people start working on real world of graphs that often span hundreds of millions or even billions of nodes and interactions between them. By the thumb of rule, we can say that 'large graphs' are those graphs exploration of which requires long computation time and 'big data' is typically the data which takes too much memory space to be stored on a single hard drive.
A good sampled graph must include useful knowledge. There comes a trade-off between accuracy and computational time when we sample a graph. As we increase the size of our sample graph, the accuracy of the graph properties increases because we come close to the original graph in every iteration and also the computational time increases with the increase in sample size. Our primary goal is to find the important properties that effectively summarizes the graph.