×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Extracting Meaning From the Structure of Networks

timothy posted more than 5 years ago | from the which-outhouse-is-on-top dept.

Networking 31

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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

31 comments

Omygosh what baloney (1, Funny)

Anonymous Coward | more than 5 years ago | (#23286308)

Can we have some real science please ?

Re:Omygosh what baloney (1)

mrbluze (1034940) | more than 5 years ago | (#23286628)

Can we have some real science please ?

Let me see... *tap tap tap* .. hmmm...

.. Computer says no I'm afraid.

Re:Omygosh what baloney (0, Troll)

2.7182 (819680) | more than 5 years ago | (#23286744)

The parent is no troll! Yech this stuff is so silly. What are the applications that aren't "promised" for the future ? I am shocked that such vague nonsense of this is in the journal Nature.

Skeptics and arrogance. (2, Informative)

TapeCutter (624760) | more than 5 years ago | (#23288248)

"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 [wikipedia.org] 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.

Re:Omygosh what baloney (1)

verySmartApe (1053716) | more than 5 years ago | (#23288802)

Yes, the GP is not a troll, he's a karma whore. If Roland posts a science article, the whores will denounce it as fast as they can in expectation that they will get mode points, and those that actually read the article will support them later. The sad thing is that 9 times out of 10 the article really will be crap. But I don't see any problem with this work. It's not revolutionary, but I wouldn't by any means call it bad science.


So, to the P&GP: enough with vague denunciations. If you have a problem with the article, what is it?

poop? (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#23286316)

poop.

Re:poop? (1)

Foobar of Borg (690622) | more than 5 years ago | (#23294154)

Considering this is a Roland article (and even more particularly silly than usual), I think you have summed up quite succinctly all the discussion that needs to be had on it here.

Roland the Plogger again (3, Informative)

Animats (122034) | more than 5 years ago | (#23286422)

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 [nanounion.net]:

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.

Re:Roland the Plogger again (1)

Winawer (935589) | more than 5 years ago | (#23286534)

The article is full of links: to the Nature article webage, to the authors' homepages, and even to a link with a .PDF containing the article itself. Did you actually read the ZDNet article?

Re:Roland the Plogger again (1)

Giloo (1008735) | more than 5 years ago | (#23286860)

You must be new here...

Re:Roland the Plogger again (2, Insightful)

Winawer (935589) | more than 5 years ago | (#23286926)

If by "new" you mean "I usually read the articles and don't comment often", then you're right. Are you trying to tell me that I did something wrong?

Re:Roland the Plogger again (1)

Raenex (947668) | more than 5 years ago | (#23289404)

It's just an old Slashdot joke. From Wikipedia: [wikipedia.org]

(Invoked frequently after a poster complains of a common Slashdot issue such as duplicate stories or perceived bias by certain editors)
In this case, noting that people on Slashdot in general don't read the articles. Don't take it personally -- the joke isn't meant to be at your expense.

Re:Roland the Plogger again (1)

Animats (122034) | more than 5 years ago | (#23292056)

The problem is that the Slashdot article has links to places that get Roland the Plogger ad revenue, but doesn't have a link to the original paper. This is typical Roland the Plogger behavior.

Re:Roland the Plogger again (1)

Winawer (935589) | more than 5 years ago | (#23292754)

Fair enough. Given that he provided copious links to the original articles in his blog post and that he provided a reasonably thorough summary (for a journalist) of the work, I can't say that this really bothers me at all. However, as is clear, I'm not overly familiar with Slashdot etiquette, so I'll just take your word for it that it's a Bad Thing.

Re:Roland the Plogger again (1)

jc42 (318812) | more than 5 years ago | (#23288208)

We further show that knowledge of hierarchical structure can be used to predict missing connections in partly known networks with high accuracy, ...
It's a scheme for ... inferring what links might be missing.

And this is the point where any sensible person would get a distinct paranoid feeling. It's not hard to imagine how this might be misused.

Thus, I have a large number of connections to other software developers. I also have a lot of connections to other musicians. I have a CS degree from the U of Wisconsin, which gives me another large set of links. A close friend in my high school class is CEO of a corporation that everyone here has heard of. My wife and I own a Mini Cooper (great car!), which gives us another growing set of connections. And on and on, for a fair number of unrelated subject areas.

Suppose now that an analysis of the various sets that I'm involved with turns up a close friend of Osama bin Laden in each set. The obvious fear is that the above heirarchical-analysis scheme will fill in the "missing link" between Osama and myself. Since I live in the US, this would make me highly suspect to a lot of people currently in power.

Of course, in a rational world, this scenario would actually show the silliness of attempts to infer such links, as well as the absurdity of imposing a heirarchy on the structure of an unstructured rat's nest of links like the Internet. But we don't really live in a rational world, do we?

A more rational world (2, Insightful)

TapeCutter (624760) | more than 5 years ago | (#23288604)

"But we don't really live in a rational world, do we?"

Parinoia is an ally of irrationality.

Your argument boils down to "a tool can be used for good or evil", now since good and evil are subjective that reduces to "a tool can be used". Taken in the context of your post, this implies you are a Ludite but I don't think you are since a Ludite would not have the means to post on slashdot, ergo your post is irrational not the world.

"It's not hard to imagine how this might be misused [by the US administration]"

A bad tradesman will always blame his tools. The problem you speak of has nothing to do with the mathematical and scientific tools the US administration abuse on a regular basis.

As Carl Sagan put it, "Science is a candle in the dark". If you would like to live in a more rational world, please try and avoid inadvertently snuffing it out with parinoia regardless of wether the parionia is justified or not.

Pencilnecked foureyed plagiarist (1)

Anonymous Coward | more than 5 years ago | (#23286426)

Roland Piquepaille writes
No he doesn't, he copies and pastes.

Nature? (1, Offtopic)

ponraul (1233704) | more than 5 years ago | (#23286436)

How did such a poorly written, presented and researched paper get into Nature? Is it April 1 again?

Re:Nature? (1)

cdw38 (1001587) | more than 5 years ago | (#23287924)

Clauset, Newman, and Moore are three of the most respected and well-known networks researchers. I'm not sure what you mean by being poorly presented or researched; care to elaborate? But how this blog post makes the front page of /. is beyond me. It tells you absolutely NOTHING about the actual paper.

Brains. (0)

Anonymous Coward | more than 5 years ago | (#23286494)

Networks have always been intelligent, summed from their pulses. And in the case of loosely coupled networks (ie. abstract entities such as Gods), then "See the wheels turn for you, know the final truth at last. That we are here now and always were."

Can we get a Roland filter? (0)

Anonymous Coward | more than 5 years ago | (#23286548)

You know, like we used to have for Jon Katz? So we don't have to even see anything he submits, since it's mostly old news or just recycled from a more credible source?

Re:Can we get a Roland filter? (3, Insightful)

mrbluze (1034940) | more than 5 years ago | (#23286672)

You know, like we used to have [a filter] for Jon Katz? So we don't have to even see anything he submits, since it's mostly old news or just recycled from a more credible source?

I was about to take offence at that statement, but then I realized I'm not Roland Pipe.. pip.. something.

But I had to laugh at the title. The meaning of the structure of networks is a stupid idea. The purpose maybe, the philosophy behind the structure maybe. But the meaning of? Go ask a Dadaist.

Re:Can we get a Roland filter? (3, Interesting)

mrogers (85392) | more than 5 years ago | (#23290516)

The meaning of the structure of networks is a stupid idea. The purpose maybe, the philosophy behind the structure maybe. But the meaning of?

In the context of the research (using known parts of a network's structure to predict unknown parts), I don't think the word "meaning" is out of place at all. A hierarchical clustering algorithm will extract some kind of hierarchy from any network you throw at it - but does that hierarchy mean anything? Does it contain information? This new research suggests that, for certain kinds of network, the extracted hierarchy is meaningful, because it allows us to make predictions about unknown parts of the network that we could not make without first extracting the hierarchy.

That's actually quite a profound discovery, because in the last ten years, complex networks (especially small-world and scale-free networks) have been held up as models of natural decentralisation and non-hierarchical self-organisation in many fields, from ecology to politics to communications to epidemiology. If such networks turn out to contain meaningful hierarchies (i.e. hierarchies that actually tell us something about how they function) then much of the rhetoric about complex systems will be turned on its head.

Article PDF (2, Informative)

apankrat (314147) | more than 5 years ago | (#23286604)

Re:Article PDF (1)

CurtMonash (986884) | more than 5 years ago | (#23289344)

Thanks.

I've having trouble seeing meat there, however. I.e., I haven't detected enough detail to tell me what to think about the generality of their claims.

CAM

Re:Article PDF (0)

Anonymous Coward | more than 5 years ago | (#23293602)

I agree, the paper doesn't actually say anything other than advertising.

Piqued interest (1)

xactuary (746078) | more than 5 years ago | (#23286676)

If Roland Piquepaille posts another gee-wiz article on Slashdot with only this first post, does anyone care?

Is the hierarchical character intrinsic? (1)

karlandtanya (601084) | more than 5 years ago | (#23290764)

I'm not a mathematician, so maybe one can answer this question? I know that I can take pretty much any open (e.g. not a ring) topology and document it in a hierarchical model. Heck, if I'm permitted just a few multiple paths, I can model pretty much any topology with a such a drawing. Think org charts in any large corporation. Abstraction is necessary for generalization, and models are absolutely necessary. Studying your model instead of your subject is a trap. The article presents a model for review; I guess it's up to the scientfic community to evaluate the applicability of the model to any particular subject.

Danger of becoming another quantum theory (1)

Ox0065 (1085977) | more than 5 years ago | (#23291930)

Don't get me wrong I think it sounds like a great tool for abstracting complex systems into neat boxes for human consumption.

I'm just imagining we'll have researchers wanting venture capital to create networks that can re-organise themselves simply by changing the hierarchy model used (perspective)
The danger I see in this is people confusing the network in reality with a model of how we might perceive it, or perhaps of people being confused long enough to cough up the dough.

or perhaps people thinking that their network topology can be rationalised by making a more rational looking model of an irrational system, without real changes being made... ...it sounds like a powerful tool that could be very dangerous in stupid hands.
Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...