News & AnalysisPhysics

Scientific Link-Up Yields ‘Control Panel’ for Networks

+ See all authors and affiliations

Science  13 May 2011:
Vol. 332, Issue 6031, pp. 777
DOI: 10.1126/science.332.6031.777

You are currently viewing the summary.

View Full Text

Summary

A trio of physicists has found a way to determine the smallest number of nodes that must be externally controlled to force a given network from any initial state to any desired final state. That number can be calculated by brute force, but the size of the computation grows exponentially with the number of nodes. So the researchers take a more efficient tack, as they report this week in Nature. For each node in a network, they randomly erase all but one outgoing link and all but one incoming link to create a skeleton called a "matching." They apply a simple technique to make sure the matching contains as many links as possible. In the end, some nodes are left disconnected. And those nodes form a set that can control the original network.