Social Media

Analytics
Module 2
Network Measures
Overview - Network Measures
 Properties of Real-World Networks –
High Average Local Clustering
Coefficient, Small-world Property,
Scale-free Property.
 Random Network Model- Degree
Distribution of Random Network,
Evolution of a Random Network,
Average Path Length, Clustering
Coefficient, Random Network vs.
Real-world Network
Network Models
• Social network models are theoretical frameworks that
represent and analyze the patterns of relationships and
interactions among entities
• Can we characterize, model, and reason about the structure of
social networks?
• Utilizing network models in platforms like Facebook, Instagram,
etc. is essential for comprehending and optimizing the intricate
web of user interactions and relationships.
• These models serve as foundational tools for analyzing the
structure and dynamics of social networks
Challenges
• Utilizing network models instead of analyzing the complete real-world social networks
directly offers several advantages, particularly in the context of platforms like Facebook
and Instagram
• Scalability and Complexity Management:
– Real-world social networks are vast and intricate, comprising billions of users and
connections.
– Direct analysis of such massive networks is computationally intensive and often
impractical.
– Network models abstract essential features, enabling researchers to study the
network's properties without the need to process the entire dataset.
• Privacy and Ethical Considerations:
– Analyzing real user data raises significant privacy concerns.
– Network models allow for the study of social dynamics without exposing personal
information, as they can generate synthetic data that mirrors the statistical properties of
real networks.
– This approach facilitates research while safeguarding user privacy.
Challenges
• Hypothesis Testing and Simulation:
–Researchers can manipulate model parameters to observe potential
outcomes, such as the spread of information or the impact of removing
certain nodes, which would be challenging to perform on the actual network.
• Generalization and Theory Development:
–By focusing on models, researchers can identify underlying principles and
patterns that apply across different networks.
• Data Availability and Accessibility:
–Access to complete real-world network data is often restricted due to
proprietary or privacy reasons.
–Network models, however, can be constructed using available data samples or
inferred characteristics, making it feasible to conduct meaningful analyses
without requiring full access to the original network.
 So, what do we do?
Design models that generate graphs
– The generated graphs should be similar to
real-world networks.
• If we can guarantee that generated graphs
are similar to real-world networks:
1. We can analyze simulated graphs instead of
real-networks (cost-efficient)
2. We can better understand real-world
networks by providing concrete
mathematical explanations; and
3. We can perform controlled experiments on
synthetic networks when real-world Basic Intuition:
Hopefully! Our complex output [social network] is
networks are unavailable. generated by a simple process
Synthetic Networks (Models)

• Generated using theoretical network models

• Often possesses strong underlying mathematical foundation
• Often can simulate important real-world network characterics
• Help getting insights of sticsthe real-life networks
• Allow experimentation through simulation when real networks
are unavailable
• Can establish network insights on concrete theoretical
foundations
Properties of Real-world Networks

•Small-world property
•High average local clustering
coefficient
•Scale-free property
Properties of Real-world Networks
• Small-World Phenomenon:
– Most individuals are connected by short chains of acquaintances, leading to the
"six degrees of separation" concept.
– This property facilitates rapid information dissemination across the network.
• Scale-Free Distribution:
– These networks often have a few highly connected nodes (hubs) and many nodes
with fewer connections, following a power-law distribution.
– This structure makes the network robust against random failures but vulnerable to
targeted attacks on hubs.
• High Clustering Coefficient:
– Individuals tend to form tightly knit groups where members are more
interconnected, resulting in a higher probability that two friends of a person are
also friends with each other.
Properties of Real-world Networks

• Community Structure:
– Social networks naturally divide into communities or clusters with dense internal
connections and sparser links between groups. This modularity reflects shared
interests or affiliations among members.
• Assortative Mixing:
– Nodes with similar attributes, such as age, profession, or socioeconomic status, are
more likely to connect with each other, leading to homophily within the network.
• Dynamic Evolution:
– Social networks are not static; they evolve over time as individuals form new
connections or sever existing ones, influenced by factors like changing interests,
life events, or technological advancements.
Small-world Property
An outcome of Stanley Milgram’s small-world
experiment (1967) to measure the probability
of two random persons being known to each
other
Can also be viewed in light of the average
path length between two randomly chosen
nodes in a network
A network 𝐺 is said to follow the small-world
property if the average path length of the The "six degrees of
network is logarithmically proportional to the separation" model
https://en.wikipedia.org/wiki/Small-
network size. world_experiment
𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝑷𝒂𝒕𝒉 𝑳𝒆𝒏𝒈𝒕𝒉 ∝ 𝐥𝐨𝐠(𝑵𝒆𝒕𝒘𝒐𝒓𝒌 𝑺𝒊𝒛𝒆)
How Small is the World?
• A rumor is spreading over a social
network.
–Assume all users pass it immediately to Rumor Spreading on Facebook
all of their friends

