Random graphs defined by a set of tiles

Question

Related to this question, which I asked at MSE, I'd like to ask this one here:

Consider a (large) graph $G$ and its multi-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the multi-set of pointed graphs (one for each vertex) containing the vertex and all of its neighbours, together with all the edges between them.

Define the set $\Gamma(T)$ of all graphs having the same tile set $T$.

How would you calculate some expected properties $P$ of these graphs in the sense of "almost all graphs in $\Gamma(T)$ have property $P$". If "almost all" was to mean "in the limit $|V(G)| \rightarrow \infty$" one would interpret a given tile set $T$ as defining ratios of tiles, i.e. counting relative instead of absolute numbers per single (isomorphism class of) tile.

There are two "properties" literally all graphs in $\Gamma(T)$ do have: the (same) degree distribution and the (same) distribution of clustering coefficients. By which means do I find and calculate other properties that almost all graphs in $\Gamma(T)$ have?

Answer 1

The question you ask is, in my opinion, extremely important: decomposing a graph into a (small) set of small graphs (the tiles or ego-centered sub-graphs, for instance), and then characterizing how these small graphs are combined in the initial graph and how this induces its properties, certainly is a great way to get insight on the graph under concern. This is a typical reductionnist approach.

Let me explain a small step we made in this direction a few years ago. First notice that many graphs met in practice have a high local density, captured, e.g., by the clustering coefficient (which is nothing but the density of your tiles). We said that this may be seen as an indication of the fact that these graphs are composed of many cliques combined together. In other words, they are projection of bipartite graphs (either a known bipartite graph, or built from an edge clique cover of the graph, or another set of cliques such that each edge belongs to at least one). The structure of this bipartite graph tells what clique sizes arisen and how they are combined to get the whole graph.

 

 

We explored in particular two kinds of bipartite graphs: random ones with prescribed degree distributions, and some produced by a kind of preferential attachment. More details are available in the paper Bipartite Graphs as Models of Complex Networks, by Jean-Loup Guillaume and myself, and formal analysis is available in A scale-free graph model based on bipartite graphs by Etienne Birmelé. It is shown in particular that the degree distribution and clustering coefficient of graphs under concern may be seen as consequence of such an underlying bipartite structure.

One may iterate this idea and describe the obtained bipartite graph by a tripartite graph encoding its bipartite cliques, see A random model that relies on maximal bicliques to preserve the overlaps in bipartite networks by Fabien Tarissan and Lionel Tabourier. More theoretical work on the iteration of such operators is available in On the Termination of Some Biclique Operators on Multipartite Graphs by Christophe Crespelle, myself, and Thi Ha Duong Phan, as well as in Termination of Multipartite Graph Series Arising from Complex Network Modelling by myself, Thi Ha Duong Phan, Christophe Crespelle, and Thanh Qui Nguyen.

This is quite far from what you primarily ask, though, as this is focused only on clique tiles that are not necessarily defined as in your post. Still, I hope this gives some insight.

Answer 2

To whom it may be of interest: Find here a short paper where I describe a graph generation model that takes a set of ego-networks and ties them together in a systematic (and possibly realistic) way. The ego-networks are not fully specified, only their size (number of nodes $n$) and their density (number of edges $m$) are given. Beyond that, they are assumed to be Erdős–Rényi graphs from $G(n,m)$. The graph as a whole is composed of many such small Erdős–Rényi graphs, while other (more structured) characterizations of the ego-networks are conceivable. The paper is basically an elaboration of Matthieu Latapy's first comment on the question.

The model bears some similarity with configuration models.

Answer 3

You may be interested in research by Nicolas Trotignon, among others, which is somewhat complementary: characterising families of graphs by a subset of patterns (graphs) that do not appear in them. E. g. triangle-free graphs.

Nice idea btw, your generation model based on tiles / ego networks.