Extracting Meaning From the Structure of Networks

Roland Piquepaille writes "Networks are used to represent the structure of complex systems, including the Internet or social networks, but often these descriptions are biased or incomplete. Now, researchers at the Santa Fe Institute (SFI) have shown that it's possible to extract automatically the hierarchical structure of networks. The researchers say their results 'suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.' They also think that their algorithms can be applied to almost every kind of networks, from biochemical networks (protein interaction networks, metabolic networks or genetic regulatory networks) to communities in social networks. But read more for additional references and some pictures about hierarchical networks and their applications."

Comments

Roland the Plogger again

[Animats]

As is typical of a Roland the Plogger article, there's no link to the original article, but there's a link to his ad-laden blog. Here's the abstract:

Hierarchical structure and the prediction of missing links in networks
Nature 453, 98 (2008). doi:10.1038/nature06830
Authors: Aaron Clauset, Cristopher Moore & M. E. J. Newman
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 techniques. Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.

So now, unlike Roland, we now have a clue what's being talked about. It's a scheme for finding some structure in networks and inferring what links might be missing.

Article PDF

[apankrat]

http://www-personal.umich.edu/~mejn/papers/cmn08.pdf

Skeptics and arrogance.

[TapeCutter]

"Yech this stuff is so silly. [snip] I am shocked that such vague nonsense of this is in the journal Nature."

The thing we should all be 'shocked' by is the number of so called geeks who dismiss genuine science/math with nothing more than vauge handwaves and ad-homs. I think it might be connected to a general lack of understanding of scientific skepticisim or perhaps it's just plain old arrogance.

The novel finding in the paper is that they can use the properties of networks to automatically predict missing links in the network under study.

I haven't read the paper but I think it's reasonably obvious that if you 'pick up' any particular node in a network and call it the root you will have a hierarchy. For example imagine a small fishing net, pick the net up by any knot and the rest of the net can be seen as a hierarchy dangling under it, of course the hierarchy will differ depending on which knot you choose. Now the abstract claims they can use this to not only find broken strings in the net but as a general technique to find missing links in ANY network.

"What are the applications that aren't "promised" for the future?"

Firstly that's an irrelevant question when considering wether something should(n't) be published in Nature. Secondly to get an idea of possible future applications in the real world I suggets you take a look at the history of logistics and it's connection to WW2, or perhaps follow up the more than reasonable speculation in TFA.

As an aside, anyone with historical knowledge of the periodic table will know that it's invention predicted missing elements that in subsequent investigations over many years were found in the lab using their predicted properties, helium being the classic example since it was found in the Sun not the lab. This may or may not be as important but only time can be the judge of that.

Disclaimer: IAACS with a major in OR.