Scale Free Networks

Why this is interesting?

Networks are everywhere, whether it’s our society, or our brain cells, or metabolic system or even the Internet and it’s really interesting how most of these networks follow the same pattern without being relevant to each other in any manner. It would also be very exciting to see if studying one network can help us to understand others like how understanding network of World Wide Web can help us killing the bacteria in our body.

Background

In 1998, when researchers thought to analyze World Wide Web, they expected it to be a random network because people follow what interests them and due to people often pursue different interests, from the tremendous number of pages, most of the pages should have approximately same number of followers. Random network theory also predicts that despite the random placement of links, the resulting system will be deeply democratic: most nodes will have approximately the same number of links. But the outcome of the research showed that more than 80% of the pages on the network had only four or less links and a small minority less than 0.01% of all the nodes had more than 1000 links. There was no normal distribution among the links, it was a continuously decreasing function which is termed as power-law. Specifically, a power law does not have a peak, as a bell curve does, and when plotted on a double-logarithmic scale, a power law is a straight line

Scale-Free Networks Abound

The main take away from this research was the web follow a network pattern which is controlled by few high potential nodes, also called as hub. Hubs have tremendous number of connections to other nodes, whereas most nodes just have few. The hubs can have thousands or even millions of links and in this sense, network appears to have no scale, and this is what we call, "Scale Free Networks". Airline system can be termed as scale free network as, few major airports act as a hub and control the major traffic of airlines. Viral marketing campaigns, for instance, often specifically try to target hubs to speed the adoption of a product.

 Researchers found a scale-free structure in the cellular metabolic networks in 43 different organisms. In such networks, each node is a particular molecule, and each link is a biochemical reaction. We found that most molecules participate in just one or two reactions, but a few (the hubs), such as water and adenosine triphosphate, play a role in most of them. Even the study of networks of actors in Hollywood, considering actors as node and appearing together as link, followed the scale free pattern. So the curiosity raised as how can systems as fundamentally different as the cell and the Internet have the same architecture and obey the same laws?

Nature of Scale Free Network: Growth and Preferential attachment

These two basic mechanisms-growth and preferential attachment-will eventually lead to the system's being dominated by hubs. Constant growth of the network gives older nodes, a greater opportunity to acquire links, which is called "Rich Gets Richer" principle that generally favor the early nodes, which are more likely to eventually become hubs. Furthermore, all nodes are not equal. When deciding where to link their web page, people can choose from a few billion locations. Yet most of us are familiar with only a tiny fraction of the full Web, and that subset tends to include the more connected sites because they are easier to find. By simply linking to those nodes, people exercise and reinforce a bias toward them. This process of "preferential attachment "occurs elsewhere. In Hollywood the more connected actors are more likely to be chosen for new roles. On the Internet the more connected routers, which typically have greater bandwidth, are more desirable for new users.

Reliability of Scale Free Networks 

Are these networks, dominated by few hubs, can be considered reliable? The research says that, complex systems with tremendous number of nodes area amazingly resilient against the accident failures because of their inhomogeneous topology, any random removal of nodes will take out mainly the small ones because they are much more plentiful than hubs. That’s the reason that hundreds of routers routinely malfunction on the Internet at any moment but the network rarely suffers major disruptions, Also people rarely notice the consequences of thousands of errors in their cells, ranging from mutations to mis-folded proteins. In fact, as many as 80 percent of randomly selected Internet routers can fail and the remaining ones will still form a compact cluster in which there will still be a path between any two nodes

But a reliance on hubs has a serious drawback: vulnerability to attacks. Study shows that the removal of just a few key hubs from the Internet splintered the system into tiny groups of hopelessly isolated routers. Similarly, knockout experiments in yeast have shown that the removal of the more highly connected proteins has a significantly greater chance of killing the organism than does the deletion of other nodes. These hubs are crucial-if mutations make them dysfunctional, the cell will most likely die.

Apart from robustness and reliability on hubs, I find scale free network also has issue of trustworthiness, i.e. Information spreading through hubs, how trustworthy are they? For instance, there are only few media houses that control the news all over the world and rest of the media follows them. But we also have to be sure, that these news media houses are dependable.

Conclusion

For transportation, transmission and communications systems (such as the Internet), congestion along specific links is a major consideration: too much traffic on a particular link can cause it to break down, leading to the potential failure of other links that must then handle the spillover. Determining whether a network is scale-free is important in understanding the system's behavior, but other significant parameters merit attention, too. For instance, immunizing hubs might not be sufficient to stop the spread of a disease; a more effective solution might be found by considering not just the number of connections a person has but also the frequency and duration of contact for those links. Behavior of scale free networks encourages researchers from different area to collaborate and model the network, draw the pattern and work to enhance the reliability of network.