Preferential Attachment
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
March 31, 2023
Models and Networks
Models and Networks
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á ·Preferential attachment ·March 31, 2023 2 / 30
Models and Networks
Generating Random Networks with Given pk
General approach:
Generate a random network based on a given degree
distribution pk.
Allows for the creation of surrogate data for a real network.
Does not reveal anything about the origin of the network’s
structure itself.
Three main variants:
Degree-preserving randomization
Generative models
Configuration model
Hidden variable model
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 3 / 30
Models and Networks
Degree-Preserving Randomization
Procedure:
Input an existing network
Randomly select a pair of edges and swap them
Multilinks are forbidden
Repeat until all links are swapped at least once
(i, j), (k, l) → (i, l), (k, j)
Properties:
Preserves the size, density, and pk of the network.
Other parameter-dependent properties are lost.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 4 / 30
Models and Networks
Degree-Preserving randomization
1
1
Barabási: Network Science Book
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 5 / 30
Models and Networks
Configuration Model
Procedure:
Input a set of nodes with given degrees (obtained from
adjacency matrix)
Links are cut in a half such that they remain stubs
Randomly connect pairs of stubs to get links
Properties:
Probability of an edge between nodes i and j:
kikj
2|E|−1 =⇒ prefers
connecting high-degree nodes
Leads to the creation of loops and multiple edges
Degree of nodes is preserved, network is random
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 6 / 30
Models and Networks
Hidden variable model
Procedure:
start with isolated nodes
assign each node a parameter value ηi from the distribution ρ(η)
add edge (i, j) with probability
ηiηj
⟨η⟩N
e.g., for scale-free networks: ηi = c/iα, i = 1, . . . , N
results in a network with pk ≈ k−(1+ 1
α )
Properties:
does not create multi-edges and loops
flexible regarding the desired pk
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 7 / 30
Models and Networks
Hidden variable model
2
2
Barabási: Network Science Book
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 8 / 30
Models and Networks
Which model to choose?
3
3
Barabási: Network Science Book
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 9 / 30
Models and Networks
Growth models
Motivation:
we are interested in the principles behind the scale-free nature
of networks shared across vastly different systems
Observation:
real networks often form through gradual evolution (adding
nodes)
citation network, WWW, ...
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 10 / 30
Models and Networks
Preferential attachment
Intuition:
newly arriving nodes are more likely to be connected to popular
nodes with high ki
rich get richer effect
General procedure:
iteratively add a node with a given number of edges
the probability of connecting to an existing node j depends on kj
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 11 / 30
Models and Networks
Barabási-Albert Model
Procedure
each new node arrives with m edges
the probability of attaching to node i is given by:
Π(ki) =
ki
j kj
Resulting degree distribution:
p(k) ≈ 2m2
k−3
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 12 / 30
Models and Networks
Netlogo demo
...
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 13 / 30
Models and Networks
Nonlinear preferential attachment
In general, Π(k) ∼ kα
Sublinear (α < 1)
Not enough to create hubs: random network
Linear (α ≈ 1)
Scale-free network
Superlinear (α > 1)
The tendency of rich-get-richer dominates
Winner-takes-all: star topology
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 14 / 30
Models and Networks
4
4
Barabási: Network Science Book
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 15 / 30
Models and Networks
Bianconi-Barabási Model
Motivation:
BA model favors older nodes (rich-get-richer)
However, in real-world, older nodes are not necessary the
richest: Myspace vs. Facebook; Yahoo vs. Google...
capable nodes can surpass existing dominant hubs – add the
fitness parameter to the model
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 16 / 30
Models and Networks
Bianconi-Barabási Model
Procedure
in each step, add a node with m edges and fitness η from a given
distribution ρ(η)
the probability of connecting the new incoming node to node i is
given by:
Πi =
ηiki
j ηjkj
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 17 / 30
Models and Networks
Bianconi-Barabási Model
Properties:
Even a small difference in node fitness leads to large differences
in degree
If node fitness η is identical for all nodes, the model reduces to
BA
= For a uniform distribution of ρ(η), we get a scale-free network
Node "age" is not the main determining factor for the resulting
degree
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 18 / 30
Models and Networks
Netlogo demo
...
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 19 / 30
Models and Networks
Bose-Einstein Condensation
5
5
Barabási: Network Science Book
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 20 / 30
Models and Networks
Topological Phase Transition
6
6
Csermely (2006). Weak links, pp 75.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 21 / 30
Midterm Summary
What Do We Know So Far?
Summary + Going Above and Beyond
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 22 / 30
Midterm Summary
Node Centralities
Degree
Number of links connected to the node. In directed network, we
distinguish in-degree and out-degree.
Eigenvector centrality
Self-referential measure of centrality – node has high eigenvector
centrality if it connects to other nodes that have high eigenvector
centrality.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 23 / 30
Midterm Summary
Homophily
Assortativity
A positive assortativity coefficient indicates that nodes tend to link to
other nodes with the same or similar degree.
Disassortativity
A negative assortativity coefficient indicates that nodes tend to link
to other nodes with different degree.
Rich Club Coefficient
Measures the extent to which well-connected nodes also connect to
each other.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 24 / 30
Midterm Summary
Communities
Local Clustering
How close are nodes’ neighbours to be a complete graph (clique).
Community structure
A subset of network that maximizes within-group links a minimizes
between-group links.
Modularity
A statistic which denotes to what extent the network may be divided
into groups.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 25 / 30
Midterm Summary
Paths
Path
A sequence of linked nodes that never visits a single node more than
once (as opposed to walks which allow this).
Betweenness centrality
Fraction of all shortest paths in the network that contain a given
node. High BC = many shortest paths through the node. Similarly,
edge betweenness centrality may be calculated.
Closeness centrality
Measures how short the shortest paths are from selected node to all
other nodes.
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 26 / 30
Midterm Summary
Basic network characteristics
Avg./min./max. degree & degree distribution
Avg. path length & BC or Closeness centrality distribution
Connectedness – number of components & size of giant
component
Modularity & modularity classes (communities)
Comparison to known network models
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 27 / 30
Midterm Summary
Models and Networks
model class model observation
static Erdös-Rényi giant component
Watts-Strogatz small worlds
generative configuration model loops and multilinks
hidden parameter model adjustable pk
growing Barabási-Albert rich-get-richer; scale-free
Bianconi-Barabási winner-takes-all
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 28 / 30
Midterm Summary
A ZOO of Complex Networks
7
7
Types of Networks
J. Spurný, E. Výtvarová ·Preferential attachment ·March 31, 2023 29 / 30