Scale Free Networks

Scale Free Networks and the

Small World Phenomenon

Over the last few years, an overwhelming amount of attention has been giving to a new science of networks. This new cohort of research takes a closer look at trying to understand the rules behind how certain networks are formed and how they evolve. This new understanding of networks is starting to depart from its previous graph theory oriented background and branch across to more sociology based field of studies, in order to help scientist obtain a better idea of how anything from ideas, diseases, information, and influence can spread from one point to another.

At the center of this research are what scientist call small world networks. Their name comes from the first glance appearance that the actual network or world tends to be far smaller than at first assumed. Resulting in two nodes of the network being connected by far fewer nodes that expected. The most typical example in explaining this phenomenon is what is usually referred to as having "six degrees of separation" between any two humans in the world, meaning that any two people in a world of 6 billion inhabitants are connected by only six or fewer connections in between them.

Scientists are discovering these small world networks to be all around us. As we will see, these somewhat disordered small world networks hold tremendous potential as models for the interaction networks of more complex systems. It is by looking at these networks as an "integral part of a continuously evolving and self-constituting system" that can help us better understand the world around us.

Common Types of Networks

The origin of the infrastructure of the Internet can be easily traced to Paul Baran. He was working for a company called RAND Corporation who received a government contract from the defense department to investigate different types of network. As a result of the Cold War, they were looking for a network that would be best suited for an information infrastructure that would be able to survive a nuclear attack. This was what has now become the internet. Paul Baran wrote a series of papers evaluating the different types of networks and strongly recommending a distributed model that would be capable of having a high percentage of its links removed before starting to collapse. The centralized and decentralized models are clearly too vulnerable for a well placed attack as can be seen in Figure 1.

Figure 1 Ð'- Paul Baran's Networks. Albert-Laszlo Barabasi, Linked; Page 145.

One of the main problems with this distributed model is that to get from certain

nodes to other nodes, a large number of steps is needed. As we are now all too familiar, the Internet, the World Wide Web and numerous others networks evolved into more reliable and better connected networks.

Although a distributed network is more robust than a centralized or decentralized network, a local attack that affects many nodes that are together can still cause the network too fail, such as a snow storm or a contagious disease. Even a very highly connected but ordered network can still fail. An ordered distributed network that is attacked could eventually collapse since certain parts of the network will be isolated from the rest.

No one person or organization was in charge of planning out or overlooking the architecture of the Internet. Yet, it resulted in a beautiful, highly connected, scale free network. It is somewhere between an ordered and random network.

A scale free network is a type of network that has a very uneven distribution of connectivity. It follows a power law distribution, creating a few, but highly connected "super-hubs" that create the small-world phenomenon. The combination of either these highly connected hubs and strategically placed links is what helps to keep the degrees of separation within a large set at a low number as we will later see.

Scale free networks are very easy to navigate, only taking relatively few jumps from a certain node to get to any other node. These type of networks do not necessarily need to be highly connected, but need to have at least a few key connections that can help bridge two worlds together.

The term "scale free network" was first coined by University of Notre Dame physicist, Albert-Laszlo Barabasi. In 1998, Barabasi and his colleagues set out to find the size of the World Wide Web when noticed that the network of the Web does not resemble a random network at all as previously thought and had many unique characteristics that led them to the continued study of scale free networks.

An Ordered Distributed Network:

Number of Links: 60

Largest number of steps to get from one node to another: 10 (from A to M)

Number of Links: 65

Largest number of steps to get from one node to another: 6 (from A to F)

An Ordered Distributed Network under attack.

Number of Links: 40

Largest number of steps to get from one node to another: 7 (from A to F).

Although this network has lost over 37% of its connectivity, it can still operate. It is important to note that group DAB would have been isolated under the regular lattice ordered network. The highest number of steps to get from one node to another node has only increased by one and this only affects very few nodes.

This higher level of connectivity is paramount depending on the importance of the network. Immediately after the attacks on September 11th, since most of the telephone circuits were being used with people trying to call each other to see if their family and friends were safe, many people in New York city resorted to calling relatives and friends in the Mid-West and asking them to call their family and friends in New York city since they would have a better chance in getting in touch with them.

Real world systems usually do not fall under random or regular lattice networks, making these small world networks key in adequately describing systems found throughout the natural and man-made environment.

How are these Scale Free Networks Formed?

Everywhere scientists look, they