Module 2:

Network Growth Model

By: Udit Gupta

Department of AI&DS
CMR Institute Of Technology
 Properties of Real-World Networks
• Real-world networks, such as social, biological, and technological systems, share common
structural properties:
• Small-world property: In large networks, most nodes are just a few steps apart, meaning
the shortest path between any two nodes is quite small compared to network size. For
example, on Facebook, any user can reach another through a small chain of connections.
• High Clustering: If person A knows persons B and C, then B and C are likely friends as
well. This "tight friend circle" pattern forms triangles in the network. High clustering is a
hallmark of real social groups
• Heavy-Tailed Degree Distribution (Scale-Free): Most nodes have a few connections, but
some nodes (hubs) have a very high number of connections, such as celebrities on Twitter.
• Community Structure: Nodes form groups (modules or communities) where connections
within the group are denser than outside connections. Examples include student groups in
university networks
• Resilience: Networks withstand random node failures but are sensitive to targeted attacks
(e.g., the internet)
 Small-World Network
• In most real-world networks, the average distance (shortest path) between nodes is very small
compared to the network size, meaning even in huge networks, the average distance between
nodes is small.
• Definition: A network where the typical (average) shortest path between nodes grows very
slowly (logarithmically) as the network increases.
o Mathematically expressed as L∼log(N), where Lis average path length and N is number of
nodes.
o This property means that, on average, it takes a small number of hops or steps to get from
one person to another in social networks or from one computer to another in the internet.
o Even in very large networks, any two nodes can be connected through a small number of
steps.
• Examples: The Six Degrees of Separation hypothesis states that anyone on Earth can reach
anyone else through only 6 connections. Similarly, almost any two webpages are separated by
just a few clicks.
• Significance: Small worlds facilitate rapid, reliable communication even in gigantic
networks, making them efficient for spreading information and valuable for robust design.
• Contrast with Random Graphs: Random graphs also often have a short average path
length, but they lack clustering
Applications
• Social networks (Facebook, co-authorship graphs)
• Brain neural networks
• Corporate collaboration structures
 High Clustering Coefficient
Definition: Clustering reflects the prevalence of triangles—highly connected local
neighborhoods. Nodes in real-world networks tend to form triangles (friend-of-a-friend is also a
friend).
The local clustering coefficient 𝐶𝑖 for each node quantifies this:

● where 𝐸𝑖 is the number of links between the neighbors of node 𝑖, and 𝑘𝑖 is how many
neighbors 𝑖 has. The global clustering coefficient is the average 𝐶𝑖 across all nodes. In
social networks, high clustering is observed because friends of a person tend to be friends
with each other
● Global clustering coefficient: It is the average of all local coefficients.
 Random Graphs vs. Real Networks
In a random graph, clustering coefficient is close to the probability 𝑝 of an edge existing
usually very low. Real-world networks exhibit clustering coefficients orders of magnitude
higher.
Examples:
• Social networks: Friends of a person are also friends among themselves.
• Biological networks: Proteins involved in similar functions often interact together.
Significance:
• Encourages community formation.
• Facilitates robustness and redundancy.
Applications
• Community detection algorithms use clustering to infer friendship circles, project teams,
ecological niches, and more
 Heavy-Tailed Degree Distribution
Definition: Heavy-tailed distributions mean a few nodes dominate network connectivity.
Most nodes have a low degree (few links), but a few hub nodes have extraordinarily high
degrees. Mathematically, these systems follow a power law:

𝑃 𝑘 is the probability of a node has degree 𝑘.The formula states that P(k) is proportional to k
raised to the power of negative alpha (the scaling exponent), where α is a constant greater than
1. Range of 𝛾 typically between 2 and 3.
Characteristics:
• Most nodes have few connections.
• A few nodes (hubs) have extremely high degree.
 Mechanism:
• Preferential attachment (the rich get richer): New nodes are more likely to connect to
already well-connected nodes.
Effects:
• Robustness against random failure: removal of most nodes minimally impacts the network.
• Vulnerability: Attacks targeting hubs can severely fragment the network.
• Emergence of super-spreaders: in epidemiology, marketing, and cybersecurity, targeting or
leveraging hubs has oversized effects.
Example:
• Twitter: Most users have few followers; a handful have millions.
• Internet topology: Most servers have few links; critical root servers control thousands.
 Community Structure
