SOCIAL MEDIA MINING —

Complete Exam Notes (Units

I–V)
[Link] AI & DS — Each topic written as a 6-mark (2–3
page) answer, plain English, worked examples, ASCII
diagrams.

UNIT I: Introduction & Graph

Essentials

1. What is Social Media Mining? New

Challenges

Definition: Social Media Mining is the process of

representing, analyzing, and extracting actionable
patterns from social media data using techniques
from network science, data mining, machine learning,
and statistics.

Why it's different from traditional data mining:

 Data is networked (users connected to users) —
not independent rows like a normal table

Massive scale — billions of nodes/edges

Dynamic — networks change every second (new

edges/nodes)

Noisy & incomplete — fake accounts, missing

profile info

Multi-modal — text, images, video, network

structure all together

New Challenges (exam favorite — list format):

1. Big Data problem — volume, velocity, variety too

large for classical algorithms

2. Noise removal — spam, bots, fake news

3. Data validity — self-reported info unreliable

4. Model construction — networks violate the

"independent and identically distributed" (i.i.d.)
assumption used in classical stats

5. Privacy — mining personal data raises

ethical/legal issues

6. Heterogeneity — combining text + graph + image

data

Cross-reference: These challenges motivate why Unit

III (Data Mining Essentials) needs special
preprocessing before community detection.
2. Graph Basics

A graph G = (V, E) consists of:

V = set of vertices/nodes (e.g., users)

E = set of edges (e.g., friendships, follows)

Order of graph = |V| (number of nodes)

Size of graph = |E| (number of edges)

ASCII Diagram — Basic Graph

A ---- B
| |
| |
C ---- D

V = {A, B, C, D}
E = {(A,B), (A,C), (B,D), (C,D)}
Order = 4, Size = 4

Degree of a node = number of edges attached to it.

deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2

Handshaking Lemma: Sum of all degrees = 2 × |E|

Check: 2+2+2+2 = 8 = 2×4 ✓ (this is a common 6-
mark numeric question)

3. Graph Representation
(a) Adjacency Matrix — n × n matrix, entry = 1 if edge
exists else 0

A B C D
A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 1]
D [0, 1, 1, 0]

Space: O(n²) — good for dense graphs

Edge lookup: O(1)

(b) Adjacency List — for each node, list its neighbors

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

Space: O(n + m) — good for sparse graphs (social

networks are usually sparse!)

Edge lookup: O(degree)

Worked example question: "Given adjacency list,

construct adjacency matrix" — just reverse the process
above.

4. Types of Graphs
Type Description Example

Edge has no
Undirected direction Facebook friend
(mutual)

Edge has
Directed
direction Twitter follow
(Digraph)
(arrow)

Number of
Edge has a
Weighted messages
numeric weight
exchanged

Simple friend
Unweighted All edges equal
link

Two disjoint
sets, edges Users–Movies
Bipartite
only between (ratings)
sets

Multiple edges
Multiple emails
allowed
Multigraph between two
between same
people
pair

Signed Edges have +/- Trust/distrust

graph sign network
 Directed Graph example:
A ---> B
^ |
| v
D <--- C
(A follows B, B follows C, C follows D, D
follows A)

Bipartite Graph example:

Users Movies
U1 -------- M1
U1 -------- M2
U2 -------- M1
U3 -------- M2

Bipartite graphs are the foundation of collaborative

filtering in Unit V.

5. Connectivity in Graphs

Connected graph: path exists between every pair

of nodes

Disconnected graph: made of multiple

components

Strongly connected (directed): path exists from

every node to every other node respecting
direction
 Weakly connected (directed): connected if you
ignore direction

Component: maximal connected subgraph.

Two Components:
A---B E---F
|
C
(Component 1: A,B,C) (Component 2: E,F)

Cut vertex (articulation point): removing it

disconnects the graph.
Bridge: edge whose removal disconnects the graph.

A---B---C---D
(removing B disconnects {A} from
{C,D})
B is a cut vertex; edge (B,C) could
be a bridge

