📂Graph Theory

Blue-Loo Fitness Model

Definition

A Fitness Model refers to a random network where weights are assigned to each node, and the probability of links being formed is varied according to these weights.

Algorithm

Input

A null graph with $n \in \mathbb{N}$ nodes, denoted as $G$, is given.

Chung-Lu model ¹

Step 1.

A degree sequence $\displaystyle \mathbf{w} := \left( w_{1} , \cdots , w_{n} \right)$, which satisfies $\displaystyle \max w_{k}^{2} < \sum_{k=1}^{n} w_{k}$, is generated. Here, each node $k \in V(G)$ is assigned a weight $w_{k}$.

---

Step 2. Bernoulli Trials

for $i,j \in \left\{ 1, \cdots , n \right\}$
　　if $i \ne j$ then
　　　　With probability $$p_{ij} = {{ w_{i} w_{j} } \over { \sum_{k=1}^{n} w_{k} }}$$, link $ij$ is added to the network $G$ as follows: $$G \gets G + ij$$

---

Output

A random network $G$ with an expected degree $\mathbf{w}$ of nodes is obtained.

Galloskelli-Lofredo model ²

Step 1.

Given a parameter $\delta > 0$ and considering the GDP $w_{k}$ for each country $k \in V(G)$, the normalized relative GDPs $x_{k}$ are defined as the fitness. $$x_{k} := {{ w_{k} } \over { \sum_{k=1}^{n} w_{k} }}$$

---

Step 2. Bernoulli Trials

for $i,j \in \left\{ 1, \cdots , n \right\}$
　　if $i \ne j$ then
　　　　With probability $$p_{ij} = {{ \delta x_{i} x_{j} } \over { 1 + \delta x_{i} x_{j} }}$$, link $ij$ is added to the network $G$ as follows: $$G \gets G + ij$$

---

Output

A scale-free network $G$ is obtained.

Caldarelli model ³

Step 1.

Given a threshold function $z(n)$ dependent on $n$, sample $x_{1} , \cdots , x_{n}$ from an exponential distribution $\exp(1)$. A weight $x_{k}$ is then assigned to each node $k \in V (G)$.

---

Step 2.

A matrix $A$ is generated as follows for the Heaviside step function $\theta$: $$\left( A \right)_{ij} := \theta \left( x_{i} + x_{j} - z(n) \right)$$ This matrix $A$ becomes one where if the sum of fitnesses of two nodes $i,j$ exceeds the threshold $z(n)$, it is $1$; otherwise, it is $0$.

---

Step 3.

A graph $G$ with adjacency matrix $A$ is generated.

---

Output

A scale-free network $G$ with a degree distribution following Pareto distribution $\text{Pareto} \left( 2 \right)$ is obtained.

Description

The fitness model has been developed primarily to generate scale-free networks, as introduced, by leveraging the fact that nodes with higher weights (influence) are more likely to be connected to many links, thereby inducing a Heavy Tail of Pareto distribution. Hence, there’s no need to be overly fixated on terms like weight or fitness.

The Gilbert model, which gives a constant probability of $p$ for links between every pair of nodes, can be seen as a generalization of the Chung-Lu and Galloskelli-Lofredo models.