Nature paper describes technique for extracting hierarchical structure of networks

May 01, 2008

Networks -- used throughout the sciences in the study of biological, technological, and social complexity -- can often be too complex to visualize or understand.

In a May 1 Nature paper, "Hierarchical structure and the prediction of missing links in networks," Santa Fe Institute (SFI) researchers Aaron Clauset, Cristopher Moore, and Mark Newman show that many real-world networks can be understood as a hierarchy of modules, where nodes cluster together to form modules, which themselves cluster into larger modules -- arrangements similar to the organization of sports players into teams, teams into conferences, and conferences into leagues, for example.

This hierarchical organization, the researchers show, can simultaneously explain a number of patterns previously discovered in networks, such as the surprising heterogeneity in the number of connections some nodes have, or the prevalence of triangles in a network diagram. Their discovery suggests that hierarchy may, in fact, be a fundamental organizational principle for complex networks.

Unlike much previous work in this area, Clauset, Moore, and Newman propose a direct but flexible model of hierarchical structure, which they apply to networks using the tools of statistical physics and machine learning.

To demonstrate the practical utility of their model, they analyze networks from three disparate fields: the metabolic network of the spirochete Treponema pallidum (the bacteria that causes syphilis), a network of associations between terrorists, and a food web of grassland species. Even when only half of the connections in these networks were shown to their algorithm, the researchers found that hierarchical structure can predict missing connections with an accuracy of up to 80 percent.

"Many networks, particularly those in the biological sciences, are not well understood," says Clauset, an SFI Postdoctoral Fellow. "But hierarchy offers a way to understand their large-scale organization and, from this, predict what interactions we might have missed."
-end-
The Santa Fe Institute (SFI) is an acknowledged leader in multidisciplinary scientific research. Its objectives are to discover and understand the common fundamental principles in physical, computational, biological, and social complex systems that underlie many of the most profound issues facing science and society today. By transcending disciplines, breaking academic molds, and drawing together an international network of unorthodox creative thinkers, SFI is an independent non-profit research and education center supported by grants, charitable giving, and corporate relationships.

Santa Fe Institute

Related Cluster Articles from Brightsurf:

Image release: Galaxies in the Perseus Cluster
New VLA images show how the crowded environment of a cluster of galaxies affects the individual galaxies, helping astronomers better understand some of the complex details of such an environment.

Is it one or two species? The case of the cluster anemones
Their scientific name is ''Parazoanthus axinellae'' and they are among the most fascinating corals of the Mediterranean Sea.

Discovered: Remnant of ancient globular cluster that's "the last of its kind"
A team of astronomers discovered a stellar stream composed of the remnants of an ancient globular cluster that was torn apart by the Milky Way's gravity 2 billion years ago, when Earth's most-complex lifeforms were single-celled organisms.

Stellar fireworks celebrate birth of giant cluster
Astronomers created a stunning new image showing celestial fireworks in star cluster G286.21+0.17.

Resistance to immunosurveillance favors cluster cancer metastasis
Researchers at Baylor College of Medicine show that circulating cancer cell clusters are more resistant to NK-cell mediated destruction than single cancer cells, leading to more cluster metastasis.

Age of NGC 6652 globular cluster specified
Senior Research Associate Margarita Sharina (Special Astrophysical Observatory) and Associate Professor Vladislav Shimansky (Kazan Federal University) studied the globular cluster NGC 6652.4.05957 and found out that its age is close to 13.6 billion years, which makes it one of the oldest objects in the Milky Way.

Rhythmicity of cluster headache
Although it is known that CH patients exhibit circadian rhythmicity of attacks, new data add a new feature with regard to the rhythmicity of attacks throughout the disease course.

Hubble snaps a crowded cluster
This sparkling burst of stars is Messier 75. It is a globular cluster: a spherical collection of stars bound together by gravity.

Ushering in ultrafast cluster electronics
A new computational method can help fast track the development of tiny, ultrafast electronic devices made from small clusters of molecules.

Aging a flock of stars in the Wild Duck Cluster
The way they move belies the true ages of the almost 3,000 stars populating one of the richest star clusters known.

Read More: Cluster News and Cluster Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.