Hubs, Rich Club, Scale Free Network
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
March 31, 2023
Introduction
Hubs
Short definition: nodes with high degree
What does high mean:
reminder: binomial degree distribution in random network
hubs: far to the right from the expected distribution
far means, for example, at least one standard deviation from the
mean
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 2 / 32
Introduction
Hubs: A ZOO of Complex Networks
1
1
https://noduslabs.com/radar/
types-networks-random-small-world-scale-free/
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 3 / 32
Introduction
Hubs: Motivation
Why do we observe hubs?
network structure is a result of self-organization
real-world systems have limited resources
maintaining links is costly
hubs allow coordination, faster spreading...
hubs are found across multiple scales - fractal (scale-free)
distribution
scale-free distribution is a result of optimization process
in systems with finite resources2
2
Csermely, P. (2006), pp. 20. Weak links.
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 4 / 32
Introduction
Hubs: Motivation
model (network) clusters small diameter hubs
Grid yes no no
Erdös-Rényi (random) no yes no
Watts-Strogatz (small world) yes yes no
Barabási-Albert (scale-free) no yes yes
Many real-world networks contain hubs:
protein-protein interaction, gene expression, metabolic networks
human communication (phone calls, emails...)
human interaction (science / movie cooperation, wealth
distribution...)
www, internet, power grids
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 5 / 32
Introduction
Guimera et al. (2007) doi:10.1038/nphys489
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 6 / 32
Introduction
Hubs in Detail
If the network has a community structure, we can distinguish
between:
global hubs
provincial hubs within modules
connector hubs connecting multiple modules
peripheral hubs
satellite connectors
We quantify this using the so-called participation coefficient.
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 7 / 32
Introduction
Participation Coefficient3
Pi = 1 −
NM
s=1
κis
ki
2
NM is the total number of modules
κis is the number of edges from node i to module s
P ≤ 0.3 provincial hubs
0.3 < P ≤ 0.75 connectors
0.75 < P global hubs
3
Guimera, Amaral (2008). Functional cartography of complex
metabolic networks.
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 8 / 32
Rich-club
Rich-club
(a) (b)
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 9 / 32
Rich-club
Rich-club (k-core)
Rich club is a result of network assortativeness (homophily)
Describes whether
dominant nodes form a tightly interconnected core.
φ(k) =
2E>k
N>k(N>k − 1)
E>k is the number of edges between N>k nodes with degree
greater than k
it represents the fraction of edges between these nodes out of
all possible edges
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 10 / 32
Rich-club
Rich-club: Normalization
Null model:
φun(k) ∼
k2
⟨k⟩N
Normalized RC:
ρunc(k) =
φ(k)
φun(k)
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 11 / 32
Rich-club
Rich-club examples4
4
Colizza et al. (2006) doi:10.1038/nphys209
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 12 / 32
Rich-club
Detour
Project proposals...
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 13 / 32
Power law
Hubs are nodes with a surprisingly high degree. What does the
surprisingly high degree mean?
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 14 / 32
Power law
Hubs and node degree distribution
random network vs. scale-free network
binomial distribution
Gaussian distribution
Poisson distribution
normal distribution
power-law distribution
Pareto distribution
heavy-tailed distribution
fat-tailed distribution
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 15 / 32
Power law
Logarithmic representation of distribution
On a normal histogram, we don’t see much, but a log-log
representation is much more interesting.
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 16 / 32
Power law
Power law distribution5
5
Newman, M. E. (2005) DOI:10.1080/00107510500052444
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 17 / 32
Power law
Power law distribution
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 18 / 32
Power law
Power law distribution
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 19 / 32
Power law
From graph to equation: Power law
log(ak) = k · log(a)
log(ab) = log(a) + log(b)
The relationship can be described
as y = kx + q:
log(P) = log(c) − γ log(D)
After exponentiation :
P = cD−γ
where
P is the probability to meet
a good friend or acquaintance
c is constant
γ is scaling exponent
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 20 / 32
Power law
Power law: variance
The second moment (variance) is generally infinite =⇒ as the
sample (network) size increases, so will the maximum value.
k σ
yeast protein-protein interaction network 2.9 4.88
E. Coli metabolic network 5.58 20.79
WWW network 4.60 30.27
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 21 / 32
Power law
Let’s compute the scaling exponent: Log-log
representation6
Problem:
as the degree increases, fewer samples are available, hence
noise increases.
6
Note: always use logarithm with base 10.
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 22 / 32
Power law
Let’s compute the scaling exponent: Log-log
representation
Solution:
logarithmic bins
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 23 / 32
Power law
Let’s compute the scaling exponent: Log-log
representation
Solution:
complementary cumulative distribution function
P≥(x) = x1−γ
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 24 / 32
Scale-free networks
Scale-free networks
A scale-free network is a network whose degree distribution follows
a power law, at least asymptotically.
Many systems seem to be in the regime of 2 < γ < 3. Is there any
reason for that?
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 25 / 32
Scale-free networks
Example: Scale-free Search Strategy
When social insects seek food, they frequently make
cost-efficient small trips
From time to time, they make longer jumps
Rarely, they make very long journeys
This search strategy is called Lévy flight and follows the
power law P = cL−α, where L is length of a trip
Why it is the best strategy?
It minimizes probability to return to the same site (disadvantage
of random search)
It maximizes chance to end in new location (disadvantage of grid
search)
=⇒ best survival strategy
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 26 / 32
Scale-free networks
Lévy flight
Lévy flight search patterns for 1000 steps. Values for α = 2 proven to
be optimal7.
7
Csermely (2006). Weak links, pp. 29
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 27 / 32
Scale-free networks
Classes of scale-free networks
Anomalous regime γ ≤ 2
the degree of the largest hub grows faster than the size of the
network
such a network is not asymptotically possible without loops
Scale-free regime 2 < γ < 3
the first moment of the distribution (mean) is finite, other
moments diverge (variance, skewness, ...)
specific behavior of dynamic processes (diffusion)
robustness against random failure
vulnerable to targeted attack (unlike a random network)
Random network regime γ > 3
probability of large hubs decreases too fast
hard to distinguish from a random network
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 28 / 32
Scale-free networks
Classes of scale-free networks
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 29 / 32
Scale-free networks
Empirical estimation of exponent
Motivation:
important for null models, e.g. for the study of dynamic
processes
Procedure:
start with log-log transformation, fit a line
use logarithmic intervals or cumulative distribution to remove
noise
apply the method of least squares, maximum likelihood, etc. in
your favorite statistical software
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 30 / 32
Scale-free networks
Example in Excel
...
J. Spurný, E. Výtvarová ·Hubs ·March 31, 2023 31 / 32