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 to describe complex-network topology from graphlet decomposition. This new framework exploits the local information provided by graphlets to give a global explanation of network topology. The GHuST framework is comprised of 12 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 disregarding their size. It also reduces the complexity of graphlet counting, since it does not use 4- and 5-node graphlets. The application of the novel framework to a large set of networks shows that it can classify networks of distinct nature based on their topological properties. To ease network classification and enhance the graphical representation of them, we reduce the 12 dimensions to their main principal components. Furthermore, the 12 dimensions are easily interpretable. This enables the connection between complex-network analyses and diverse real applications.

Figure 1

2- to 5-node graphlets (from $G_0$ to $G_{29}$) and their automorphism orbits (from 0 to 72). For each graphlet, nodes in the same automorphism orbits are identified with the same color (e.g. all blue nodes in $G_1$ are in $O_1$, they are in a symmetric position in the graphlet, the green node is in a different topological position, it is in $O_2$).

Figure 2

(a) Variance explained (%) and accumulated variance explained (%) by each of the principal components resulting from the PCA analysis to a set of 1,404 networks. As can be seen, the first 3 principal components summarize more than 90% of the variance of the original data. (b) Graphical representation of the 1,404 networks in the 3-d space defined by the three first principal components. In this representation, several clusters can be appreciated, corresponding to networks with similar topological structure. (c) 2-d projections of the 3-d representation of the 1,404 networks in the space defined by the three first principal components. (d) Loadings of $\rho$ for the three first principal components. As there are no null coefficients, it can be concluded that there are no irrelevant dimensions in the proposed 12 dimensional metric.

Figure 3

Range of variation of each metric dimension, ${\rho }_i$, (green area) and median value of each ${\rho }_i$ for the seven set of networks analyzed: autonomous systems, enzymes, Facebook, power networks, retweet, roads and webs. Networks with different structures exhibit a distinct distribution of the ${\rho }_i$ values, as highlighted by these charts.

Figure 4

Contributions of each dimension of the GHuST framework to the first principal component obtained for each set of networks analyzed. Larger loadings are associated with a high variance in the original dataset, providing information about the topological differences between networks of the same set.

Figure 5

Variance explained and cumulative variance explained by each of the principal components of the resulting PCA applied independently to each type of network analyzed. As can be seen, in all cases using the first 3 principal components account for more than 90% of the variance of the original dataset.