1. How long does it take to reach

almost all of the nodes in the
network?
2. What is the maximum time?
3. What is the average time?
 Milgram’s Experiment
• 296 random people from Nebraska (196
people) and Boston (100 people) were
asked to send a letter (via intermediaries)
to a stock broker in Boston
• S/he could only send to people they
personally knew, i.e., were on a first-name
Stanley Milgram (1933-1984)
basis

At the end Milgram’s results determined that the chain varied

between two hops to ten hops, with an average path length of five
and a half or six.
 Small-world of Social Media!!!
• The concept of "six degrees of separation" suggests that any two individuals are, on
average, separated by six or fewer social connections. This idea has been explored
extensively within real-life social networks, particularly on platforms like Facebook.
• Average distance between two random Facebook users in 2011 was 4.74 with 3.74
intermediaries [Four Degree of Separation by Backstrom et al. (2012)]
• This study encompassed approximately 721 million active users and 69 billion friendship
links, making it one of the most extensive analyses of its kind.
• Building upon this, in 2016, Facebook updated its analysis and reported that the average
degrees of separation had further decreased to 3.57.
• This reduction suggests that the global Facebook community was becoming increasingly
interconnected over time.
• Average distance between two random Facebook users in 2016 was 4.57 with 3.57
intermediaries [Repeat Experiment by Facebook in 2016]
 Small-world of Social Media!!!
• A 2020 study analyzed social media networks to test the small-world phenomenon
on platforms such as Instagram, LinkedIn, and Twitter using graph theory.
• The research aimed to understand how recent developments in social media have
influenced social networks and human behavior.
• The findings suggest that these platforms exhibit small-world properties,
characterized by high clustering and short average path lengths, which facilitate
efficient communication and information spread among users.
• A 2023 study examined the network of top museum Instagram accounts, revealing
that the connections among these accounts form a scale-free small-world network.
• This structure is characterized by a few highly connected nodes (hubs) and many
nodes with fewer connections, facilitating efficient information spread and robust
connectivity.
Testing the Small-World Phenomenon on Instagram
• Researcher: Katherine Li, University of Pennsylvania, 2020
• Objective: Investigate if Instagram exhibits the small-world phenomenon, where
individuals are connected through short chains of acquaintances.
• Methodology:
– Adapted Milgram's 1969 small-world experiment to the Instagram platform.
– an Instagram user was selected as the target user.
– Next, a group of Instagram users were selected to be starting users.
– Like the participants in Milgram’s study, they attempted to generate an “acquaintance
chain” from themselves to the target user.
– Each starting user was given a picture that described this experiment, listed the
Instagram username of the target user, and asked them to send the picture on.
• The experiment demonstrated that Instagram maintains small-world properties.
• Users are typically separated by a short number of intermediate connections, facilitating
rapid information dissemination and community building. Value between 2.3 to 4.37 less
than FaceBook
 High Average Local Clustering Coefficient
Neighbors of a node tend
to be highly connected
with each other at
individual level

In Facebook social graph,

for users with 100 friends
have average local
clustering coefficient of
0.14
Clustering coefficient of
Facebook Social Graph
https://www.sciencedirect.com/science
For a graph of 150 million Ugander et al. (2011)
/article/pii/S0166218X16304589 nodes, the number is
unexpectedly high
Impact
• Community Formation
– Users tend to form groups based on common interests, professions, or locations.
– Example: LinkedIn professional networks often show high clustering within the same
industry.
• Efficient Information Diffusion
– Content spreads rapidly within clustered groups.
– Example: Viral posts on Instagram and Facebook often gain traction within close-knit
groups before reaching a broader audience.T
• Trust and Social Influence
– High clustering increases trust within groups, leading to stronger influence.
– Example: In e-commerce networks (e.g., Facebook Marketplace), people are more
likely to trust recommendations from mutual connections.
• Network Resilience
– Even if some connections are lost, information can still circulate due to multiple
redundant links.
– Example: On Twitter (X), breaking news or trending topics persist in highly connected
sub-networks even if some original tweets are removed.
 Experimental Analysis

