Friday, May 20, 2011

#WIRELESS: "Smart Algorithm Untangles Network Snarls"

As the complexity of networks skyrockets, managers have been hard-pressed to come up with analytic tools that can cope, but now researchers claim to have a general-purpose technique that unsnarls nearly any network.

The driver nodes (red) that can control the rest of a network are often a very small in number, and seldom are they the most active nodes. Credit: Mauro Martino.

Researchers claim to have come up with a new computational model that can analyze any type of complex network—from the nodes of the Internet to the neurons of the brain—revealing the critical points that can be used to control the entire network...

Engineers have been using control theory to manage electronic networks since their invention—allowing the entire network to be controlled from just a few nodes with installed feedback loops that monitor input/output and adjust accordingly. Unfortunately, control theory usually assumes a closed system whose topology was as carefully architected by an engineer. However, today many networks—such as connected online communities—are self-organizing, creating a topology that is difficult to analyze and impossible to control with conventional theory.

Now researchers are claiming that a new algorithm can help steer even the most complex networks toward desired stable states, no matter if they are the result of engineering design or naturally evolved. This framework for controlling complex self-organized systems automatically identifies a set of "driver nodes," which can be used to guide the entire network's dynamics using well-known time-dependent control methodologies.

Interesting characteristics of these driver nodes, which would not have been predicted by most observers, is that the number of driver nodes in a network is inversely proportional not to the number of total nodes, but to how many connections are made by each node—called a network's degree-of-connectedness, or just "degree distribution."

For instance, networks with relatively "sparse" connections among inhomogeneous nodes are among the most difficult to control. This is because many nodes would have to be controlled to assert authority. In contrast, dense homogeneous networks can be controlled with far fewer driver nodes. For each type of network, the team calculated the percentage of driver nodes that need to be controlled in order to gain control of the entire system. The results ranged from as high as 80 percent for the most sparsely connected networks, to as few as 10 percent for the most dense.
Another result the researchers cited as particularly counterintuitive was that the specific location of driver nodes almost invariably avoids the highest-degree nodes in a network.

The new analytic technique, created by professor Jean-Jacques Slotine at the Massachusetts Institute of Technology in collaboration with professors Albert-Laszlo Barabasi and Yang-Yu Liu at Northeastern University, claim that their algorithm works for any real-life network—man-made or natural—including the Internet, cell-phone networks, social networks, gene expression networks, and the neural networks of the brain.
Further Reading: