Dendrogram model of random network

from Complexity digest :

02.03. Hierarchical Structure And The Prediction Of Missing Links In
Networks , Nature

Excerpts: Networks have in recent years emerged
as an invaluable tool for describing and quantifying complex systems in many
branches of science.
(...) We further show that knowledge of hierarchical
structure can be used to predict missing connections in partly known networks
with high accuracy, and for more general network structures than competing
techniques. Taken together, our results suggest that hierarchy is a central
organizing principle of complex networks, capable of offering insight into many
network phenomena.

* [10] Hierarchical Structure And The Prediction
Of Missing Links In Networks, Aaron Clauset, Cristopher Moore, M. E. J. Newman,
08/05/01, DOI:
10.1038/nature06830, Nature 453, 98-101

[10] http://www.nature.com/nature/journal/v453/n7191/full/nature06830.html

Because the idea looks so simple, I even wonder why this work is published in Nature. :) The author fits the "Hierarchical Random Graph Model (HRG)" to the observed network using MCMC method. HRG is described by the dendorgram, which is mainly used for the visualization of hierarchical clustering result in multivariate statistics.

In fact, the algorithm to decompose the network into nested cohesive blocks was also suggested before. The most well-known algorithm in social network community is the algorithm using k-component of James Moddy and Douglas R. White, which is stated in "James Moody, Douglas R. White. 5/9/2001. Structural Cohesion and Embeddedness: A hierarchical conception of social groups.Embeddedness".

However, like the other works done by Clauset, this approach is very intuitive and well-modeled statistically. I hope that this work may be ueful for my ongoing research, bernoulli random triad graph.