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 1
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 2
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 3
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.
Chung, Lu. (2002). Connected components in random graphs with given expected degree sequences. https://doi.org/10.1007/PL00012580 ↩︎
Garlaschelli, Loffredo. (2004). Fitness-Dependent Topological Properties of the World Trade Web. https://doi.org/10.1103/PhysRevLett.93.188701 ↩︎
Caldarelli. (2002). Scale-Free Networks from Varying Vertex Intrinsic Fitness. https://doi.org/10.1103/PhysRevLett.89.258702 ↩︎