Subgraphs with diameter 2

102 Views Asked by At

When examining the modularity of graphs or networks, concepts like "blocks", "clusters", or "communities" are used, more or less strictly defined as (maximal) subgraphs with some given properties.

A natural generalization of cliques (as maximal complete subgraphs, having diameter 1) would be "diam-k-cliques", i.e. maximal subgraphs with diameter k. Under which name are such graphs filed and can be googled? And which efficient methods to find them are there - or some statistics on them? Is there a Mathematica function for it?

To make "diam-2-cliques" more community-like one might add the simple requirement that the minimal degree of such a subgraph must be 2 (to avoid star graphs as "communities").