Social Network Average Path Length Clustering Coefficient

Approximately 2.32
Instagram 0.42
steps
High (specific value not
LinkedIn Approximately 3.5 steps
provided)
Low to Moderate
Twitter Approximately 4.8 steps (specific value not
provided)
 Scale-free Property: Power Law
Power Law: a relative change in the value of one
variable leads to the proportional change in the value
of other variable
Independent of the initial values of both the variable
Mathematically,
𝑦 ∝ 𝑥 −𝑏 , 𝑏 ∈ ℝ
Functions that follows power-law are scale-invariant
Pareto Principle (or the 80/20 rule) in Economics: 80%
of the outcomes are results of 20% of the causes
Power law principle is also coined as Pareto
https://exploitingchange.com/2016/09/14/a Distribution
nother-powerful-idea-the-power-law/
 Distributions – Real Examples
• Wealth Distribution:
– Most individuals have average capitals,
– Few are considered wealthy.
– Exponentially more individuals with average
capital than the wealthier ones.
• City Population:
– A few metropolitan areas are densely populated
– Most cities have an average population size. Herbert A Simon,
On a Class of Skew Distribution Functions, 1955
• Social Media:
– We observe the same phenomenon regularly The Pareto principle
(80–20 rule): 80% of the effects come
when measuring popularity or interestingness for from 20% of the causes
entities.
Distributions
• Site Popularity:
– Many sites are visited less than a 1,000 times a month
– A few are visited more than a million times daily
• User Activity:
– Social media users are often active on a few sites
– Some individuals are active on hundreds of sites
• Product Price:
– There are exponentially more modestly priced products for sale compared to
expensive ones.
• Friendships:
– Many individuals with a few friends and a handful of users with thousands of
friends
– (Degree Distribution)
Simon Model
• Herbert Simon is widely recognized for his significant contribution to understanding
power laws in social networks, particularly through his "Simon model" which
explains how a system with preferential attachment can generate power-law
distributions
• A small number of nodes in a network hold a disproportionate amount of
connections, mirroring phenomena observed in real social networks
• Essentially, the more connected a node is, the more likely it is to gain further
connections over time.
• Key points about Herbert Simon and power laws:
• The Simon Model describes a mechanism where new elements (like individuals in a
social network) are added to a system with a higher probability of attaching to
already well-connected elements, leading to a power-law distribution of
connections.
Simon Model
• Application to Language: Simon initially applied his model to explain the
frequency distribution of words in a text, where common words appear
much more frequently than rare words, following a power law pattern.
• Concept of "Preferential Attachment": A key element of the Simon model
is the concept of preferential attachment, meaning that new connections
are more likely to be made to nodes with existing high connectivity.
• Relevance to Social Networks: By applying the Simon model to social
networks, researchers can explain why a small number of individuals in a
social group tend to have significantly more connections than the
majority.
Scale Free Networks

• A Scale Free Network is one in which the degree distribution of nodes

