Graphlets in Complex Networks

Analyzing the characteristics of complex networks is a principal task of network sci- ence. In this thesis, we study graphets, small induces subgraphs rooted in a vertex, as a tool to describe and compare networks. First, we use graph theory to explore the theo- retical properties of graphlets, propose a framework for studying them, and make novel observations. We discuss the link between graphlets and the Weisfeiler-Lehman isomor- phism test and the reconstruction conjecture. We prove that the knowledge of graphlets of size n − 1 for certain graphs is sufficient for their reconstruction. Second, we develop several graphlet-based metrics and apply them to real-world networks and their models. In line with prior literature, the results suggest that graphlets are potentially an excellent tool of characterizing networks. Counter to prior literature, the results suggest that the Albert-Barabási model produces more realistic synthetic networks than other models.