Subgraph Methods for Comparing Complex Networks

Abstract

An increasing number of models have been proposed to explain the link structure observed in complex networks. The central problem addressed in this thesis is: how do we select the best model? The model-selection method we implement is based on supervised learning. We train a classifier on six complex network models incorporating various link attachment mechanisms, including preferential attachment, copying and spatial. For the classification we represent graphs as feature vectors, integrating common complex network statistics with raw counts of small connected subgraphs commonly referred to as graphlets. The outcome of each experiment strongly indicates that models which incorporate the preferential attachment mechanism fit the network structure of Facebook the best. The experiments also suggest that graphlet structure is better at distinguishing different network models than more traditional complex network statistics.

To further the understanding of our experimental results, we compute the expected number of triangles, 3-paths and 4-cycles which appear in our selected models. This analysis shows that the spatial preferential attachment model generates 3-paths, triangles and 4-cycles in abundance, giving a closer match to the observed network structure of the Facebook networks used in our model selection experiment. The other models generate some of these subgraphs in abundance but not all three at once. In general, we show that our selected models generate vastly different amounts of triangles, 3-paths and 4-cycles, verifying our experimental conclusion that graphlets are distinguishing features of these complex network models.