Graphlets
Graphlets are small connected non-isomorphic induced subgraphs of a large network. Graphlets differ from network motifs, since they must be induced subgraphs, whereas motifs are partial subgraphs. An induced subgraph must contain all edges between its nodes that are present in the large network, while a partial subgraph may contain only some of these edges. Moreover, graphlets do not need to be over-represented in the data when compared with randomized networks, while motifs do.
Graphlets were first introduced by Nataša Pržulj, when they were used as a basis for designing two new highly sensitive measures of network local structural similarities: the relative graphlet frequency distance and the graphlet degree distribution agreement. Additionally, Pržulj group developed a novel measure of network topological similarity that generalizes the degree of a node in the network to its graphlet degree vector or graphlet degree signature.
Graphlet-based network properties
Relative graphlet frequency distance
RGF-distance compares the frequencies of the appearance of all 3-5-node graphlets in two networks. Let Ni be the number of graphlets of type in network G, and let be the total number of graphlets of G. The "similarity" between two graphs should be independent of the total number of nodes or edges, and should depend only upon the differences between relative frequencies of graphlets. Thus, relative graphlet frequency distance D between two graphs G and H is defined as:,
where. The logarithm of the graphlet frequency is used because frequencies of different graphlets can differ by several orders of magnitude and the distance measure should not be entirely dominated by the most frequent graphlets.
Graphlet degree distribution agreement
GDD-agreement generalizes the notion of the degree distribution to the spectrum of graphlet degree distributions in the following way. The degree distribution measures the number of nodes of degree k in graph G, i.e., the number of nodes "touching" k edges, for each value of k. Note that an edge is the only graphlet with two nodes. GDDs generalize the degree distribution to other graphlets: they measure for each 2-5-node graphlet Gi,, such as a triangle or a square, the number of nodes "touching" k graphlets Gi at a particular node. A node at which a graphlet is "touched" is topologically relevant, since it allows us to distinguish between nodes "touching", for example, a three node path at an end node or at the middle node. This is summarized by automorphism orbits : by taking into account the "symmetries" between nodes of a graphlet, there are 73 different orbits across all 2-5-node graphlets.For each orbit j, one needs to measure the jth GDD, dGj, i.e., the distribution of the number of nodes in G "touching" the corresponding graphlet at orbit j k times. Clearly, the degree distribution is the 0th GDD. dGj is scaled as
to decrease the contribution of larger degrees in a GDD and then normalized with respect to its total area
giving the "normalized distribution"
The jth GDD-agreement compares the jth GDDs of two networks.
For two networks G and H and a particular orbit j, the "distance" Dj between their normalized jth GDDs is:
The distance is between 0 and 1, where 0 means that G and H have identical jth GDDs, and 1 means that their jth GDDs
are far away. Next, Dj is reversed to obtain the jth GDD-agreement:
, for.
The total GDD-agreement between two networks G and H is the arithmetic or the geometric average of the jth GDD-agreements over all j, i.e.,
,
and
,
respectively. GDD-agreement is scaled to always be between 0 and 1, where 1 means that two networks are identical with respect to this property.
Graphlet degree vectors (signatures) and signature similarities
This method generalizes the degree of a node, which counts the number of edges that the node touches, into the vector of graphlet degrees, or graphlet degree signature, counting the number of graphlets that the node touches at a particular orbit, for all graphlets on 2 to 5 nodes. The resulting vector of 73 coordinates is the signature of a node that describes the topology of node's neighborhood and captures its interconnectivities out to a distance of 4. The graphlet degree signature of a node provides a highly constraining measure of local topology in its vicinity and comparing the signatures of two nodes provides a highly constraining measure of local topological similarity between them.The signature similarity is computed as follows. For a node u in graph G, ui denotes the ith coordinate of its signature vector, i.e., ui is the number of times node u is touched by an orbit i in G. The distance Di between the ith orbits of nodes u and v is defined as:
,
where wi is the weight of orbit i that accounts for dependencies between orbits. The total distance D between nodes u and v is defined as:
.
The distance D, where distance 0 means that signatures of nodes u and v are identical. Finally, the signature similarity, S, between nodes u and v'' is:
.
Clearly, a higher signature similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods.
Application of graphlet-based network properties
RGF-distance and GDD-agreement were used to evaluate the fit of various network models to real-world networks and to discover a new, well-fitting, geometric random graph model for protein-protein interaction networks, as well as other types of biological networks, such as protein structure networks, also called residue interaction graphs. These graphlet-based network properties are implemented in , a software tool for large network analyses and modeling. Alternatively, a parallel implementation is provided in , a software library for computing graphlet-based network properties in large and massive networks.Graphlet degree vectors and signature similarities were applied to biological networks to identify groups of topologically similar nodes in a network and predict biological properties of yet uncharacterized nodes based on known biological properties of characterized nodes. Specifically, they were applied to protein function prediction, cancer gene identification, and discovery of pathways underlying certain biological processes, such as melanogenesis or protein degradation. Additionally, GRAph ALigner, a global network alignment method, used graphlet degree vectors and signature similarities to produce topological alignments of biological networks, without using any information external to network topology.