0
$\begingroup$

I'm interested in two tasks:

  1. Find a decomposition (is it unique?) of a graph $G$ into its graphlets.
  2. Construct a graph starting from a set of graphlets.

What is the most efficient way to do it?

Unfortunately, I'm not very familiar with Spectral Graph Theory. I tried reasoning about the eigendecomposition of the Laplacian matrix, but it is not clear how a eigenvector correspond to a graphlet.

On the other hand, approaching the problem computationally has for me some issues, e.g. a 99 nodes graph has 33 3-graphlets or a node can belong to more than 1 graphlet?

$\endgroup$
0
$\begingroup$

Both problems are very hard.

For (1), there exist practical algorithms for counting the numbers of restricted graphlets (k=3,4) such as PGD or (k=5) ESCAPE. Unfortunately, even these will have trouble with very large graphs due to the computational complexity of the problem.

The Laplacian spectrum has deep relations to graph topology, but precise relations between graphlets and spectrum are still very tough to find. See here for information on 'cospectral graphs': graphs with identical spectra, but differing topology.

For (2), just a list of graphlets is not enough -- one needs the relative positions of the graphlets as well. Unfortunately, the problem is not very interesting once you have relative positions and graphlets as that is very close to having the original graph already.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.