Social Networking and Mining
-Dr. Jyoti Shokeen
(Assistant Professor, IT)
IGDTUW
Dr. Jyoti Shokeen- Social networking and Mining
Closeness Centrality
• Measures how close a node is to all others in the network.
• Efficiency in spreading information
where d(v,u) is the shortest path between nodes u and v.
Degree Centrality: how many people you know
Closeness Centrality: how quickly you can reach everyone
Dr. Jyoti Shokeen-Social networking and Mining
Eigenvector Centrality
• Measures a node’s influence based on the importance of its
neighbors.
• Example: Google's PageRank algorithm is a variant of
eigenvector centrality.
x is the eigenvector of A
λ is the largest eigenvalue,
x_i gives the centrality score of node i
Dr. Jyoti Shokeen-Social networking and Mining
Power Law & Network Properties
Power Law Distribution:
In real networks, a few nodes have many connections,
most have few
Degree distribution follows: [P(k) ∝ k^(-γ)]
Where P(k)=Probability that a node has degree k
γ = constant exponent (typically between 2 and 3)
Real-World Properties:
Small World Effect: Short path between any two nodes
Scale-Free Networks: Presence of hubs; robust to random
failure, vulnerable to targeted attack
Dr. Jyoti Shokeen- Social networking and Mining
Clustering coefficient
The clustering coefficient tells us how close a node’s
neighbors are to being a complete clique (all
connected to each other).
OR
It measures how densely connected the immediate neighbours
of a node are to each other.
Types of clustering coefficient:
a. Local Clustering Coefficient (per node)
b. Global Clustering Coefficient
Dr. Jyoti Shokeen- Social networking and Mining
Local Clustering coefficient
Dr. Jyoti Shokeen- Social networking and Mining
Find the clustering coefficient?
Dr. Jyoti Shokeen- Social networking and Mining
Find the clustering coefficient?
Dr. Jyoti Shokeen- Social networking and Mining
Calculate local CC for node v
Dr. Jyoti Shokeen- Social networking and Mining
Global Clustering coefficient
Dr. Jyoti Shokeen- Social networking and Mining
Network Graphs to Analyze
Zachary's Karate Club
Dolphins' Social Network
US Politics Books Network
US College Football Network
Dr. Jyoti Shokeen- Social networking and Mining
Network Models
A. Random Network Model (Erdős-Rényi)
Edges are added randomly with fixed probability
Degree distribution ~ Poisson
Not realistic for most real-world networks
B. Preferential Attachment Model (Barabási–Albert)
Nodes attach to existing nodes with high degree
Results in hubs (rich-get-richer)
Degree distribution follows power law
Matches many social networks
Dr. Jyoti Shokeen- Social networking and Mining
Random Network Model (Erdős–
Rényi)
Understanding the G(n, p) and G(n, m) Models
Random Network Model (Erdős-Rényi)
Edges are added randomly with fixed probability
Degree distribution ~ Poisson
Not realistic for most real-world networks
One of the simplest models for generating random graphs
Two main forms: G(n, p) and G(n, m)
Dr. Jyoti Shokeen- Social networking and Mining
How It Works – G(n, p) Model
Start with n isolated nodes
For each of the n(n-1)/2 possible edges:
– Add edge with probability p
Result: A random network
Dr. Jyoti Shokeen- Social networking and Mining
How It Works – G(n, m) Model
Start with n isolated nodes
n = number of nodes.
m = exact number of edges to include, chosen uniformly at
random from all possible edges.
Result: A random network
Dr. Jyoti Shokeen- Social networking and Mining
Key Properties
Degree distribution: Binomial (approximates Poisson for
large n, small p)
Average degree: <k> = p × (n-1)
Clustering coefficient: p (low)
Short average path length: log(n)/log(<k>)
Limitations of ER Model
Low clustering compared to real-world networks
Degree distribution is narrow (Poisson)
Lacks community structure
Example
Preferential Attachment Model
(Barabási–Albert)
Understanding the 'Rich-Get-Richer' Network
Growth Mechanism
Basic Idea
New nodes prefer to attach to already well-connected nodes
The higher the degree of a node, the more likely it is to gain
new links
Also called 'rich-get-richer' mechanism
How It Works – Barabási–Albert Model
Start with a small connected network of m₀ nodes
Add a new node with m edges
Probability of connecting to node i: Pᵢ = kᵢ / Σⱼ kⱼ
Repeat until desired network size is reached
Key Properties
Degree distribution follows a power-law: P(k) ∼ k⁻³
Scale-free: no characteristic degree
Higher clustering than ER model
Small-world property: short average path lengths
Comparison with Erdős–Rényi Model
ER: Poisson degree distribution; PA: Power-law distribution
ER: Few hubs; PA: Many hubs
ER: Low clustering; PA: Moderate clustering
ER: Random edges; PA: Incremental, preferential edges
Real-World Examples
Internet topology – few hubs with many connections
Citation networks – famous papers get more citations
Social media – popular accounts attract more followers
Mini Project Idea
Collect Twitter data for a hashtag
Create a graph of users replying to each other
Use NetworkX to calculate centrality
Visualize in Gephi
Dr. Jyoti Shokeen- Social networking and Mining
References
https://www.sciencedirect.com/topics/computer-
science/eigenvector-centrality
Rani, Poonam, and Jyoti Shokeen. "A survey of tools for
social network analysis." International Journal of Web
Engineering and Technology 16.3 (2021): 189-216.
https://www.jsums.edu/nmeghanathan/files/2015/08/CS
C641-Fall2015-Module-2-Centrality-Measures.pdf
Dr. Jyoti Shokeen- Social networking and Mining
Thanks
Dr. Poonam Rani - Soft Computing
