How can I construct "better" block graphs?

Question

A graph is a block graph if it can be constructed from an undirected tree by replacing each edge with a clique. My method of generating "random" block graphs is as follows. The parameters are the number of blocks and the maximum size of any clique.

RandomBlockGraph[b_, max_] :=
  Module[{g = Graph[{}], L = Table[i, {i, 1, b*max}]},
    For[i = 1, i <= b, ++i,
      r = RandomInteger[{2, max}];
      h = IndexGraph[CompleteGraph[r], First[L]];
      L = Drop[L, r - 1];
      g = GraphUnion[g, h];
    ];
      Return[g];
  ];

The function "glues" together cliques. The weakness is that right now, a vertex is joining at most 2 cliques. Here's a few examples of what the function spits out with RandomBlockGraph[3, 5]:

It would be nice if my function could say take a tree, and then actually replace every edge with a clique. This would make it possible to get as an output say a star graph on $n$ vertices, where every edge was replaced with a clique. The current function can't do this, since every vertex joins at most 2 cliques.

How can I modify (or write a better function) for generating block graphs such that a vertex can join more than just 2 cliques?

Answer 1

You can simply replace each edge of the tree with the edges of the click. The only point is to avoid repeated identifiers for the new vertices.

click[v1_, v2_, n_Integer] := First@# \[UndirectedEdge] Last@# & /@ Subsets[Join[{v1, v2}, {v1, v2, #} & /@ Range[n - 2]], {2}];
blockGraph[tree_Graph, max_Integer] := Graph@Flatten[click[First@#, Last@#, RandomInteger[{2, max}]] & /@ EdgeList[tree]];

Here is a sample call:

tree = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 5}];
blockGraph[tree, 5]

That converts this tree:

to this graph:

Answer 2

Here's another method. Let $G = K_n$, and choose a vertex $v \in V(G)$ uniformly and independently at random. Glue a new clique to $v$, and continue this process until the desired number of blocks have been obtained. This handles the problem mentioned by Rahul Narain in the comments: starting from a tree, one can't construct a 5-clique such as the one in Wikipedia's example.

RandomBlockGraph[max_, b_] :=
  Module[{g = 
     CompleteGraph[RandomInteger[{2, max}], VertexLabels -> "Name", 
      ImagePadding -> 20]},
   For[i = 1, i <= (b - 1), ++i,
    v = RandomChoice[VertexList[g]];
    newblock = 
     UndirectedEdge @@@ 
      Subsets[Union[{v}, 
        Range[Max[VertexList[g]] + 1, 
         Max[VertexList[g]] + RandomInteger[{2, max-1}]]], {2}];
    g = EdgeAdd[g, newblock];
    ];
   Return[g];
   ];

The usage is simple:

GraphPlot[RandomBlockGraph[3, 4], VertexLabeling -> True]