📂Graph Theory

Scale-Free Network

Definition ¹

A random network whose degree distribution follows a Pareto distribution is known as a Scale-free Network.

Description

The term Scale-free (SF) network comes from the scale-invariance of the Pareto distribution. Being defined by its degree distribution, it strongly inherits the properties of that distribution. Mathematically, the degree $v \in V(G)$ of nodes in a scale-free network $G$ can be described by some parameter $\gamma > 0$ as follows. $$ P \left( \deg v = k \right) \sim k^{-\gamma} $$ Like the Pareto distribution, SF networks are frequently found across the sciences and are known to be excellent models for describing social and natural phenomena. However, recent papers² have warned against the universal applicability of SF networks, so caution is advised.

One prominent application is mimicking the underlying structure in certain dynamics. Given that it is derived from numerous real data, it is the first to be considered when a mathematically universal structure is needed for human relationships, traffic networks, ecosystems, etc., and is indeed widely used. Methods for artificially generating SF networks include the following models:

• Chung-Lu Fitness Model
• Barabási-Albert Model

The following is a visualization of an SF network generated by the Barabási-Albert model.

In the formula, the histogram of degree distribution should form a straight line when plotted on a log-log scale. In other words, $$ p(x) \sim x^{-\gamma} $$ when logs are taken on both sides of $$ \log p (x) = - \gamma \log x $$ it becomes a straight line with a slope of $- \gamma$. Actually, drawing it shows a clear straight line except for the area where hub nodes occur.