Exploiting graphlet decomposition to explain the structure of complex networks: the GHuST framework

Abstract

The characterization of topology is crucial in understanding network evolution and behavior. This paper presents an innovative approach, the GHuST framework (Global connectivity, HUbs, Strings and Triangles), to describe complexnetwork topology from graphlet decomposition. GHust exploits the local information provided by graphlets to give a global explanation of network topology. The GHuST framework comprises twelve metrics that analyze how 2- and 3-node graphlets shape the structure of networks. The main strengths of the GHuST framework are enhanced topological description, size independence, and computational simplicity. It allows for straight comparison among different networks independently of their size. It also reduces the complexity of graphlet counting, since it does not use 4- and 5- node graphlets. The application of this novel framework to a large set of networks shows that it can intuitively classify networks of different nature based on topology. To ease network classification and enhance the graphical representation of them, we reduce the twelve dimensions to their main principal components. Furthermore, the twelve dimensions are easily interpretable. This enables the connection between complex-network analyses and diverse real applications.