Number of Connected Components in a Graph: Estimation via Counting Patterns

Ashish Khetan, Harshay Shah, Sewoong Oh

Due to the limited resources and the scale of the graphs in modern datasets, we often get to observe a sampled subgraph of a larger original graph of interest, whether it is the wo…