Vidal's library
Title: Hierarchical structure and the prediction of missing links in networks
Author: Aaron Clauset, Cristopher Moore, and M. E. J. Newman
Journal: Nature
Volume: 453
Number: 7191
Pages: 98--101
Year: 2008
DOI: 10.1038/nature06830
Abstract: Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, in which vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases the groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (protein interaction networks, metabolic networks or genetic regulatory networks) or communities in social networks. Here we present a general technique for inferring hierarchical structure from network data and show that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right-skewed degree distributions, high clustering coefficients and short path lengths. 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 techniques8. Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.



@Article{clauset08a,
  author =	 {Aaron Clauset and Cristopher Moore and
                  M. E. J. Newman},
  title =	 {Hierarchical structure and the prediction of missing
                  links in networks},
  journal =	 {Nature},
  year =	 2008,
  volume =	 453,
  number =	 7191,
  pages =	 {98--101},
  abstract =	 {Networks have in recent years emerged as an
                  invaluable tool for describing and quantifying
                  complex systems in many branches of science. Recent
                  studies suggest that networks often exhibit
                  hierarchical organization, in which vertices divide
                  into groups that further subdivide into groups of
                  groups, and so forth over multiple scales. In many
                  cases the groups are found to correspond to known
                  functional units, such as ecological niches in food
                  webs, modules in biochemical networks (protein
                  interaction networks, metabolic networks or genetic
                  regulatory networks) or communities in social
                  networks. Here we present a general technique for
                  inferring hierarchical structure from network data
                  and show that the existence of hierarchy can
                  simultaneously explain and quantitatively reproduce
                  many commonly observed topological properties of
                  networks, such as right-skewed degree distributions,
                  high clustering coefficients and short path
                  lengths. 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 techniques8. Taken
                  together, our results suggest that hierarchy is a
                  central organizing principle of complex networks,
                  capable of offering insight into many network
                  phenomena.},
  doi = 	 {10.1038/nature06830}
}
Last modified: Wed Mar 9 10:16:53 EST 2011