● Definition: Nodes are organized into clusters/ communities, where nodes inside a community are
more densely connected than with nodes outside. Networks are modular means nodes cluster into
tightly connected groups with much sparser links between groups.
● Modularity(Q): It is a metric that quantifies the strength of a network's internal community
structure, indicating how well the network is divided into distinct subgroups. A high modularity
score means there are many connections within communities and few connections between them,
suggesting a robust, well-formed community structure.
 Community Structure
o Blue community and Green community are densely connected inside.
o Only two dashed red edges connect the groups (sparse between them).
o This shows high modularity i.e strong internal clusters with weak external links.
• This concept is central to community detection, where researchers use modularity to identify and
understand the hierarchical and organized nature of relationships in online platforms, groups, and
other complex social systems.
• Overlapping Communities: Individuals, publications, proteins, etc., may belong to multiple
communities (e.g. cross-disciplinary researchers).
• Applications
o Disease outbreak analysis (tracking clusters)
o Targeted marketing (identifying interest groups)
o Biochemistry (detecting functional protein complexes).
• Significance:
○ Helps in detecting functional units in networks.
○ Affects information spreading (more likely to stay within communities before
spreading across).

Resilience
Real-world networks survive random failures robustly. Removing a random node usually
leaves the network intact. However, they are fragile if hubs are targeted; eliminating these
key connectors fragments the network, reducing communication and possibly causing
failure in information transfer, robustness, or survivability.
 Assortativity
Definition: Tendency of nodes to connect with other nodes of similar or dissimilar degree.
o Assortative mixing: High-degree nodes connect to high-degree nodes.
o Disassortative mixing: High-degree nodes connect to low-degree nodes.
o Measurement: Pearson correlation coefficient between degrees of connected nodes.
Examples:
o Social networks: Assortative (popular people know other popular people).
o Technological/biological networks: Disassortative (hubs connect to peripheral nodes).

o
 Network Motifs
Definition: Network motifs are small, recurring patterns or subgraphs that appear much more frequently
in real networks than expected by chance. They are like the building blocks of complex networks.
Motifs are like Lego blocks. If you analyze a large network, you’ll find certain patterns appearing again
and again.
Examples:
● Triangles: In social networks, the triad (three people all connected to each other) forms the basis of
close-knit friendship groups. It represents trust and strong clustering.
o Example: In Facebook, if you and your friend both know another person, very likely all three are connected.

● Feed-forward loops: In gene regulatory networks, A regulates B, A and B both regulate C This
allows fine control over gene responses and robust regulation. It adds robustness and delays/filters
noise in gene expression.
o Example: In biology, one gene activates a second gene, and both together control a third gene. This prevents random
fluctuations and ensures stable responses.
 Network Motifs
• Functions & Importance:
o In biology, motifs serve as building blocks for complexity in gene regulation, protein signaling,
and metabolic pathways. Feed-forward loops, for example, can filter out transient noise,
accelerate responses, and ensure stability against fluctuations.
o In social networks, motifs like triangles enable trust and reinforce group cohesion.
 Hierarchical Organization
● Hierarchy involves multiple organizational layers i.e modules within modules.
●Many real-world networks show hierarchical modularity:
○ Small clusters combine to form larger clusters.
○ Hubs often connect different clusters.
● Examples:
○ In Biology: Cells form tissues which group into organs, building from micro to macro
scales.
○ In Technology: Computers → routers → global backbone form layers of the internet,
each responsible for higher-level tasks.
○ Function: Hierarchy enhances scalability, large systems are manageable in layers, and
errors are contained locally. Efficient communication is possible within and across layers
 Dynamic & Temporal Properties

Definition: Real-world networks are not static; they grow, shrink, and change structure over
time.
Mechanisms:
● Growth: New nodes and edges are constantly added (e.g., users joining Facebook).
● Preferential attachment: New nodes prefer to connect to already well-connected nodes
(“rich-get-richer”).
Significance:
● Explains power-law degree distribution.
● Captures real-world phenomena like viral growth, information diffusion.
 Robustness and Fragility

