Communications of the ACM
Powerful New Metric Quickly Reveals Network Structure at Multiple Scales
Researchers testing the Onion Decomposition on the stanford.edu World Wide Web network domain found an unexpected subnetwork structure.
Credit: Hbert-Dufresne, Allard, and Grochow
Researchers at the Santa Fe Institute and the University of Barcelona have developed the Onion Decomposition, a metric that bypasses the limitations associated with other methods of network analysis.
The researchers note the new metric simultaneously reveals network structure at the microscopic, mesoscopic, and macroscopic levels, and analyzes a network by peeling away "layers" of nodes that have the same number of connections, usually starting with the layers having the fewest number of connections.
The researchers wanted to build an algorithm that capitalizes on the benefits of k-core decomposition, but also uses layer-level information to provide insights about the network at multiple scales.
They successfully tested the new method on real-world datasets, including the Northwestern U.S. power grid and the road system of Pennsylvania. In both cases, the metric delivered accurate pictures of the network structures at different scales.
The new analysis showed by removing a few nodes of the power grid network, its overall connectivity would quickly collapse. The road network proved to be more robust and would remain relatively well connected despite the removal of a few nodes, the researchers say.
The Santa Fe Institute's Laurent Hebert-Dufresne says the new metric could be a valuable first step for network analysis that "allows us to understand, at a glance, whether a network is tree-like or grid-like, how heterogeneous it is, and even identify surprising subgraphs."
From Santa Fe Institute
View Full Article
Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA
No entries found