follows a power law.
• The power law means that the vast majority of nodes have very few
connections, while a few important nodes (we call them Hubs) have a
huge number of connections.
• Key Reasons for the Term "Scale-Free"
• Power-Law Distribution
–In most natural and random networks, node degrees follow a bell
curve (Gaussian distribution), meaning most nodes have a similar
number of connections.
–In scale-free networks, the degree distribution follows a power law
Scale Free Networks
• No Characteristic Scale
– In networks like Facebook, Instagram, Twitter, etc., you cannot define an
"average" or "typical" number of connections.
– The presence of super-connectors (hubs) makes the network highly
heterogeneous, meaning different nodes have vastly different connection levels.
– In contrast, in a network with a characteristic scale (e.g., random networks), most
nodes would have a similar number of connections.
• Preferential Attachment ("Rich Get Richer" Effect)
– New nodes joining the network prefer to connect to high-degree nodes (hubs)
rather than randomly selecting connections.
– This self-organizing mechanism results in a few nodes accumulating
disproportionately high connectivity.
– For example, a new Instagram user is more likely to follow Virat Kohli or some well
known person rather than an unknown user.
Scale Free Networks - Implications
• Robust to Random Failures
– If random users drop out, the network still functions.
• Vulnerable to Targeted Attacks
– If key hubs (e.g., top influencers) are removed, it can fragment the network.
• Highly Efficient Information Flow
– Content, news, and trends spread fast due to influential hubs.
• Community Formation:
– Smaller clusters of users form within the network, but a few central nodes connect
them all.
• Viral Content Spread:
– Influencers play a huge role in making content viral.
• Marketing Strategies:
– Brands target hubs (influencers) for maximum reach.
• Fake News & Misinformation:
– Misinformation spreads quickly due to central hubs.
• Platform Growth & Engagement:
– Scale-free properties help social networks sustain user engagement.
 A typical shape of a power-
law distribution
Power-Law Distribution

• Many real-world networks exhibit a power-

law distribution.
• Power-laws seem to dominate
• When the quantity being measured can
be viewed as a type of popularity.
Log-Log
• A power-law distribution plot
• Small occurrences: common
• Large instances: extremely rare
The tail of the power-law distribution is long!
• The Loooooong Tail
Are most sales being
generated by a small set of
items that are enormously
popular?

OR
The total sales volume of unpopular
By a much larger population of items, taken together, is very
items that are each individually significant.
 57% of Amazon’s sales is
less popular? from the long tail
 Power Law in Scale-Free Social Networks
• A scale-free network is a type of network where a few nodes (users) have a
massive number of connections, while most nodes have only a few. This follows
a power-law degree distribution.
• Examples :
–Facebook & Instagram – Celebrities and influencers (e.g., Cristiano Ronaldo,
Virat kohli) have millions of followers, while most users have only a few
hundred.
–Twitter (X) – A few accounts (e.g., Elon Musk, Narendra Modi) dominate
conversations with millions of followers, while most users have a small
audience.
–LinkedIn – Thought leaders and CEOs (e.g., Satya Nadella) have vast
professional networks, while most professionals have relatively small ones.
Impact

• Virality & Influence: A tweet or post from a highly connected user can
reach millions instantly.
• Misinformation Spread: Fake news can spread quickly when influential
users share it.
• Targeted Marketing: Companies can use power-law properties to focus
on influential users for advertising.
• By understanding scale-free networks, social media platforms can design
better recommendation systems, control misinformation, and optimize
network structures.
Impact of the Long Tail
• The Long Tail allows niche creators to find an audience despite not being top influencers.
– Example: On Instagram, a small travel blogger with 5K followers might not compete with
Virat Kohli but can still attract a dedicated niche audience.
– Platforms like YouTube, Instagram, and Facebook encourage niche content discovery using
recommendation algorithms.
• Brands increasingly target micro- and nano-influencers rather than only top celebrities.
– Example: Local businesses in India prefer collaborating with regional influencers rather
than Bollywood stars.
• Network Resilience & Decentralization
– Unlike scale-free networks dominated by hubs, the Long Tail provides redundancy and
prevents total collapse if a few key users (hubs) leave.
– Example: On Twitter (X), even if Elon Musk deletes his account, millions of niche
conversations will still continue.
• Platforms like Facebook and LinkedIn monetize engagement from the Long Tail by:
– Personalized ads for niche communities
– Subscriptions (e.g., LinkedIn Premium for professionals in small industries)
Network Models
• A basic problem in network modeling is to define a random process that
generates networks that are similar to those in the real world.
• The simplest model:
• Suppose we want a network with N nodes and E edges
–Create a graph with N nodes
– For every pair of nodes (i, j), connect them with probability p
– If we want the expected number of edges to be E, then we should set

• This is known as the “Erdos-Renyi” random graph model

 Synthetic Networks: Random Network Model
