Using Subgraph Distributions for Characterizing Networks and Fitting Random Graph Models

There exist many different global graph measures that can be used to summarize and characterize a network. However, existing measures often ignore the local topological features of a network. This is relevant, for example, when fitting a random graph model to a real-world network. With respect to existing measures the model might look like a good fit, however, the local topology might be very different. In the article we propose a new characterization of networks using the distribution of small subgraphs in the network. Because computing these distributions exactly is computationally unfeasible for large networks we propose two new sampling schemes to approximate the distribution. Finally, we perform some experiments comparing a set of datasets with respect to their pattern distributions and comparing the fit of some random graph models to the datasets.