Research: Extracting the Structure of Networks

Extracting the Structure of Networks
ZDNet (05/03/08) Piquepaille, Roland

Santa Fe Institute researchers Aaron Clauset, Cris Moore, and Mark Newman have developed an algorithmic method that enables the automatic extraction of the hierarchical structure of networks, and they say the results "suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena." The researchers suggest a direct yet flexible hierarchical structure paradigm that is applied to networks via machine learning and statistical physics tools. Analysis of networks from three distinct disciplines shows that hierarchical structures can predict missing network links with up to 80 percent precision, even in scenarios where only 50 percent of connections are exposed to the algorithm. The May 1 issue of Nature details Clauset, Moore, and Newman's work, and notes in the editor's summary that the data describing complex networks is frequently biased or incomplete. An accompanying article by Boston University's Sid Redner says that "focusing on the hierarchical structure inherent in social and biological networks might provide a smart way to find missing connections that are not revealed in the raw data--which could be useful in a range of contexts." The SFI researchers think that their algorithms are applicable to nearly all network categories, ranging from biochemical networks to social network communities.
Click Here to View Full Article