• Also popularly known as Erdős and Rényi model (or ER
model)
• A number of variants of the model
• Popular variants:
– 𝐺(𝑁, 𝐾) model [Erdős and Rényi 1959]: From the set
of all networks of 𝑁 nodes and 𝐾 edges. a network is
chosen uniformly at random
– 𝐺(𝑁, 𝑝) model [Gilbert 1959]: Network has 𝑁 nodes,
and any random pair of nodes has a probability 𝑝 of
being adjacent independently with any other pair of
nodes in the network
• Both the variants behave identically in the limiting case
𝟏
• 𝐺 𝑁, 𝑝 model considered as the standard random 𝑮(𝟏𝟔, )
An instance of
𝟕
network model network
Random Graphs

• We have to assume how friendships are formed

–The most basic form:
Random Graph assumption:
Edges (i.e., friendships) between nodes (i.e.,
individuals) are formed randomly.

We discuss two random graph models 𝐺(𝑛, 𝑝) and 𝐺(𝑛, 𝑚)

Random Graph Model - 𝑮(𝒏, 𝒑)

• Consider a graph with a fixed number of nodes 𝑛

𝑛
• Any of the 2
edges can be formed independently, with probability p

• The graph is called a 𝐺(𝑛, 𝑝) random graph

Random Graph Model - 𝑮(𝒏, 𝒎)
• Assume both number of nodes 𝑛 and number of edges
𝑚 are fixed.
• Determine which 𝑚 edges are selected from the set of
possible edges

• Let Ω denote the set of graphs with 𝑛 nodes and

𝑚 edges
–There are |Ω| different graphs with 𝑛 nodes and
𝑚 edges This model was first proposed
• To generate a random graph, we uniformly select one of by
Paul Erdös and Alfred Rényi
the |Ω| graphs (the selection probability is 1/|Ω|)
Modeling Random Graphs, Cont.

• Similarities:
–In the limit (when 𝑛 is large), both 𝐺(𝑛, 𝑝) and 𝐺(𝑛, 𝑚) models
act similarly
𝑛
• The expected number of edges in 𝐺(𝑛, 𝑝) is 2
𝑝
𝑛
• We can set 2
𝑝 = 𝑚 and in the limit, we should get similar results
• Differences:
–The 𝐺(𝑛, 𝑚) model contains a fixed number of edges
–The 𝐺(𝑛, 𝑝) model is likely to contain none or all possible edges
Degree Distribution

• When computing degree distribution, we estimate the probability of

observing 𝑃(𝑑𝑣 = 𝑑) for node 𝑣

• For a random graph generated by 𝐺(𝑛, 𝑝), this probability is

• This is a binomial degree distribution. In the limit this will become the
Poisson degree distribution
Erdős-Rényi Network: Degree Distribution
 For a node in 𝐺(𝑁, 𝑝) to have degree 𝑘, the
corresponding node must be adjacent to 𝑘 other nodes
of the network

𝑁−1
 We can choose these nodes in 𝑘
ways

 Probability 𝑃 𝑘 of a node to have degree 𝑘 is given by

𝑁−1 𝑘
𝑃 𝑘 = 𝑝 (1 − 𝑝)𝑁−1−𝑘
𝑘

 Letting 𝑁 → ∞,
𝑒− 𝑑 𝑑 𝑘
Comparison of degree distribution 𝑃 𝑘 =
𝑘!
Instagram – Degree Distribution
Degree distribution of the Twitter (X) friendship graph.
 Erdős-Rényi Networks vs. Real-life Networks:
Presence of Outliers
In an Erdős-Rényi Network,
probability of having a node
with a high degree is
extremely low
probability of a node with
2000 neighbours is 10−27 !
In real-world networks, such
nodes exist (Hubs)
Celebrities in social networks
 Erdős-Rényi Network: Average Path Length
When 𝑙𝑚𝑎𝑥 represent the maximum path length of
𝐺(𝑁, 𝑝),

1+ 𝑑 + 𝑑 2 + 𝑑 3 + ⋯⋯⋯+ 𝑑 𝑙𝑚𝑎𝑥 =𝑁

When 𝑑 ≫ 1, the above yields,

𝑙𝑜𝑔𝑁
𝑙𝑚𝑎𝑥 ≈ 𝑙𝑜𝑔 𝑑

Further approximation yields,

𝑙 ∝ 𝑙𝑜𝑔𝑁

Theorem: Erdős-Rényi Networks follow small-world

