Scientists describe 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.”

Source: Santa Fe Institute

Explore further: New filter could advance terahertz data transmission

add to favorites email to friend print save as pdf

Related Stories

The importance of building small things

Jan 22, 2015

Strong materials, such as concrete, are usually heavy, and lightweight materials, such as rubber (for latex gloves) and paper, are usually weak and susceptible to tearing and damage. Julia R. Greer, professor ...

How terrorists use Twitter to become 'brand ambassadors'

Dec 08, 2014

On an overcast afternoon in London in May 2013, an off-duty soldier named Lee Rigby was murdered near his barracks in Woolwich, southeast London. Rigby's killers were two young British men of Nigerian descent, ...

An egalitarian Internet? Not so, study says

Jun 10, 2011

(PhysOrg.com) -- The Internet is often thought of as a forum that enables egalitarian communication among people from diverse backgrounds and political persuasions, but a University of Georgia study reveals ...

Vine-tree-like CNT architectures

Nov 03, 2014

The vine-tree structure is widely observed in nature when the plant has a growth habit of trailing or climbing stems. The vines use trees for growth rather than devoting energy to development of supportive ...

Recommended for you

New filter could advance terahertz data transmission

21 hours ago

University of Utah engineers have discovered a new approach for designing filters capable of separating different frequencies in the terahertz spectrum, the next generation of communications bandwidth that ...

The super-resolution revolution

21 hours ago

Cambridge scientists are part of a resolution revolution. Building powerful instruments that shatter the physical limits of optical microscopy, they are beginning to watch molecular processes as they happen, ...

A new X-ray microscope for nanoscale imaging

Feb 27, 2015

Delivering the capability to image nanostructures and chemical reactions down to nanometer resolution requires a new class of x-ray microscope that can perform precision microscopy experiments using ultra-bright ...

Top-precision optical atomic clock starts ticking

Feb 26, 2015

A state-of-the-art optical atomic clock, collaboratively developed by scientists from the University of Warsaw, Jagiellonian University, and Nicolaus Copernicus University, is now "ticking away" at the National ...

User comments : 5

Adjust slider to filter visible comments by rank

Display comments: newest first

Ragtime
1 / 5 (3) May 01, 2008
By AWT the hiearchy of nested foam is given by multinomial distribution of causual events in inertial chaos. We can imagine the numbers as a countable particles, then the distribution of gradients in such particles corresponds the distribution of fluctuations inside of random field of colliding particles (condensing supercritical fluid, for example). By such way, the hiearchy is imanent part of every observable reality, composed of inertial gradients. If we can count the elements of system, then the formation of hiearchic structures between them is undeniable.
thales
not rated yet May 01, 2008
Makes me wonder how this applies to brain organization, since it is a network of neurons. The brain could then be classified by a hierarchy of structures! I'd bet this model could also be used to determine the order in which different areas of the brain developed. By AWT!
Ragtime
May 02, 2008
This comment has been removed by a moderator.
thales
not rated yet May 05, 2008
Mmmmm... quantum foam...
nilbud
1 / 5 (1) May 05, 2008
Don't forget quantum prayer raggy and any other bullshit you can slap the word quantum in front of.
A) It's "an aether" although it's spelled ether.
B) Professor Penrose is not referred to as Sir Penrose, or Penny Henny, or Hey Jimbo.
Alexa
not rated yet May 06, 2008
Sorry, but you're still not so respectful authority for me, as the Encyclopædia Britannica is:

http://www.britan...-Penrose

Professor is the name of occupation, which you can change anytime over life. Do you prefer to be titled as a Floor manager Jimbo or Rabbit feeder Henny?

I don't think so.

The "quantum" denomination means "stuff, whose density increases proportionally with energy density". Which is basically an insintric property of every foam, therefore the word "quantum" is redundant here.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.