Network Models

Chapter overview

Network models are representations of interconnected systems, illustrating relationships, flows, or interactions among entities, often used in operations research and management.

Recording

What are Network models?

  • model: A simplified description, especially a mathematical one, of a system or process, to assist calculations and predictions.
    • “All models are wrong, but some are useful” ~ George E. P. Box
  • Network model: A set of instructions (i.e. a recipe) used to assemble a network.
    • The rules incorporate intuitions, or hypotheses, about how network features emerge.
    • Using the recipe, we can build networks and compare them with real networks, to see if our generative process is valid
    • From this we learn about the mechanisms that give rise to real-world networks.

Recall: Clustering coefficient

  • Clustering coefficient: (node property) ratio between the number of triangles that include the node, and the maximum number of triangles in which the node could participate.

  • Clustering coefficient \(\rightarrow\) measures triangles (friends of a friend)

Where the denominator is given by

Example calculation

NetworkX

https://networkx.org/documentation/stable/reference/algorithms/clustering.html

Example-1: NetworkX calculation

Code
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

G.add_edges_from([(0,3),(0,2),(0,1),(1,2),(1,3),(2,3)])
fig, ax = plt.subplots()
fig.set_size_inches(12, 12)

nx.draw(G,
    with_labels=True,
    # labels=labels,
    node_color='blue',
    width=3,
    node_size=4000,
    font_color='white',
    font_size=18,
    ax=ax
    )
plt.show()
  

print("number of triangles each node is in:",nx.triangles(G))
print("clustering coefficient for each node:",nx.clustering(G))
print("average clustering coefficient of graph:",nx.average_clustering(G))
number of triangles each node is in: {0: 3, 3: 3, 2: 3, 1: 3}
clustering coefficient for each node: {0: 1.0, 3: 1.0, 2: 1.0, 1: 1.0}
average clustering coefficient of graph: 1.0

Example-2: NetworkX calculation

Code
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

G.add_edges_from([(0,3),(0,2),(0,1),(1,2)])
fig, ax = plt.subplots()
fig.set_size_inches(12, 12)

nx.draw(G,
    with_labels=True,
    # labels=labels,
    node_color='blue',
    width=3,
    node_size=4000,
    font_color='white',
    font_size=18,
    ax=ax
    )
plt.show()
  

print("number of triangles each node is in:",nx.triangles(G))
print("clustering coefficient for each node:",nx.clustering(G))
print("average clustering coefficient of graph:",nx.average_clustering(G))
print("(0.33333333+1+1+0)/4.0=",(0.33333333+1+1+0)/ 4.0)
number of triangles each node is in: {0: 1, 3: 0, 2: 1, 1: 1}
clustering coefficient for each node: {0: 0.3333333333333333, 3: 0, 2: 1.0, 1: 1.0}
average clustering coefficient of graph: 0.5833333333333333
(0.33333333+1+1+0)/4.0= 0.5833333325

Additional code

Common real-world properties of networks

  • short paths \(\rightarrow\) it takes a few steps to go from any node to any other node.
  • Many triangles \(\rightarrow\) reflected in high clustering coefficients
  • Heterogeneous, often power law distributions, of node and link attributes (e.g. degree and weight)
  • Sparse \(\rightarrow\) very small average degree compared to the total number of nodes, and very small density.

Where do such properties come from? \(\rightarrow\) network modeling provides some explanatory value

Common network models

  • Consider building a network by adding links between a set of N disconnected nodes.
  • There are many ways to place the links between the nodes.
  • Different network models use different methods
    • Random Networks
    • Small Worlds
    • Configuration Model
    • Preferential Attachment
    • Other Preferential Models

Recall: Scale free (heterogenious) networks

  • A scale-free network is a network whose degree distribution follows a power law, at least asymptotically.
  • That is, the fraction \(P(k)\) of nodes in the network having \(k\) connections to other nodes goes for large values of \(k\) as

\[ P(k) \sim k^{-\gamma} \]

  • where \(\gamma\) is a parameter whose value is typically in the range \(2<\gamma<3\)
  • Degree distribution for a network with 150000 vertices and mean degree \(=6\) created using the Barabási-Albert

Scale free networks: Video

Random network model

Overview

  • Definition: A random network model is a mathematical abstraction used to study complex networks characterized by random connections between nodes.
  • Randomness: Connections between nodes are typically established randomly, following a probability distribution.
  • Properties:
    • Degree Distribution: Often follows a Poisson or Gaussian distribution.
    • Clustering: Typically low compared to real-world networks.
    • Shortest Path Length: Typically shorter due to high connectivity.