A depiction of random network in tree format
property.
Erdős-Rényi Network: Clustering Coefficient

In 𝐺 𝑁, 𝑝
𝑑
 Number of possible edges between neighbours of a node: 2
𝑑
 Expected number of edges between these nodes: 𝑝 × 2
The above yields, the local clustering coefficient for a node 𝑣𝑖 ∈ 𝐺
𝑑
𝐶𝑖 = 𝑝 ≈
𝑁
Theorem: The local clustering coefficient for any node in an Erdős-Rényi Network is
inversely proportional to the size of the network
Note: The local clustering coefficient for any node in an Erdős-Rényi Network does not
depend on the degree of the node
 Erdős-Rényi Networks vs. Real-life Networks:
Clustering Coefficient
Avg. Clustering
Network
Coefficient
local clustering coefficients in Erdős-Rényi
ER Random Graph Networks decreases with the increase in
~ 0.001
(N=10K, p=0.001) network size
Facebook (global
~ 0.61 Nodes having high local clustering coefficient
network)
exist in enormously large real-life networks
Instagram ~ 0.55

Twitter ~ 0.23 Echo chambers in large social networks like

Facebook
LinkedIn ~ 0.39
Clustering Coefficient: Random Graphs vs. Real Social Networks

• Random Graphs (Erdős–Rényi Model - ER)

–Clustering Coefficient Approx = (edge probability P).
–Low clustering because edges are placed randomly.
–No community structures.
• Real Social Networks (Facebook, Instagram, Twitter, LinkedIn)
–High clustering coefficient due to triadic closure (friends of friends
tend to be friends).
–Users form groups, circles, and communities.
–Hubs (influencers) have high local clustering.
 ER Random Graphs vs. Real Social Networks
Property ER Random Graphs Real Social Networks
Poisson-like (most nodes Power-law (few hubs, many
Degree Distribution
have similar degrees) low-degree nodes)
High (friends of friends tend
Clustering Coefficient Low approx ≈p
to be friends)
Short (small-world-like for Even shorter due to hubs (six
Shortest Path Length
large NNN) degrees of separation)
Random connections, no Strong communities and
Network Structure
clear communities clusters
Rare (no preferential Common (few nodes have
Hubs / Influencers
attachment) very high degrees)
Does not scale like real-world Scales naturally due to
Scalability
networks preferential attachment
Erdős–Rényi Random Graph – Nodes are randomly connected, resulting in a low
clustering coefficient and no hubs.
Scale-Free Network (Real Social Network Approximation) – A few highly connected
hubs emerge, creating a small-world structure with high clustering.
Why Use Random Graphs to Study Social Networks?
• Baseline Model: Provides a fundamental comparison for real-world networks.
• Mathematical Simplicity: Well-defined properties make them easier to
analyze.
• Predictive Power: Helps understand phase transitions, like giant component
formation.
• Giant Component Insight: Models when a network becomes mostly
connected, revealing how information or influence can spread.
• Null Model: Acts as a reference to detect deviations in real social networks.
• Scalability: Can be generated for large-scale simulations efficiently.
• Insight into Connectivity: Helps study network resilience and link formation.
 The Giant Component
• In random graphs, as we increase 𝑝, a
large fraction of nodes start getting
connected
–i.e., we have a path between any pair
• This large fraction forms a connected
component:
–Largest connected component, also
known as the Giant component
• In random graphs:
–𝑝 = 0
• the size of the giant component is 0
–𝑝 = 1
• the size of the giant component is 𝑛
The Giant Component

Probability (𝒑) 0.0 0.055 0.11 1.0

Average Node Degree (𝒄) 0.0 0.8 ≈1 n-1=9

Diameter 0 2 6 1

Giant Component Size 0 4 7 10

Average Path Length 0.0 1.5 2.66 1.0

Demo (𝑛 = 150) - From David Gleich
 1st Phase Transition (Rise of the Giant Component)

• Phase Transition: the point where diameter value starts to shrink in a random
graph
–We have other phase transitions in random graphs
• E.g., when the graph becomes connected
• The phase transition we focus on happens when
–average node degree 𝑐 = 1 (or when 𝑝 = 1/(𝑛 − 1) )
• At this Phase Transition:
1. The giant component, which just started to appear, starts to grow, and
2. The diameter, which just reached its maximum value, starts decreasing.
Random Graphs

