Networks

In class we discussed the small-world phenomenon, also known as the “six degrees of separation,” which is the fact that groups in a social network can be connected by very short paths. In particular, Chapter 20 of the book describes a model that supports the small-world phenomenon. This model, known as the Watts-Strogatz model, proposes a hybrid structure of nodes consisting of a small amount of randomness sprinkled onto an underlying structured pattern. The structured patterns results from homophilous links between the nodes (which arise when one connects to others that are like oneself). The “randomness” emerges from weak ties between the nodes. These weak ties play a large role in the small-world phenomenon, and the Watts-Strogatz model shows that introducing merely a small amount of randomness is sufficient to make a “small” network in which there are short paths between every pair of nodes.

A key component to the Watts-Strogatz model is the concept of range, applied to the links between nodes. The range of a particular link connecting two nodes is the length of the shortest path between these nodes if the link is absent. A central component to this model is the idea that the shortest paths between nodes are attributed to long-range links (i.e. links between two nodes that would have a long shortest-path if the link is not there).

However, in the article “Range-based attack on links in scale-free networks,” Motter, Nishikawa, and Lai question if long-range links are also responsible for the small-world phenomenon in scale-free networks. These are networks with the property that the number of links k originating from a given node exhibits a power law distribution . The probability of linking to a node in a scale-free network is proportional to the number of existing links that node has. There are many examples of scale-free networks in science and engineering, such as the network of web pages or the U.S. power grid. Example diagrams of random versus scale-free networks are shown below:

Based off of the Watts-Strogatz model and theories around small networks and long-range weak ties, the authors hypothesized that the short connectivity of scale-free networks would also result from long-range weak ties. To examine this, the authors studied range-based attacks on links in generated scale-free networks. They found that unlike random networks, scale-free networks are more sensitive to attacks on short-range than on long-range links. The implication of this finding is that short-range links are the crucial component of communication between nodes in scale-free networks, rather than long-range ones. The authors explain this finding by addressing the notion of load. In particular, the load of a link is the the number of shortest paths passing through the link. The study found that short-range links usually have the highest load. So, for scale-free networks, the load and range of a link are important factors to consider when addressing the small-scale phenomenon of the network.