Geometric Local Structure in Biological Networks

Abstract—The recent explosion in biological and other real-world network data has created the need for improved tools for large network analyses. Several new mathematical techniques for analyzing local structural properties of large networks have recently been developed. Our work introduces small induced subgraphs of large networks, called graphlets. We use graphlets to develop “network signatures ” that quantify local structural properties of a network. Based on these network signatures, we design two novel “network agreement ” measures. These measures lead us to new, well-fitting geometric graph models of biological networks. Models are in turn used to design efficient heuristics. I