# What is a “hierarchical random graph”?

I was linked to Clauset, Moore, & Newman (2008) "Hierarchical structure and the prediction of missing links in networks" on Twitter and have a hard time following the definition of a "hierarchical random graph." Google searching suggests the term has only been used in research papers and therefore doesn't have anything like a Wikipedia entry for me to look up.

Specifically, I want to fully understanding the meaning of Figure 1 in the aforementioned paper. Any helpful walkthroughs or explanations?

-
more on the hierarchical random graphs from the authors – Artem Kaznatcheev Jan 27 '12 at 6:15

A heirarchical random graph is a random graph whose definition encodes some information about the expected community structure of the graph. The definition is given in terms of a dendrogram (a fancy word for a rooted tree) which gives information about the probability that any two nodes in the graph are connected.

The best way to explain this is by example. Consider the following dendrogram:

         O
/ \
/   \
A     B
/ \   / \
C   D E   F


Here the nodes O, A, B, C, D, E and F have probabilities associated with them, such that the probability for a node higher up the graph is strictly less than a node higher down the graph. Here, for example, we require that p(O) < p(A) < p(C), and p(O) < p(A) < p(D), etc. The nodes C, D, E and F represent subsets of the vertices in the random graph whose structure we are describing (in the simplest case they would each represent a single node, but more commonly they will represent a subset of nodes).

We declare that any two vertices are joined by an edge with a probability corresponding to their lowest common ancestor in the dendrogram. For example, vertices in C are connected to other vertices in C with probability p(C). Since C and D share a common ancestor A, a vertex in C is connected to a vertex in D with probability p(A). And since the lowest common ancestor of C and E is O, a vertex in C is connected to one in E with probability p(O).

Because of the inequalities satisfied by the probabilities, this will naturally generate a graph with community structure (ie. clusters of mutually connected vertices with a few connections to vertices in other clusters) and we call it 'heirarchical' because, by the nature of the dendrogram, we can form communities of communities, communities of communities of communities etc.

-