Models for Scale Free Networks

Barabasi-Albert Model §

• The Barabasi-Albert Model is a minimal model that can generate a scale-free network. It consists of two aspects

  • Growth - At each time step, add a new node to the network with links that connect the new node to nodes already in the network.
  • Preferential Attachment

• Assume:

  • The probability to connect to a node depends on that node depends on that node’s degree.
  • is linear in .

Properties §

• The degree distribution is given as

  • For large , the above reduces to in line with that shown in scale-free networks
  • The power law that emerges is independent of the choice of
  • The power law distribution is scale and time invariant, which can also be observed in the above distribution of the Barabasi-Albert model
  • The coefficient of the power-law distribution is proportional to , which is supported by numerical simulations.
  • Derivation is given in Barabasi Box 5.3

• The Barabasi-Albert model tends to be more clustered than a random network The average clustering is obtained as

Evaluation §

• The degree distribution of the Barabasi-Albert Model implies the following about the structure of the model

  • A power law emerges of independent of the links per node in the growth
  • The power law that emerges provides supporting evidence that the Barabasi-Albert model gives a scale-free network.

• Growth and Preferential attachment are necessary to model most real networks, so indeed, the model captures this aspect of real networks.

  • Without growth, the network will eventually become a complete graph with a non-power law degree distribution
  • Without preferential attachment, the degree distribution shows exponential decay, which means that the network lacks hubs .

• Because of growth and preferential attachment, hubs are large and get larger as the number of nodes increases.

• In a Barabasi-Albert model, older nodes in the network are more likely to grow than newer networks. This explains where our hubs come from.

  • In the model, an existing node can increase its degree when a new node enters the network. This node will link to of the nodes in the network. The link probability is given as .

  • If we approximate the degree as a real variable, representing the expected value over the growth process, the rate at which an existing node acquires links is

  • Because the denominator goes over all nodes except the newly added one, the sum is equal to and so

  • Using the fact that (i.e., node joins the network at with links), we obtain

  • Where is referred to as the dynamical exponent. Here it has value . This implies that the degree exponent is .

  • The degree of each node increases following the power law. Older nodes eventually become hubs.

• The Barabasi-Albert network features shorter distances between nodes.

  The diameter when and large is given by

• The Molloy-Reed Criterion on a scale-free network to get a breakdown threshold , we arrive at

Extensions §

Linearized Chord Diagram §

• Aims to make the Barabasi-Albert model more rigorous by modifying the generation algorithm.

  • Start with which is a graph with no nodes.

  • Given , generate by adding node and a single link between and with link probability

    This allows for loops and multi-edges however, this number becomes negligible at the limit

  • For , build by adding links from the new node one by one. In each step, we allow the outward half of the newly added link to contribute to the degrees.

    That is, when a new node attaches to an existing node, increment the existing node’s degree by one.

Bianconi-Barabasi §

• The Bianconi-Barabasi Model adds a criterion of fitness to each node

  • The growth of a network follows by adding a new node with links and fitness .

  • The fitness pertains to an intrinsic property of nodes that propels them ahead of other nodes when the network grows

  • The fitness is chosen from a fitness distribution , and this fitness does not change.

  • Preferential attachment is obtained by having the link probability be determined by both the fitness and the degree of the node as shown

• There is, in fact, a dependence between the degree distribution and the fitness distribution of each node in the Bianconi-Barabasi model. More specifically we have that ¹

• In a fitness-model, nodes with higher fitness will increase in degree faster. Thus, it is not enough to be the “oldest” node in the network. Newer nodes which are very fit can easily grow quicker given enough time.

  • In particular, the degree exponent of the Bianconi-Barabasi model satisfies ¹

Accelerated Growth §

• The Accelerated Growth Model extends the assumption that the number of links increases linearly with the number of nodes.
• In real networks, accelerated growth is observed where the number of nodes grows faster than linearly.
• Accelerated growth makes the network more homogeneous. It may lead to hyper-accelerating growth where the average degree grows linearly with time and the network no longer becomes scale-free
• Assume that in a growing network, the number of new links arriving with each new node is
  The degree exponent now changes to
  If , then the average degree diverges.

Aging §

• The Aging Model accounts for the fact that some nodes in the system might only persist for a limited time.

• In practice, aging is due to the finite amount for resources that nodes may consume.

• The preferential attachment is given as

  Where affects the dependence of the incoming node on the age of existing nodes.

  • If , new nodes will link to older nodes. Hence, aging will actually enforce the scale-free property.
  • If new nodes will link to younger nodes. This will homogenize the network.
  • If the aging effect will overcome the preferential attachment, leading to the loss of the scale-free property

Initial Attractiveness §

• The initial attractiveness model addresses a limitation of the Barabasi-Albert model wherein isolated nodes cannot acquire links

• The Preferential Attachment is modified to be of the form

• denotes the initial attractiveness which indicates the probability that it acquires its *first link in the next time step. *

Internal Links §

• The internal links model adds the phenomenon of double preferential attachment that can affect the homogeneity of the degrees in the network.

• We make use of double preferential attachment, where for internal nodes we have that

• Double preferential attachment has the following effects:

  • If , then the degree exponent lowers which makes the network more heterogeneous by connecting hubs together and making them larger. Here the degree exponent becomes

  • If we have the case of random attachment which increases the degree exponent and makes the network more like a random network

Node Deletion §

• The Node Deletion accounts for the fact that some nodes can be deleted or removed while others may be virtually impossible to remove.

• The scale-free property of networks can persist even with node deletion as long as the rate of adding new nodes is greater than the rate of removing them.

• Node deletion causes the growth in three phases

  • In the Scale-Free Phase the number of nodes removed is smaller than the number of new nodes. Thus, the network continues to grow with the degree exponent.

  • In the Exponential Phase, the rate of node removal is the same as the rate of node arrival. Thus, the network has a fixed size, and will lose its scale free nature.

  • In the Declining Phase, the rate of node removal exceeds the number of new nodes.

Hierarchical Network Model §

• The Hierarchical Network Model is a model for networks that aims to capture hierarchies in real networks

• It is generated as follows

  • Start from a fully connected module of five nodes
  • Create four identical replicas of the starting module and connect the peripheral nodes of each module to the central node of the original module.
  • Do the same as (2) indefinitely but now for each of the replicas.

• It generates a scale-free network with degree exponent

• In this network, the clustering size is independent of the size of the network. It is, instead, dependent on the degree of the node

• In this network, we observe the following as a consequence of clustering size being dependent on degree

  • Small degree nodes have high clustering since they reside in dense communities
  • High degree nodes have low clustering since they connect communities.

Links §

• Barabasi
• Random Network
• Fundamental Constructs of Network Science
• Scale Free Network

Footnotes §

1. See Barabasi Ch. 6.1 ↩ ↩²