Graphlets in mathematics are induced subgraph isomorphism classes in a graph, i.e. two graphlet occurrences are isomorphic, whereas two graphlets are non-isomorphic. Graphlets differ from network motifs in a statistical sense, network motifs are defined as over- or under-represented graphlets with respect to some random graph null model.
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(G) be the number of graphlets of type i {\displaystyle i} ( i ∈ { 1 , … , 29 } {\displaystyle i\in \{1,\ldots ,29\}} ) in network G, and let T ( G ) = ∑ i = 1 29 N i ( G ) {\displaystyle T(G)=\sum _{i=1}^{29}N_{i}(G)} 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(G,H) between two graphs G and H is defined as:
D ( G , H ) = ∑ i = 1 29 | F i ( G ) − F i ( H ) | {\displaystyle D(G,H)=\sum _{i=1}^{29}|F_{i}(G)-F_{i}(H)|} , where F i ( G ) = − log ( N i ( G ) / T ( G ) ) {\displaystyle F_{i}(G)=-\log(N_{i}(G)/T(G))} . 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 (GDDs) 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, i = 0 , 1 , . . . , 29 {\displaystyle i=0,1,...,29} , 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 (or just orbits, for brevity): by taking into account the "symmetries" between nodes of a graphlet, there are 73 different orbits across all 2-5-node graphlets (see [Pržulj, 2007] for details). For each orbit j, one needs to measure the jth GDD, dGj(k), 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(k) is scaled as
S G j ( k ) = d G j ( k ) k {\displaystyle S_{G}^{j}(k)={\frac {d_{G}^{j}(k)}{k}}} to decrease the contribution of larger degrees in a GDD and then normalized with respect to its total area
T G j = ∑ k = 1 ∞ S G j ( k ) {\displaystyle T_{G}^{j}=\sum _{k=1}^{\infty }S_{G}^{j}(k)} giving the "normalized distribution"
N G j ( k ) = S G j ( k ) T G j {\displaystyle N_{G}^{j}(k)={\frac {S_{G}^{j}(k)}{T_{G}^{j}}}} . 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(G,H) between their normalized jth GDDs is:
… excerpt ends here. Continue reading the full article.
