Transportation Geography and Network Science/Scale-free network

Introduction

The scale-free network has heterogeneity, and the connection status (degrees) between its nodes has severe uneven distribution: a few nodes in the network called Hub points have extremely many connections, and most nodes only have a few connections. A few hub points play a leading role in the operation of scale-free networks. Broadly speaking, the scale-free nature of scale-free networks is an intrinsic property that describes the large uneven distribution of a large number of complex systems as a whole.

It has been shown that applying statistical dynamics to networks is applicable to a broad spectrum of social, biological and technical networks. Unlike many physics fields that concentrate on micro or local interactions, network research utilizes methods that are inherently inductive. Although statistical analysis refuted the claims of the scale-free network and seriously suspected others, many networks have been reported to be scale-free network. To explain power-law degree distribution in real networks, the mechanism of preferential attachment and the growth of network theory has been proposed.

Discovery of the property of scale-free

The World Wide Web is known as the largest humanitarian network. The size of the informatic system is more than a trillion $(10^{7})$, larger than the human brain, $10^{11}$. Because of the diversity of interest in organizations and individuals, it was considered an arbitrary network so that documents could be linked to randomly selected documents. Then, Hawoong Jeong of the University of Notre Dame created one of the Web domains. Unexpectedly, the results were different. In a random network, hubs with highly connected nodes are generally prohibited. However, in the topology of the World Wide Web, some degree nodes and nodes with large links coexist. This led to the discovery of the property of "scale-free".

This sample from the WWW is mapped in Albert's 1999 research. And the distribution of the degree is displayed on the double logarithmic axis (log-log plot), where a power law follows a straight line. The gamma in is 2.1 and 2.45 is the gamma out. Since the gamma-in is lower than gamma out, the gamma-in is straighter than the gamma-out line. As shown in the graphs, in comparison to the expectation of getting a Poisson distribution that characterizes random networks, the networks demonstrate power-law distribution. This can be simplified as the "scale-free network" is the network whose degree of distribution is power-law distribution.

Power law distribution

   $P_{k}$ ~ $k^{-r}$

This is power law distribution equation and the exponent gamma is its degree exponent. K represents the degree of the node; the number of links. P is the probability; fraction.

Mathematical way of defining scale-free property

Mathematically, scale-free network means statiscal moments of degree distribution are not defined(Zhao, Park and Lai, 2004). The property of scale-free can be mathematically defined either with a discrete formalism or continuum formalism.

Discrete formalism

The discrete formalism provides the probability P_k at an exact number of k links as the number of links is always positive and discrete as k = 0, 1, 2, etc. According to the “normalization condition” and “Riemann zeta function”, the equation can be obtained with the following:

$P_{k}=k^{-r}/\zeta (r)$

Continuum Formalism

$P(k)=(r-1)k_{min}^{r-1}k^{r-1}$

In contrast to discrete formalism, the fact that this formalism is continuous means that the degree can have any positive real number within the interval of interest. Probability densities can be taken into account more than the value of the probability itself. P(k) is no longer a probability but a probability per x unit. According to continuum formalism, the probability P(k) can be obtained within some range of values.

Hubs

Hub is the most important difference between a random network and a scale-free network. It represents the distribution of altitude nodes, most of which do not exist in random networks, and naturally exist in scale-free networks. By calculating the maximum degree k_max, it can be seen that how the size of the hub is affected by the network size. It is called "natural cut-off," the expected size of the largest hub in the network.

According to the formula for random networks and scale-free networks, one can recognize how the size of a network affects the size of a hub.

Random network

$K_{max}=K_{min}+lnN/{\lambda }$

$lnN/{\lambda }$ is a "slow function" of system size[1]. And this indicates the degree of nodes will not change noticeably from the minimum number of links.

Scale free network

$K_{max}=K_{min}N^{\dfrac {1}{r-1}}$

As the network size of scale-free networks increases, it can be seen that the degree of nodes will increase significantly. This, again, emphasizes that hubs are prohibited in random networks, but they exist logically in scale-free networks.

The difference between a random and a scale-free network

• Scale-free network is like an air-network. Airports are nodes and the flights are links between them. As nodes have a few hubs with a large number of links, airports in big cities have a large number of flights to other cities, which act as hubs.
• Random network is like a highway. All cities are connected from the highway system and there are no cities have a large number of highways. For instance, when travelling to Melbourne from Sydney by car, the vehicles should drive through many cities while one direct flight can reach the destination by using an aeroplane.
• In random networks, the degree of nodes is comparable as hubs are forbidden. This results in having a bell-shape curve, following the Poisson distribution.

Mechanisms of scale-free architecture

The growth of networks

The number of nodes continuously increase in the real network, in contrast, the number of nodes N is fixed in a random network.

Preferential attachment

In preferential attachment, nodes tend to link to the nodes have many other links and nodes in the scale-free network. In contrast, nodes randomly choose other nodes regardless of the degree of the nodes in a random network.

Preferential Attachment Example

Above the example, in the first figure, each link node has an equal chance of being linked to by another node. However, in the second figure, a node with two links has a 50% chance of being picked, whereas each of other nodes ahs one link, which makes the nodes with one link only have a 25% chance of being picked. Finally, in the last figure, the node with a 50% link is chosen. Hence, the more links that existing node has, the more likely it is to be chosen.

Vulnerability due to interconnectivity

In a scale-free network

The main difference between a random network and a scale-free network is the existence of a hub. A hub in a scale-free network has supposedly unlimited links, and a node is not typical of others. A scale-free network is vulnerable to coordinated attack but is robust to accidental failure.

In a random network

Cascade failures are often caused by interconnectivity. One of the examples was North American blackouts in 2003. For electricity, there is less redundancy than for other networks. Electricity is one of the transportation systems. And because it cannot be stored, it must be used once it has been produced. And, if one node fails, it will affect other nodes due to interconnectivity. This is called "cascading failure." The figure shows 20 hours before and after the North American blackouts in 2003. Because of the interconnectivity between cities, other cities have failed to provide electricity.

Reference

BARABÁSI, A.-L., & PÓSFAI, M. (2016). Network science.

Albert, R., Jeong, H. & Barabási, A. L. The diameter of the World-Wide Web. Nature 401, 130–131 (1999).

Zhao, L., Park, K. and Lai, Y. (2004). Attack vulnerability of scale-free networks due to cascading breakdown. Physical Review E, 70(3).