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:
/ \ / \
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.