Graphlet

From TrustLet, a free, collaborative project for collecting and analyzing information about trust metrics.

Here on Trustlet we feel some elective affinity with graphlet so this page. Graphlets are small connected non-isomorphic subgraphs of a large network

From Biological network comparison using graphlet degree distribution:

For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought.

We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes ‘touching’ k edges, into distributions measuring the number of nodes ‘touching’ k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2–5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network ‘agreement’ measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdös–Rény, random scale-free, or Barabási–Albert scale-free networks.

This article is a stub. You can help by expanding it.