Robustness: Networks are tolerant of random failures (random node removal rarely
disconnects the network).
Fragility: However, targeted attacks on hubs can collapse the network, disconnecting large
sections.

Examples:
• If random routers fail, the Internet still works.
• If major hubs (like Google or root DNS servers) are attacked, the system faces major
disruption.
Comparison of random graph and real-world network

Property Random Graphs Real-World Networks

Average Path Length Short (log N) Short (log N)

Clustering Coefficient Low High

Degree Distribution Poisson Power-law (scale-free)

Community Structure Weak Strong

Assortativity None Present (social: assortative, tech/bio:

disassortative)

Robustness Random failure robust Targeted attack fragile

Motifs Rare Frequent, functional

Evolution Static Dynamic, preferential attachment

Random Network Model (Erdős-Rényi Model)
• Definition and Construction
o The Erdos-Renyi (Erdos and Renyi, 1959) is the first ever proposed algorithm for the
formation of random graphs.
o Model Name: 𝐺 𝑁 𝑝 or Gilbert model
o Process: Given 𝑁 nodes, every possible pair is connected by an edge with independent
probability 𝑝.
𝑁 𝑁−1
o Space: The total number of possible edges is .
2
o Alternative: 𝐺 𝑁 𝑀 model fixes the number 𝑀 of edges distributed randomly among the
node pairs.
• Degree Distribution:
o The degree 𝑘 of a node (number of connections) follows a binomial distribution:

o 𝑃 𝑘 =
𝑁−1
𝑘
𝑝𝑘 ቀ1 − 𝑝)𝑁−1−𝑘 , Poisson for large N
o For large 𝑁 and small 𝑝, the degree distribution is well-approximated by a Poisson law:
𝜆𝑘 −𝜆
𝑃 𝑘 ≈ 𝑒
𝑘!
where 𝜆 = 𝑝 𝑁 − 1 is the expected degree.
• Average Path Length
o For sparse graphs with fixed average degree 𝜆, the average shortest path length 𝐿 scales as:
log 𝑁
𝐿∼
log 𝜆
This means even large networks remain navigable with a small number of steps “small-world
property” (but not high clustering).
The Erdős–Rényi model is the foundation of random graph theory. It shows:
Poisson degree distribution, Low clustering, Short path length, Critical phase transition at
average degree = 1
However, it fails to capture the heterogeneity, clustering, and community structure seen in real-
world networks. This motivated the development of models like the Watts–Strogatz (small-
world) model and the Barabási–Albert (scale-free) model.
 Ring Lattice Model
• Definition: A ring lattice network model (also called a regular ring lattice) is a graph theory
model where nodes are arranged in a circle and each node is connected to its nearest
neighbors on both sides, forming a ring. This structure creates a regular graph where every
node has the same number of connections (degree k). The ring lattice is often used as a
starting point for building more complex networks, such as the Watts-Strogatz small-world
model, by randomly rewiring some edges.
 Ring Lattice Model
So, let us see let us fix the degree as k . So, each node has degree k in this
particular example k equals to 4. So, this is actually a 4 regular ring lattice network
Properties:
• Very regular structure
• High clustering coefficient
• Long average path length
• Example: Sensor networks with fixed nearest-neighbor communication
 Watts-Strogatz Model (Small-world Model)
• Definition: Watts and Strogatz model actually you know combines the idea of regular lattice
and random graph models. It start with ring lattice and rewire each edge with probability

• Benefits:
• Retains high clustering
• Reduces path length drastically
• Example: Neural networks in brain, collaboration networks
 Preferential Attachment Model (Barabási-Albert
Model)
• Definition: Preferential attachment is a network growth rule where new nodes joining the
network are more likely to connect to nodes that are already well connected (i.e., have a
higher degree).
• Mechanism: When a new node joins:
o It looks at all existing nodes and decides where to create links.
o The probability that it will link to a particular node is proportional to that node's degree
(number of existing links):

o Where 𝑘𝑖 is the degree of node 𝑖, and the denominator is the sum of the degrees in the
network.
o Process: Start with a small network. Each new node added connects to 𝑚 existing nodes,
chosen by this probability.
 Preferential Attachment Model (Barabási-Albert
Model)
• Output: Power-law degree distribution (scale-free)
o Resulting structure: After many steps, the network develops a power-law degree distribution:

