Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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]:

enter image description here

enter image description here

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?

share|improve this question
    
For each edge u <-> v in the tree, create max - 2 fresh vertices and attach them all to each other and to u and v? –  Rahul Narain May 30 '13 at 8:13
    
By the way, how do you get the 5-clique in Wikipedia's example by starting with a tree and replacing edges with cliques? I think your definition of block graph might be wrong. –  Rahul Narain May 30 '13 at 8:15
    
@RahulNarain That's a good point. The definition is from here, definition ii. That is another weakness of my current function (the current answer doesn't "fix" that either, but the mistake was mine in not mentioning it). –  mrm May 30 '13 at 17:46

2 Answers 2

up vote 1 down vote accepted

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:

Tree

to this graph:

Block Graph

share|improve this answer

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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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