If 𝒄 < 𝟏:
– small, isolated clusters
– small diameters
– short path lengths
1.0
At 𝒄 = 𝟏:
– a giant component appears
– diameter peaks
– path lengths are long
For 𝒄 > 𝟏:
– almost all nodes connected 0 1.0 c
– diameter shrinks
– path lengths shorten
phase transition
Modeling with Random Graphs

• Compute the average degree 𝑐 in the real-world graph

• Compute 𝑝 using 𝑐/(𝑛 − 1) = 𝑝
• Generate the random graph using 𝑝

• How representative is the generated graph?

– [Degree Distribution] Random graphs do not have a power-law degree distribution
– [Average Path Length] Random graphs perform well in modeling the average path
lengths
– [Clustering Coefficient] Random graphs drastically underestimate the clustering
coefficient
 Watts-Strogatz (WS) Model
• This is a generative model for small-world networks that balances regularity & randomness.
• It helps explain how real-world networks exhibit high clustering and short path lengths.
• Key Properties:
– High Clustering Coefficient: Nodes tend to form tightly connected groups, similar to real
social networks.
– Short Average Path Length: Despite high clustering, only a few random rewires reduce
the shortest path length significantly, leading to the small-world effect.
– Degree Distribution: Unlike scale-free networks, WS networks do not follow a power-law
distribution but have a more uniform degree distribution.

The model starts with a regular

lattice and starts adding random
edges [through rewiring]
 Comparison to Real Social Networks:

Property Watts-Strogatz Model Real Social Networks

Clustering Coefficient High High

Average Path Length Short Short

Degree Distribution Uniform Power-law (Scale-free)

Small-World Effect Present Present

Preferential Attachment Model - Properties

• Nodes with higher degrees are more likely to attract new connections
(rich-get-richer effect).
• Degree distribution follows a power law: few nodes with very high
degrees, many nodes with low degrees.
• Results in a scale-free network with highly connected hubs.
• Found in social networks like Facebook, Twitter, and LinkedIn, where
influencers or popular accounts have significantly more connections.
• Enables robust connectivity but can be vulnerable to targeted attacks on
hubs.
Barabasi-Albert Network Model
• Real-life social networks often evolve with time
• Originates with a small seed network
• The network grows as new nodes and edges gets attached to the
network with time
• Barabasi-Albert model follows the same principle of network
evolution
• Also known as Preferential Attachment model or rich gets richer
model
• Generates scale-free networks
Preferential Attachment: Example

• Node 𝑣 arrives
𝑃(1) = 1/7 𝑃(5) = 3/7
𝑣

𝑃(2) = 1/7 𝑃(4) = 0

• 𝑃(1) = 1/7
• 𝑃(2) = 1/7 1 5

• 𝑃(3) = 2/7 𝑃(3) = 2/7

• 𝑃(4) =0
• 𝑃(5) = 3/7 2 3 4
 Barabasi-Albert Model: Network Growth

𝐺 = 20 𝐺 = 50 𝐺 = 100
Average Path Length = 2.16 Average Path Length = 2.69 Average Path Length = 3.02

• https://www.researchgate.net/publication/259742981_Information_Theory_Kolmogorov_Complexity_and_Algorithmic_Probability_in_Network_Biology
 Barabási-Albert (BA) Watts-Strogatz (WS)
Property Real Social Networks
Model Model
No, follows a more
Power Law Degree Yes, follows power-law Yes, follows power-law
uniform degree
Distribution distribution distribution
distribution
High Clustering
Moderate clustering High clustering Very high clustering
Coefficient
Moderate, depends on
Yes, strong small-world
Small-World Property preferential Yes, by design
property
attachment
Yes, hubs exist
Hubs (Highly Yes, hubs naturally No, hubs do not
(influencers,
Connected Nodes) emerge naturally form
celebrities)
Grows with
Starts with rewiring of Grows dynamically
Connectivity Growth preferential
regular network with new users
attachment
Models scale-free Models small-world Captures both scale-
Applicability to Social
nature well, but low behavior well, but lacks free and small-world
Networks
clustering power-law distribution properties
END