o This means most nodes have a few links, but a small number of “hubs” have very many links. The
network becomes scale-free.
o Why it happens: Because popular nodes keep getting new links, which increases their chance of
further links even more i.e positive feedback loop (the Matthew Effect).
• Example: The World Wide Web
o Popular websites: When building a new web page, the owner tends to link their page to well-
known ones (Google, Wikipedia, major news sites) because those are easy to find, trusted,
and visible.
o Snowballing effect: These popular sites grow their incoming links rapidly, while most sites
attract only a few. The web’s link structure ends up dominated by a few hubs.
 Preferential Attachment Model (Barabási-Albert
Model)
• Drawback: Low clustering
o Clustering: Real social networks feature many triangles (friend-of-a-friend connections), i.e.,
high clustering.
o Problem: The basic preferential attachment rule leads to networks where most connections go
directly to hubs, resulting in fewer triangles (low clustering coefficient than real-world
friendship or collaboration networks).
o Solution: More realistic networks may require additional mechanisms (e.g., local attachment,
triadic closure, fitness, aging).
 Price's Model (Generalization of Preferential
Attachment)
• Definition: Price’s Model is an early, foundational model for growing networks especially
citation networks , developed by Derek J. de Solla Price in the 1970s.
• Generalization: Unlike basic preferential attachment (where a node's chance of gaining a
new link is strictly proportional to its current degree), Price's Model adds a constant offset to
this probability, introducing the concept of initial attractiveness.
• Why? In real networks (especially citations), even a brand new node/paper, with zero
links/citations, may attract a connection (maybe by being cited because it’s highly relevant,
recent, or by accident). If probability is purely proportional to degree, nodes with zero links
will never get cited, which isn’t realistic.
• Price’s Model refines preferential attachment by allowing new nodes ,even with zero links to
be chosen, mimicking real-life “breakouts” in citation networks and more. The constant
provides a realistic pathway for newcomers, making the model ideal for describing citation
growth, web evolution, and more
Price's Model (Generalization of Preferential
Attachment)
• Mathematical Mechanism: The probability that a new node connects to an existing node
with in-degree k is:
Where:
o k = existing number of links/citations(degree)
o a = non-negative constant(initial attractiveness) which is often set to 1 in Price’s original
papers
• Why Add a Constant “a”?
o In basic preferential attachment (Barabási–Albert), a new node connects to an existing node
with probability proportional only to its degree 𝑘:
o
Problem: If 𝑘 = 0 (the node has no links yet), it never gets chosen. But in real-life
especially citation or web networks, even new/unpopular nodes sometimes get cited or
linked by chance. This means all nodes ,even those with k=0, have some chances of being
selected
 Price's Model (Generalization of Preferential
Attachment)
• Example: Citation networks
o Application: When a scientist writes a paper, they cite other papers. Price’s model predicts:
o Well-cited papers are more likely to receive new citations (the rich-get-richer effect)
o But even uncited papers stand a chance because of initial attractiveness.
o Real-world effect: The model correctly describes why even obscure(unknown)papers can,
by chance or by later discovery, gather citations over time.
• Effect :
o The degree (in-citation) distribution still follows a power law (scale-free), but the added
constant modifies the slope (the exponent γ)
o The formula for the degree distribution in Price’s model is:

o As a result, the network is still dominated by a few hubs but more nodes have low degree,
reflecting reality better than basic preferential attachment.
 Local-world Network Growth Model
• Definition:
o It is a refinement of network growth mechanisms. Unlike global models (like Barabási–Albert
preferential attachment, where each new node "sees" the whole network), in the local-world
model, every new node connects only to a subset of existing nodes i.e its "local world".
o Within this subset, connections are made using a preferential attachment rule (favoring nodes
with higher degree even in the local world, not the whole network).
• Example: When a user joins LinkedIn as a new employee at a company or new student at a
university:
• They are first presented with people in their institution or group (the local world).
• They connect preferentially to users who already have more connections within that group
(popular students or active employees).
• Only later, or through network evolution, their connections extend to users outside this subset.
 Local-world Network Growth Model