Random network “recipe”

  • Two parameter model: The number of nodes \(N\) and a link probability \(p\) (also known as wiring probability).
  • The network can be constructed via the following procedure (formulated by Gilbert):
    1. Select a pair of nodes, say \(i\) and \(j\).
    2. Generate a random number \(r\) between 0 and 1. If \(r<p\), then add a link between \(i\) and \(j\).
    3. Repeat (1) and (2) for all pairs of nodes.
  • A network built in this fashion is called a random or Erdos—Rényi network

Density

  • Recall: Real networks are usually sparse (very small density)
  • Therefore, \(p\) must be close to zero to simulate real networks

Simulation: Vary wiring probability

  • A giant component forms when (k) = 1, that is, when each node has one neighbor on average.
  • Evolution of random networks for growing values of the average degree \(\langle k\rangle\)
    • process of adding links to the system one at a time.
  • The largest connected component (red(), is very small when the average degree is lower than one.
  • Around \(\langle k\rangle=1\) a giant component grows very fast at the expense of the other, smaller components.

Simulation: Vary wiring probability

  • Vary wiring probability: N_nodes=500

NetworkX graph generator

  • NetworkX has functions to generate random graphs according to the Erdés—Rényi and Gilbert models:

G = nx.gnp_random_graph(N,p) # Gilbert random graph in NetworkX

Degree distribution results

  • Recall: The degree-distribution of many real networks is much different from such a bell shaped distributions, due to the presence of hubs (i.e. nodes with much larger degree than the average)

Aside: Recall World flight network

Consider the following example of a real world network

Comparison with real network

  • Probability distribution of degree in a random network.
    1. Erdös-Rényi random graph with \(N=3179, L=18,617\).
    2. Degree distribution for the world flight network: \(N=3179, L=18,617\).
    3. Comparison between the two distributions in (a) and (b) on a double-logarithmic scale.
  • Pro's: Random networks do have short paths,
  • Cons
    • Triangles are rare: average clustering coefficient values can be orders of magnitude smaller than real networks
    • Absence of hubs \(\rightarrow\) non heterogenous degree distribution

Small World Models

Overview

  • In the late 1990s, Duncan J. Watts and Steven H. Strogatz introduced the small- world model, also known as the Watts—Strogatz model.
  • Goal: Create a model with short paths and high clustering coefficient.
  • Definition: A small-world network model is characterized by a combination of high clustering (local inter-connectivity) and short average path lengths between nodes.
  • Key Features:
    • High Clustering: Nodes tend to cluster together, forming tightly knit groups.
    • Short Average Path Lengths: Despite clustering, the average number of steps required to connect any two nodes is relatively small.
    • Randomness and Regularity: Combines elements of regular and random networks.
  • Properties:
    • Clustering Coefficient: High compared to random networks.
    • Average Path Length: Short, comparable to random networks.
    • Small World Phenomenon: Nodes are only a few steps away from each other despite clustering.

Recipe

The algorithm for generating a small-world network is as such:

  1. Begin with a ring of \(N\) nodes
  2. Connect each node to its \(k\) nearest neighbors (or \(k-1\) if \(\mathrm{k}\) is odd).
  3. For each edge \((u, v)\), with probability \(p\), replace edge \((u, v)\) with \((u, w)\) where \(w\) is not a neighbor of \(u\).

The expected number of rewired links is \(p L\), where \(p\) is the rewiring probability and \(L\) is the total number of links in the network. The special case \(p=0\) corresponds to the initial lattice, and the special case \(p=1\) yields a random network.

NetworkX

varying model parameters

If p is chosen to be neither too small nor too large, it is possible to achieve a trade-off, where there are enough shortcuts to make the distances considerably smaller on average, but not so many as to disrupt most of the triangles

  • In this regime, the paths are as short as those in random networks, while the average clustering coefficient decreases only slightly with respect to the initial lattice configuration, so that it can be comparable with that of real social networks.

Configuration Models

Overview

  • Goal: Given some degree distribution, can we construct a network whose nodes have exactly that degree distribution?

Setup

  • Consider an arbitrary degree sequence, with node 1 having degree k1, node 2 degree k2, … etc
  • The first step is to assign to each node a number of stubs corresponding to the degree of the node

Pros and Cons

  • Pros:
    • Can make networks with correct degree distribution
    • Easy to use in NetworkX \(\rightarrow\) G = nx.configuration_model(D) # network with degree sequence D
  • Cons:
    • Lacks explanatory power
    • Requires an a-priori degree sequence
    • The Generated networks aren’t unique (multiple ways to create the same network)
    • Only reproduces correct degree distribution but not necessarily other desired properties

Preferential Attachment Models

Motivation

  • The models explored so far are static (number of nodes was constant)
  • Real networks, instead, are usually dynamic. Nodes and links appear and disappear.
  • The models explored so far cannot explain the existence of hubs.
    • i.e. linking rules are basically egalitarian - the nodes choose their neighbors totally at random.
    • in this case, unlikely for any one node to have an advantage over the other nodes or end up with more neighbors than the rest (unrealistic).

Overview

  • Definition: Preferential Attachment is a network growth model where new nodes preferentially attach to existing nodes with higher degrees.
  • Key Principle: Nodes that already have more connections (higher degree nodes) are more likely to attract new connections.
  • Mathematical Formulation: Probability of a new node connecting to an existing node ( i ) is proportional to the degree ( k_i ) of node ( i ).
  • Resulting Network Properties:
    • Power Law Degree Distribution: Leads to a distribution where a few nodes have many connections (hubs) and many nodes have few connections.
    • Rich-get-Richer Effect: Nodes with higher degrees tend to accumulate more connections over time.
  • Applications: Used to model various real-world networks like social networks, citation networks, and the World Wide Web.
  • Criticism and Enhancements: Criticized for oversimplifying real-world dynamics; enhanced models may incorporate additional factors like node fitness or geographical constraints.

Growth mechanism

  • Preferential attachment: high-degree nodes have a high probability of receiving new links
  • The probability that a new node is attached to an old node is proportional to the degree of the old node.
  • The best-known network growth model incorporating preferential attachment Barabdsi-Albert model (1999) (AKA BA model or preferential attachment model)
  • At each step, a new node is added and connected to some existing nodes.
  • a node with degree 100 is 100 times more likely to receive a new link than a node with degree one.

Algorithm

G=nx.barabasi_albert_graph(N,m) \# BA model network

Example

  • Network generated via a similar growth model, but with random rather than preferential attachment –> no hubs.

Limitations of BA model

  • Dependency on linear preferential attachment,
  • It yields a fixed pattern for the degree distribution: The slope of the preferential attachment curve is the same for any choice of the model parameters.
  • Real degree distributions could decay faster or more slowly.
  • The hubs are the oldest nodes; new nodes cannot overcome them in degree.
  • It does not create many triangles. The average clustering coefficient is much lower than in many real networks.
  • Nodes and links are only added; in real networks they can also be deleted.
  • Since each node is attached to older nodes, the network consists of a single connected component. Many real networks have multiple components.
  • Doesn’t work with singletons, Its degree is zero, so the probability that it will get links is also zero: the node will never have neighbors!

Modification-1: Non-linear attachment

  • BA model uses linear preferential attachment, in that the link probability is strictly proportional to the degree of the target node.
  • This exposes a fundamental fragility of the BA model, as the necessity of strict proportionality between link probability and degree appears unrealistic.
  • probability vary as some power of the degree. (non-linear preferential attachment)

Modification-2: Attractiveness Model

  • A node receives links because of its degree, AND also because it has an intrinsic attractiveness.

  • In the attractiveness model, the link probability is proportional to the sum of degree and a “attractiveness” constant.

  • The attractiveness model is a slightly modified version of the original BA model, in which Eq. (5.9) expressing the probability that an old node \(j\) receives a link from a new node \(i\) is replaced by \[ \Pi(i \leftrightarrow j)=\frac{A+k_j}{\sum_l\left(A+k_l\right)}, \]

  • where \(A\) is the attractiveness parameter and can take any positive value. The case \(A=0\) yields the BA model.

  • For any value of the attractiveness parameter \(\mathrm{A}\), the model builds networks with heavy- tailed degree distributions.

  • The slope of the distribution depends on A.This way, the model is able to match degree distributions of multiple real networks, unlike the BA model.

Modification-3: Fitness Model

  • In BA and attractiveness model the hubs are also the oldest nodes.
  • Not always true (new players come along and shake things up)
  • Fitness model in which each node has its own individual appeal, called fitness.
  • The fitness values are intrinsic features of the nodes; they do not change over time.
  • The link probability is proportional to the product of the degree and the fitness of the target node. The fitness model is similar to the BA model, but each node \(i\) is assigned a fitness value \(\eta_i>0\) generated from some distribution \(\rho(\eta)\). Then at every step, each new link from a new node \(i\) is wired to an old node \(j\) with probability \[ \Pi(i \leftrightarrow j)=\frac{\eta_j k_j}{\sum_l \eta_l k_l} . \]

If all nodes have identical fitness, the model reduces to the BA model, as the constant \(\eta\) is a factor that cancels out between numerator and denominator of Eq. (5.12), returning the standard prescription of preferential attachment.

If the fitness distribution \(\rho(\eta)\) has infinite support (i.e. \(\eta\) can take arbitrarily large values), then there is a winner-takes-all effect with the highest-fitness node being linked to most modes. But if the fitness distribution \(\rho(\eta)\) has finite support (i.e. \(\eta\) has a finite maximum value), then the degree distribution of the model has a heavy tail. An example of this case is the uniform distribution in the unit interval. In Python we can draw fitness values with uniform distribution using the random() function.

Modification-4: Triadic closure

  • Networks built with the BA model have very low clustering coefficients (i.e. they don’t have many triangles), which often isn’t realistic
  • This is because the model has no built in mechanism for triangle generation
  • In the BA model the probability of a node receiving a link is proportional to its degree, regardless of whether the new pair of neighbors have a common edge or not.
  • BA only weights pair-wise connections, three body connections (neighbors of neighbors) are not considered
  • The formation of a triangle via the addition of a link is called triadic closure. This is a very important link-formation mechanism in social networks

Rank model: Overview

  • Preferential attachment implies that the nodes have a perception of how important other nodes are (i.e. new nodes “know” the degree of the target nodes)
  • In realistic settings, it is more common to have a perception of the relative value of things, rather than of their absolute value.
  • I.e. it is easier to rank than to guess the value. For example, you may know someone is older than you without knowing their exact age.

General idea: - rank nodes based some properties, e.g. degree. \(\rightarrow\) Rank vector: \(R=(1,2,3,4)\) - nodes receive new links with probability proportional to some inverse power of their rank with exponential parameter \(\alpha\). \(\mathrm{R}=(1,2,3,4) \rightarrow \mathrm{p} \approx(0.1,0.05,0.033,0.025)\) (if \(\alpha=1)\)

Rank model: Algorithm

  • The rank model can start from any small graph with \(m_0\) nodes. A node property, such as the degree, age, or some measure of fitness is selected to rank the nodes.
  • Each iteration of the algorithm consists of the following steps:
    1. All nodes are ranked based on the property of interest. Nodes are assigned ranks \(R=1,2\), etc. Node \(l\) receives rank \(R_l\).
    2. A new node \(i\) is added to the network, with \(m \leq m_0\) new links attached to it.
    3. Each new link from \(i\) is wired to an old node \(j\) with probability

\[ \Pi(i \leftrightarrow j)=\frac{R_j^{-\alpha}}{\sum_l R_l^{-\alpha}}, \]

  • Where the exponent \(\alpha>0\) is a parameter.

  • Nodes may have to be re-ranked at each iteration if the ranking property depends on the links from new nodes joining the network, as happens for example when nodes are ranked by degree.

  • rank model generates networks with heavy-tailed degree distributions,

  • By tuning the exponent, it is possible to vary the shape of the distribution, and to reproduce the empirical distributions observed in many real-world networks.

Random walk model

The random walk model can start from any small network. Each iteration of the algorithm consists of the following steps:

  1. A new node \(i\) is added to the network, with \(m>1\) new links attached to it.
  2. The first link is wired to an old node \(j\), chosen at random.
  3. Each other link is attached to a randomly selected neighbor of \(j\), with probability \(p\), or to another randomly selected node, with probability \(1-p\).

The parameter \(p\) is the probability of triadic closure, because by setting a link between \(i\) and a neighbor of \(j\), say \(l\), we close the triangle \((i, j, l)\). If \(p=0\), there is no triadic closure and new nodes choose their neighbors entirely at random. When \(p=1\) all links except the first one are wired to neighbors of the initially selected old node, thus closing triangles.

Random walk model: Important features

  • New nodes “explore” the system randomly. They have NO knowledge of the degrees of old nodes (which is more realistic than BA).
  • Nodes are “discovered” with a frequency proportional to their degrees. Therefore, the process of triadic closure implicitly induces preferential attachment.
  • The strict proportionality between link probability and degree, needed to generate broad degree distributions, can be enforced by simple random mechanisms
  • Finally, when \(p\) is large enough that there is a sufficiently high density of triangles, the random walk model produces networks with community structures

Summary

Concluding summary

These summaries capture the essence of each model’s mechanisms and their contributions to understanding network structure and dynamics.

  • Erdős-Rényi Model:
    • All nodes have equal probability of connection.
    • Short paths but lacks triangles and hubs.
  • Small-World Model:
    • Adds random shortcuts to a lattice structure.
    • Maintains high clustering with reduced path lengths.
    • Unable to create hubs effectively.
  • Configuration Model:
    • Generates networks with specified degree sequences.
    • Used as a baseline to study effects beyond degree distribution.
  • Network Growth Models:
    • Nodes and links added over time.
    • Matches real-world network evolution like the Internet.
  • Preferential Attachment:
    • Higher degree nodes attract more connections (hubs).
    • Key mechanism explaining hub emergence.
  • Barabási-Albert Model:
    • Combines growth and preferential attachment.
    • Generates networks with heavy-tailed degree distributions (hubs).
  • Implicit Preferential Attachment:
    • Seen in processes like triadic closure and link selection.
  • Enhancements to Barabási-Albert Model:
    • Introduces attractiveness, fitness, triadic closure, and ranking.
    • Overcomes limitations to better simulate real-world networks.