6. Special Graphs

Tree: connected, no cycles, |E| = |V| - 1

Complete graph (Kn): every pair of nodes

connected; |E| = n(n-1)/2

Clique: complete subgraph within a larger graph

(used in community detection)
 Regular graph: all nodes have the same degree

Ego network: a node + its immediate neighbors +

edges among them (used heavily in real SMM
analysis, e.g., "your Facebook friend circle")

Ego Network of A:
B
/ \
A---C
\ /
D
(A is ego; B,C,D are alters; edges among
alters shown too)

7. Graph Algorithms

BFS (Breadth-First Search): explores level by level

using a queue. Used to find shortest path
(unweighted) and connected components.

DFS (Depth-First Search): explores as deep as

possible using a stack/recursion. Used to detect
cycles, find bridges/articulation points.

Worked Example (BFS shortest path):

Graph: A-B, A-C, B-D, C-D, D-E

Find shortest path A to E using BFS:

 Level 0: A
Level 1: B, C (A's neighbors)
Level 2: D (B,C's neighbor)
Level 3: E (D's neighbor)

Path: A -> B -> D -> E (length 3)

Dijkstra's Algorithm: shortest path in weighted graphs

— pick the unvisited node with smallest tentative
distance, relax its neighbors, repeat.

Cross-reference: BFS-based shortest paths underlie

closeness centrality in Unit II.

UNIT II: Network Measures &

Network Models

1. Centrality Measures

Centrality answers: "Who is important in this

network?"

(a) Degree Centrality

C_deg(v) = deg(v) / (n-1)

Normalized by max possible degree. Higher = more
directly connected.

(b) Closeness Centrality

C_close(v) = (n-1) / Σ d(v,u) for all u ≠

v

Higher = closer (on average) to everyone else — good

"broadcaster."

(c) Betweenness Centrality

C_between(v) = Σ [σ_st(v) / σ_st] (over

all pairs s,t)

where σ_st = number of shortest paths from s to t,

σ_st(v) = number of those passing through v.
High = "broker"/"bridge" — controls information flow
between groups.

(d) Eigenvector Centrality

A node is important if its neighbors are important

(recursive definition). Computed as the principal
eigenvector of the adjacency matrix. Used by Google's
PageRank (a variant).

Worked Numeric Example:

 Graph: A---B---C---D---E
(a path/line graph, 5 nodes)

Degree Centrality:
deg(A)=1, deg(B)=2, deg(C)=2, deg(D)=2,
deg(E)=1
C_deg(B) = 2/4 = 0.5

Closeness Centrality of C (middle node):

Distances from C: to A=2, to B=1, to D=1,
to E=2 → sum = 6
C_close(C) = 4/6 = 0.667 (highest — C is
most central)

Betweenness Centrality of C:
All shortest paths between {A,B} and {D,E}
pass through C.
Pairs: (A,D),(A,E),(B,D),(B,E) — 4 pairs,
all pass through C → high betweenness
Pairs (A,B): path doesn't use C at all → 0
contribution

So C has the highest betweenness — it's the

"bridge" of the line graph.

2. Transitivity and Reciprocity

Transitivity (Clustering Coefficient): "friend of my

friend is my friend" tendency.
 C = 3 × (number of triangles) / (number of
connected triples)

Worked Example:

Graph: A-B, B-C, A-C, B-D

Triangles: {A,B,C} → 1 triangle

Connected triples (paths of length 2, "V
shapes"):
A-B-C, A-C-B, B-A-C → these + also B-C-
D (via B), A-B-D
Count triples centered at each node:
A: (B,C) → 1 triple
B: (A,C),(A,D),(C,D) → 3 triples
C: (A,B) → 1 triple
D: none (only 1 edge)
Total triples = 5, triangles found = 1
(only ABC closes)

C = 3×1 / 5 = 0.6

Reciprocity (directed graphs only): fraction of

directed edges that are reciprocated (mutual).

Reciprocity = (number of mutual edges) /

(total directed edges)

Example: if A→B and B→A both exist, that's

reciprocated.
3. Balance and Status (Signed
Networks)

Structural Balance Theory — for signed triads (+ =

friend, - = enemy):

Balanced: "friend of my friend is my friend" (+++)

or "enemy of my enemy is my friend" (+ - -, with
even number of minuses)

Unbalanced: odd number of negative edges in the

triad

Balanced triad (+ + +): Unbalanced

triad (+ + -):
A A
+ + + -
B----C B----C
(+) (+)
All friends = balanced Two friends
+ one enemy = unbalanced (tension!)

Status Theory: a directed alternative — edges

represent "who has higher status." A + edge from A to
B means "A thinks B has higher status."

4. Similarity

Used to find nodes that behave alike (basis of link

prediction & recommendation).
Structural equivalence: two nodes are similar if they
connect to the same neighbors.

Cosine similarity (using adjacency rows):

sim(A,B) = (A·B) / (|A||B|)

Jaccard similarity:

sim(A,B) = |N(A) ∩ N(B)| / |N(A) ∪ N(B)|

Worked Example:

N(A) = {C, D, E}
N(B) = {C, D, F}

Intersection = {C, D} → size 2

Union = {C, D, E, F} → size 4

Jaccard(A,B) = 2/4 = 0.5

5. Properties of Real-World Networks

1. Small-world property: short average path length

(≈ log n), e.g., "six degrees of separation"

2. High clustering coefficient: much higher than

random graphs
 3. Power-law degree distribution ("scale-free"): few
hubs with huge degree, many nodes with low
degree

P(k) ~ k^(-γ)

4. Community structure: dense clusters loosely

connected to each other

6. Random Graph Model (Erdős–

Rényi)

G(n,p) model: n nodes, each possible edge included

independently with probability p.

Expected number of edges = p × n(n-1)/2

Degree distribution follows a binomial/Poisson

distribution (NOT power law) — this is why it fails
to model real social networks (no hubs)

Low clustering coefficient, unlike real networks

Worked Example:

n = 100, p = 0.05
Expected edges = 0.05 × (100×99)/2 = 0.05 ×
4950 = 247.5
Expected average degree = p×(n-1) = 0.05×99
≈ 4.95
7. Small-World Model (Watts–
Strogatz)

Construction:

1. Start with a ring lattice — n nodes, each

connected to k nearest neighbors

2. Rewire each edge with probability p to a random

node

Before rewiring (ring): After

rewiring (p small):
o-o-o-o-o-o o-o-o-o-o-
o
(each connects to (a few
edges "jump"
2 nearest neighbors) across
the ring)

Result: achieves BOTH high clustering (from lattice)

AND short path length (from a few random "shortcut"
rewired edges) — matches real social networks. This
is the key insight of the model (small p already
collapses path length dramatically while clustering
stays high).
8. Preferential Attachment Model
(Barabási–Albert)

Rule: "Rich get richer." New nodes prefer to attach to

nodes that already have high degree.

P(attach to node i) = deg(i) / Σ deg(all

nodes)

Growth process:

1. Start with small seed network

2. Add a new node with m edges

3. Each new edge connects preferentially to high-

degree existing nodes

4. Repeat → produces power-law degree

distribution (hubs emerge naturally)

Worked Example:

Current degrees: A=5, B=3, C=2 (total

degree = 10)
New node joins, forms 1 edge.
P(attach to A) = 5/10 = 0.5
P(attach to B) = 3/10 = 0.3
P(attach to C) = 2/10 = 0.2
→ A is most likely to gain the new
connection (hub gets richer)
Cross-reference: BA model explains why real
networks (Unit I graph properties) show hubs, unlike
Erdős–Rényi random graphs.

UNIT III: Data Mining

Essentials & Community
Analysis

1. Data, Data Preprocessing

Types of data in SMM: structured (user profile fields),

unstructured (text posts), network data (graph),
multimedia (images/video).

Preprocessing steps:

1. Cleaning — remove duplicates, fix missing values,

remove bots/spam

2. Integration — combine data from multiple sources

3. Transformation — normalization, encoding

categorical → numeric

4. Reduction — dimensionality reduction (PCA),

sampling large graphs
2. Data Mining Algorithms —
Supervised vs Unsupervised

Supervised Learning: labeled data, learns a mapping

input→output

Examples: classification (spam/not spam),

regression (predict engagement)

Algorithms: Decision Trees, Naive Bayes, SVM,

Logistic Regression

Unsupervised Learning: no labels, finds hidden

structure

Examples: clustering (grouping similar users),

community detection

Algorithms: k-means, hierarchical clustering,

Girvan-Newman

Supervised:
Unsupervised:
Input → [Model] → Label Input →
[Model] → Groups
(trained w/ known labels) (no labels
given)

3. Community Detection
Community: a group of nodes densely connected
internally, sparsely connected to the rest of the
network.

ASCII: Two communities bridged by one edge

Community 1 Community 2
A---B E---F
|\ /| |\ /|
| X | | X |
|/ \| |/ \|
C---D----------------G---H
(bridge edge D-G)

Girvan-Newman Algorithm (most important —

exam favorite)

Steps:

1. Compute betweenness centrality for all edges

2. Remove the edge with highest betweenness

3. Recompute betweenness for remaining edges

4. Repeat until no edges remain (or desired number

of communities reached)

5. Track modularity at each step; choose the split

with highest modularity

Why it works: Bridge edges between communities

carry the most shortest paths → highest
betweenness → removed first, naturally splitting
communities apart.

Worked Example (conceptual):

Graph: A-B, A-C, B-C, C-D, D-E, D-F, E-F

Step 1: Edge (C,D) is the bridge between

{A,B,C} and {D,E,F}
→ It has the highest edge
betweenness
Step 2: Remove (C,D)
Result: Two components — {A,B,C} and
{D,E,F}
These are the two communities!

Modularity (Q) — used to evaluate a

community split

Q = (1/2m) Σ [A_ij - (k_i·k_j)/(2m)] δ(c_i,

c_j)

where m = total edges, A_ij = adjacency entry, k_i,k_j =

degrees, δ=1 if same community else 0.

Q ranges roughly -0.5 to 1

Q > 0.3 typically indicates significant community

structure

Higher Q = better community partition (more

edges inside communities than expected by
 chance)

4. Community Evaluation

Metrics to judge quality of detected communities:

1. Modularity (Q) — as above

2. Conductance — ratio of edges leaving a

community to total edges touching it (lower =
better community)

3. NMI (Normalized Mutual Information) —

compares detected communities to ground truth

4. Density — internal edges / possible internal edges

(should be high)

Cross-reference: Community detection output feeds

directly into Unit V's "recommendation using social
context" — recommendations can be made within a
user's detected community.

UNIT IV: Information Diffusion

& Influence/Homophily

1. Herd Behavior
Individuals follow the actions of a larger group,
ignoring their own private information — happens
when the "cost" of following your own signal seems
too risky compared to going with the crowd.

Example: Everyone rushing to buy a stock because

others are buying, even without personal analysis.

2. Information Cascades

Definition: A cascade occurs when people ignore their

own signal and copy the decisions of those before
them, because the cumulative public evidence
outweighs their private belief.

Classic setup (Bikhchandani-Hirshleifer-Welch

model):

Person 1 decides based on own signal →

announces decision
Person 2 sees Person 1's decision. If it
conflicts with Person 2's own weak
signal, Person 2 may still copy Person 1
(public info seems stronger)
Person 3 sees BOTH prior decisions agree →
cascade begins,
Person 3 (and everyone after) copies
regardless of own signal

Result: fragile — cascades can be wrong and easily

reversed by one strong contrary signal.
3. Diffusion of Innovations

Rogers' model — describes how new ideas/products

spread through a population over time, following an
S-curve (sigmoid).

Adoption
|
____----‾‾‾‾
| ___----
| ___----
| ___----
|____----
+---------------------------------------
--- Time
Innovators Early Early Late
Laggards
(2.5%) Adopters Majority
Majority (16%)
(13.5%) (34%) (34%)

Categories (memorize %): Innovators 2.5% → Early

Adopters 13.5% → Early Majority 34% → Late Majority
34% → Laggards 16%

4. Epidemic Models (SI, SIS, SIR)

Model how "infection" (idea/behavior/disease)

spreads through a network.
SI Model (Susceptible → Infected): once infected,
stays infected forever.

S ---β---> I (β = infection rate)

SIS Model (Susceptible → Infected → Susceptible):

can recover but become susceptible again (e.g., flu).

S ---β---> I ---γ---> S (γ = recovery

rate, back to susceptible)

SIR Model (Susceptible → Infected → Recovered):

recovered nodes are immune forever (e.g.,
chickenpox, or "old news" no longer being shared).

S ---β---> I ---γ---> R

Worked Example (SIR, discrete time):

Population: 100 nodes. β=0.3, γ=0.1. Start:

S=99, I=1, R=0

Day 1: new infections ≈ β × S × I / N =

0.3×99×1/100 ≈ 0.297 → I≈1.3
recoveries ≈ γ × I = 0.1×1 = 0.1
Day 1 totals (rounded): S≈98.7,
I≈1.2, R≈0.1

(exam usually just wants you to show the

formulas + one iteration,
 demonstrating you understand S decreases,
I rises then falls, R rises monotonically)

Basic Reproduction Number R0 = β/γ — if R0 > 1,

epidemic spreads; if R0 < 1, dies out.
Example: β=0.3, γ=0.1 → R0 = 3 (spreads widely)

5. Measuring Assortativity

Assortativity: tendency of nodes to connect to other

nodes that are similar to themselves (e.g., high-
degree nodes connecting to other high-degree nodes).

Assortativity coefficient r (Pearson

correlation of degrees at each edge's
endpoints)
r > 0 → assortative (similar connect to
similar) — common in social networks
r < 0 → disassortative (hubs connect to
low-degree nodes) — common in
technological/bio networks (e.g., internet
router graphs)

6. Influence and Homophily

Influence: A's behavior causes B to adopt similar

behavior (causation, A → B)
Homophily: "Birds of a feather flock together" —
similar people become connected because they're
similar (correlation, not causation) — the similarity
precedes the connection.

Influence: Homophily:
A adopts X A and B are
already similar
| (same
interests)
v (A influences B) |
B later adopts X v
A and B
become friends
(both
already liked X)

7. Distinguishing Influence from

Homophily

This is HARD because both produce the same

observable pattern: connected people share
behaviors.

Techniques to distinguish:

1. Shuffle test: randomly reassign network ties; if

correlation of behavior persists even after
shuffling, it's likely homophily (pre-existing
similarity), not influence
 2. Time-order test: check whether the friendship
formed before or after the shared behavior
appeared

If similarity existed before the tie →

homophily

If similarity appeared after the tie → influence

3. Controlling for confounds: e.g., shared

environment (same school) may independently
cause both similarity and friendship

Cross-reference: Distinguishing influence/homophily

matters for Unit V — if it's influence, recommend
based on friends' actions; if homophily, recommend
based on latent similarity instead.

UNIT V: Recommendation
Systems & Behavior Analytics

1. Challenges in Recommendation

1. Cold start — new users/items have no history

2. Sparsity — most users rate/interact with only a

tiny fraction of items

3. Scalability — millions of users × millions of items

4. Trust/robustness — fake reviews, manipulation

 5. Diversity vs accuracy trade-off — over-
personalization creates "filter bubbles"

2. Classical Recommendation
Algorithms

(a) Content-Based Filtering

Recommend items similar to what the user already

liked, based on item features.

User liked: Action movies with Actor X

→ Recommend: other Action movies with
Actor X or similar actors

Uses similarity measures (cosine similarity between

item feature vectors) from Unit II.

(b) Collaborative Filtering (CF)

Recommend based on what similar users liked —

doesn't need item content, only the user-item
interaction (bipartite graph from Unit I!).

User-based CF:

Rating matrix:
Movie1 Movie2 Movie3
User A 5 4 ?
User B 5 4 2
 User C 1 2 5

A and B have similar ratings on Movie1,2 →

predict A's rating for Movie3
using B's rating (2) since B is A's
"nearest neighbor"
→ Predicted rating for A on Movie3 ≈ 2
(low)

Item-based CF: find items similar to each other

(based on co-rating patterns) instead of users.

Worked Example (cosine similarity for user-based

CF):

User A ratings vector: [5, 4, 0]

User B ratings vector: [5, 4, 2]

Cosine similarity = (A·B)/(|A||B|)

A·B = 5×5 + 4×4 + 0×2 = 25+16+0 = 41
|A| = √(25+16+0) = √41 ≈ 6.40
|B| = √(25+16+4) = √45 ≈ 6.71
sim(A,B) = 41/(6.40×6.71) ≈ 41/42.9 ≈ 0.955
(very similar → trust B's rating for
prediction)

(c) Hybrid Methods

Combine content-based + collaborative to overcome

cold start (e.g., Netflix, Amazon use hybrid models).
3. Recommendation Using Social
Context

Incorporate the social network itself (Unit II/III

concepts) into recommendations:

Trust-based recommendation: weight

recommendations from friends higher than
strangers

Community-aware recommendation: recommend

items popular within the user's detected
community (Unit III's Girvan-Newman output)

Social regularization: assume a user's

preferences should be close to their friends'
preferences mathematically (adds a network-
similarity term to the CF loss function)

Traditional CF: Social-context CF:

User → Item User --- Friends
(ratings only) \ /
v v
Item
(ratings influenced by
BOTH
own history AND
friends' taste)

4. Evaluating Recommendations
Metrics:

RMSE (Root Mean Squared Error) — for rating

prediction accuracy:

RMSE = √( (1/n) Σ (predicted - actual)²

)

Precision@k / Recall@k — for top-k

recommendation lists

Precision@k = (relevant items in top-k)

/ k
Recall@k = (relevant items in top-k) /
(total relevant items)

Worked Example:

Recommended top-5 items: {A, B, C, D, E}

User actually liked: {A, C, F, G}

Relevant items in top-5 = {A, C} → 2 items

Precision@5 = 2/5 = 0.4
Recall@5 = 2/4 = 0.5 (total relevant = 4:
A,C,F,G)

5. Behavior Analytics

Individual Behavior
Study a single user's patterns: posting frequency,
sentiment, engagement patterns, activity cycles.
Often modeled with time-series methods or simple
statistical profiling (mean/variance of activity).

Collective Behavior

Study group/crowd-level patterns: how trends emerge,

viral content spread, coordinated behavior (bots,
campaigns).

Individual Behavior: Collective

Behavior:
One user's post timeline Aggregate
trend over
---|---|--|-----|---> time thousands
of users
/\
/\
/ \ /
\___
/ \__/
(viral spike then decay)

Key link: Collective behavior (Unit IV's information

diffusion, cascades) emerges from many individuals
independently making locally-rational decisions (herd
behavior) — tying Unit IV directly into Unit V's behavior
analytics topic.
Quick Cross-Unit Revision Map

Unit I (Graphs)
└─> feeds representation into Unit II
(Measures/Models)
Unit II (Centrality, Models)
└─> betweenness feeds into Unit III's
Girvan-Newman
└─> similarity feeds into Unit V's CF
Unit III (Community Detection)
└─> communities feed into Unit V's
social-context recommendation
Unit IV (Diffusion, Influence/Homophily)
└─> cascades explain Unit V's
collective behavior / viral recommendation
spread
Unit V (Recommendation, Behavior)
└─> ties all previous units together
into an applied system