• Advantages:
o Realism: In very large or distributed systems, nodes rarely possess global knowledge of
the network. Instead, individuals, websites, or documents tend to form links based on
local information—connecting initially within a nearby or familiar 'local world' and
expanding connections outward. This reflects actual behaviors in social networks, web
growth, and citation networks.

o Heterogeneity: Different nodes can belong to or interact with different local worlds,
resulting in a mixture of growth patterns throughout the full network. This is key to
representing how diverse communities, interest groups, or functional clusters emerge
naturally, as not all nodes develop connections uniformly.

o Control over Structure: By adjusting the size or nature of the local world, networks can
transition between exponential (small local world) and scale-free (large local world)
degree distributions.
 Local-world Network Growth Model
o Efficient Computation: When forming links, nodes only need to consider a small subset
of the network at a time i.e those within their local world , making the model
computationally efficient. This is particularly important for simulating or analyzing very
large networks, where global calculations can be intractable.
These advantages make the local world network growth model an essential tool for studying
complex networks that reflect both realistic behavior and computational feasibility
 Network Model with Accelerating Growth
• Definition: In a Network Model with Accelerating Growth, as the network gets larger (more
nodes added), each new node forms more connections than previous new nodes. This means
that the network doesn't just grow in size, it becomes denser at an increasing rate. The average
number of connections (edges) per node increases over time, causing the network to densify
faster than linearly(if each node just kept making the same number of connections as before.)
• Real-World Analogy: Consider Instagram or similar social media platforms:
o Early users had fewer connections because the platform was small and less popular.
o Newer influencers or users join when the platform is large and have the opportunity to
connect with many more users immediately.
o Influencers joining later can quickly reach huge audiences compared to pioneers, just
because the network is much denser and more interconnected.
This increased exposure means that the rate of connection-making speeds up as the network
grows.
 Network Model with Accelerating Growth
• Effect:
o The network becomes denser more quickly means the total number of edges increases
much faster than the number of nodes.
o However, even as the network gets dense, the degree distribution (a measure of how
many connections each node has) remains heavy-tailed. This means a few nodes still end
up with a very large number of connections, while most have far fewer , similar to typical
social, information, or citation networks.
So , this model explains why so many real-world networks become richly connected very
quickly once they reach a certain scale, and is essential in understanding and predicting the
evolution of large online and social graphs.
 Aging in Preferential Attachment
• Definition:
• In the aging extension of the preferential attachment model, each node’s attractiveness to
new links decreases as it gets older. Unlike the classic preferential attachment model
where nodes with high degree continuously attract more links regardless of age, aging
introduces a decay factor, causing older nodes to attract fewer links over time.
• Mechanism:
o The probability that a new node connects to an existing node is proportional to the
product of the existing node's degree and a decreasing function of the node's age.
o The probability Π𝑖 that a new node connects to an existing node 𝑖 is given by:

𝜫𝒊 is the probability that a new node will connect to an existing node i.

ki is the current degree of node 𝑖, meaning the number of links node 𝑖 already has.
Higher 𝑘𝑖 means node 𝑖 is more connected.
 Aging in Preferential Attachment
f(τi) is a function of the age 𝜏𝑖 of node 𝑖. This function decreases as the node gets older,
modeling the idea that older nodes become less attractive for new connections.
Thus, the probability of attaching to node i depends both on:
o Its popularity or importance (degree 𝑘𝑖 — (nodes with more connections attract more
new links (preferential attachment).
o Its age, modifying that attractiveness to decline for older nodes, reflecting diminishing
relevance or visibility over time.
This models realistic scenarios where older nodes lose relevance or visibility, making them
less likely to receive new connections despite earlier popularity.

Example:
o In citation networks, older research papers tend to receive fewer citations as time
passes, even if they were highly cited initially.
o Social networks or online platforms similarly show that users’ influence or activity
declines over time, reducing their rate of new connections.
 Aging in Preferential Attachment
• Outcome:
o Aging in preferential attachment captures temporal decay in node attractiveness, aligning
network growth models closer to real-world observations across citation, social, and
information networks. It balances continuous preferential attachment with natural fading
influence due to aging.
o In essence, this balance creates a more accurate and dynamic network growth model