SOCIAL NETWORK ANALYSIS(BAD714D)

MODULE 3
LINK ANALYSIS
WHAT IS LINK ANALYSIS?
Link analysis is about studying the connections (links) between things (called nodes) in a
network — for example, people in a social network, websites on the Internet, or computers in
a system.
These links can be:
• Directed (A → B) or Undirected (A ↔ B)
• Weighted (some links are stronger than others) or Unweighted
• Signed (positive or negative relationship)
APPLICATIONS OF LINK ANALYSIS
1. Entity Ranking
o Used to find relevant or similar matches for a given input pattern across large
sets of information.
o Can range from simple hyperlink-based ranking to complex similarity
measures (e.g., text, images, etc.).
o Also applied in computer networking, such as route balancing and caching.
2. Anomaly Detection
o Helps identify abnormal or unusual behaviour when expected link patterns
are missing or violated.
o Commonly used in criminal investigations and crime prevention.
o Also useful for predicting early disease outbreaks.
3. Mining New Patterns
o A by-product of link analysis that helps in discovering new and emerging
relationships.
o Can detect new web pages gaining attention (hyperlinked traction) but not yet
indexed.
o Useful for predicting new links or relations likely to form in a network.
4. Adversarial Attack
o Involves using link analysis to identify key nodes in a network.
o Targeting these important nodes can disrupt network operations — both
online and offline.

1
SOCIAL NETWORK ANALYSIS(BAD714D)

SIGNED NETWORKS
Introduction to Signed Networks
o Previous networks studied had directed/undirected and weighted/unweighted
edges.
o In real-world interactions, relationships often include like/dislike,
agree/disagree, or positive/negative opinions (e.g., YouTube likes/dislikes,
Reddit upvotes/downvotes, Amazon reviews).
o To represent such opinions, we use signed networks, where each edge has a
positive (+) or negative (−) sign (and may also include direction and weight).
o This shows how positive and negative relationships coexist in a network.

Balance theory of undirected signed networks

Basic Concept
o Consider two nodes A and B with a signed edge:
▪ (A,B,+) → friendship
▪ (A,B,−) → enmity
o With just two nodes, either relation is balanced.
o When a third node (C) is added, forming a triad (A, B, C), balance may not
always hold.

2
SOCIAL NETWORK ANALYSIS(BAD714D)

Types of Triads
o T0 (+ + +):
▪ Everyone is friends.
▪ Product of signs: +
▪ Stable (Balanced) — mutual trust and respect.
o T1 (− − +):
▪ Two friends share a common enemy.
▪ Product of signs: +
▪ Stable (Balanced) — trust forms from shared dislike of a third party.
o T2 (+ + −):
▪ Two friends have a mutual enemy among them.
▪ Product of signs: −
▪ Unstable (Unbalanced) — causes stress; may push one friend to take
sides or change alliances.
o T3 (− − −):
▪ Everyone dislikes everyone else.
▪ Product of signs: −
▪ Unstable (Unbalanced) — network breaks down unless two enemies
unite against a third, forming a balanced triad.
Condition for Balance
o A triad is balanced if the product of the signs of all edges is positive (T0,
T1).
o If the product is negative, it’s unbalanced (T2, T3).
o Balance theory predicts that balanced triads (stable relationships) are more
common in real networks.
o Unbalanced triads create tension, stress, or mistrust, so people naturally try
to avoid or fix them.
o As a result, in real life:
▪ Balanced triads (T0, T1) → over-represented.
▪ Unbalanced triads (T2, T3) → under-represented.

3
SOCIAL NETWORK ANALYSIS(BAD714D)

Status Theory of Signed Networks

o Status Theory interprets the edge sign as a measure of relative status or
prestige between two nodes.
o If A → B with a positive (+) link → A considers B higher in status than itself.
o If A → B with a negative (−) link → A considers B lower in status than itself.
Example
o User X follows both Y and Z.
o X → Y (+) → X believes Y is of higher status.
o X → Z (−) → X believes Z is of lower status.
o Therefore, the status order among the nodes is:
Y>X>Z
Two Node-Level Metrics
o Based on the signs a node generates or receives, we can define two measures:
▪ Generative Baseline (g):
Fraction of positive links generated by a node.
Number of positive links generated
𝑔=
Total links generated

▪ Receptive Baseline (r):

Fraction of positive links received by a node.
Number of positive links received
𝑟=
Total links received

4
SOCIAL NETWORK ANALYSIS(BAD714D)

Triad Balance vs. Status

• In a directed triad,
o A → B (+) means B > A
o B → C (+) means C > B
o So, by transitivity C > A
o Hence, when C → A, the link will be negative (−) based on Status Theory.
• But in Balance Theory (undirected),
o If (A, B, +) and (B, C, +)
o Then it predicts (C, A, +) — a positive and balanced triad.
• Conflict:
o Status Theory predicts C→A (−)
o Balance Theory predicts C–A (+)
o Thus, balance theory overestimates positive triplets.

STRONG AND WEAK TIES

o People form different kinds of relationships — some close (strong ties) and
some casual (weak ties).
o Strong ties = close friends or family → emotional support, trust.
o Weak ties = acquaintances → connect different social groups.
Granovetter’s Study (1973)
o Showed that weak ties are important for spreading new information across
groups.
o If A–B and A–C are strong ties, it’s likely B and C will also form a strong tie
— called triadic closure.

5
SOCIAL NETWORK ANALYSIS(BAD714D)

Strength of a Tie
o The strength of a tie measures how close or connected two people are in a
network.
o It depends on how many mutual friends (common neighbours) they share.
Mathematical Measure — Neighbourhood Overlap (NO)
∣ Γ(𝑥) ∩ Γ(𝑦) ∣
𝑁𝑂(𝑥, 𝑦) =
∣ Γ(𝑥) ∪ Γ(𝑦) ∣

o Γ(x): set of neighbours of node x.

o Numerator: common neighbours between x and y.
o Denominator: total unique neighbours of x and y.
o Higher NO → stronger tie.

let us calculate the neighbourhood overlap of (A,M) and (A,E)

6
SOCIAL NETWORK ANALYSIS(BAD714D)

Triadic Closure
o Simply put: “A friend of a friend tends to become a friend.”
o If nodes B and C are not connected but both are friends with A, there’s a high
chance that B and C will become friends later.
o This process is known as triadic closure.
Example
o At time t₀: x and y are not connected, but both know z.
o After some time (Δt): x and y meet through z.
o At time t₁ = t₀ + Δt: x and y become friends → forming a closed triad.\

Reasons for Triadic Closure

o Opportunity: Mutual friend (z) gives x and y a chance to meet.
o Trust: If x trusts z and z trusts y, x is likely to trust y too.
o Incentive: z benefits by connecting its friends, improving cooperation and
harmony.
Measuring Triadic Closure – Clustering Coefficient
o The clustering coefficient (CC) of node z measures how many of its friends
are also friends with each other.
o Formula:
∑𝑖,𝑗∈Γ(𝑧) 𝐼[(𝑖, 𝑗) ∈ 𝐸]
𝐶𝐶𝑧 =
𝑘𝑧 (𝑘𝑧 − 1)/2

▪ kₓ: degree of node z (number of neighbours).

▪ Γ(z): set of z’s neighbours.

▪ I[(i,j) ∈ E]: 1 if i and j are connected, 0 if not.

▪ Range: 0 → none of z’s friends are connected; 1 → all are connected.

7
SOCIAL NETWORK ANALYSIS(BAD714D)

Example
o For node A:
▪ Γ(A) = {B, C, D, E, M}, kₐ = 5
▪ Existing links: (B,C), (B,D), (C,D), (D,E)
4
𝐶𝐶𝐴 = = 0.4
(5 × 4)/2

▪ → 40% chance that B and M will form a new link (triadic closure).
Dunbar Number
o Proposed by Robin Dunbar (1992), the Dunbar Number explains the limit to
how many close relationships a person can maintain.
o The Dunbar Number ranges between 100 and 250,
and is generally taken as 150.
o This means a person can maintain close, meaningful ties with about 150
people at a time.
Local Bridges and Importance of Weak Ties
Local Bridge

An edge ⟨i, j⟩ is a local bridge if removing it means no direct link remains between the
neighbours of i and j.
• In simple terms, i and j have no mutual friends.
• Mathematically,

𝑁𝑂(𝑖, 𝑗) = 0

⇒ The edge is a local bridge.

• Local bridges are not part of any triad.

• Example: In Figure 4.5, edge ⟨A, M⟩ has NO(A, M) = 0, hence it’s a weak tie and a
local bridge.

Relationship Between Local Bridges and Weak Ties

• Weak ties often act as local bridges, connecting different parts of a network.
• They carry information between groups that otherwise wouldn’t interact.
• Hence, local bridges = weak ties in most real-world cases.

8
SOCIAL NETWORK ANALYSIS(BAD714D)

Importance of Weak Ties (Granovetter, 1973)

• Information Flow:
o Strong ties share similar information (within a group).
o Weak ties bring new and diverse information from outside groups.
• Example:
o When searching for a new job, acquaintances (weak ties) are more helpful than
close friends — they have access to different opportunities.
• Opportunities:
o Weak ties provide access to new ideas, jobs, and groups.
• Conflict Resolution:
o Weak ties act as mediators between different communities, promoting
understanding.
• Adversarial Impact:
o Removing weak ties (local bridges) can lead to echo chambers and spread of
misinformation.
o In contrast, during disease outbreaks, they can spread infections between
groups.

Edge Embeddedness

• Embeddedness(⟨x, y⟩) = |Γ(x) ∩ Γ(y)|

→ Number of mutual friends between nodes x and y.
• A local bridge has embeddedness = 0.
• Nodes with low embeddedness are more exposed (fewer common friends) but have
access to unique information across multiple groups.

LINK ANALYSIS ALGORITHMS

• Used to rank nodes/web pages and measure similarity between entities.

• Key algorithms: PageRank, DivRank, SimRank, PathSim.
• PageRank & DivRank are not incremental — any network change needs full
recalculation.
• Bahmani et al. (2010) proposed a fast incremental PageRank to fix this.
• Many improved variants were later developed for better accuracy and efficiency.

9
SOCIAL NETWORK ANALYSIS(BAD714D)

PAGERANK
o PageRank was created by Google’s founders (Page et al., 1999) to rank web
pages by importance.
o Idea: A node’s importance depends on how many important nodes link to it.
Intuition
o Every link from one page to another passes on a part of its importance (rank).
o Incoming links (in-edges) from important pages make a page more important.
o Outgoing links (out-edges) distribute a page’s importance to others.
Example
o Blog 1 links to Blog 2 → Blog 2 gains some importance.
o Blog 2 links back to Blog 1 → Blog 1 gains importance too.
o For a node w:
𝑅(𝑏)
𝑅(𝑤) = ∑
𝑁𝑏
𝑏∈𝐵𝑤

▪ Bw: set of nodes linking to w (backward links).

▪ Nb: number of forward links from node b.
Special Case
o If no links exist, all pages have equal rank:
1
𝑅(𝑝) =
Total number of pages

10
SOCIAL NETWORK ANALYSIS(BAD714D)

Random Walk
o Imagine a random surfer who starts at a web page and keeps clicking on links
to move to new pages.
o If the surfer reaches a dead-end (no links), they jump randomly to any page
on the web.
Two Actions at Each Step
o With probability α, the surfer jumps randomly to any page
1
→ 𝐸 = , where N = total number of pages.
𝑁

o With probability (1 − α), the surfer follows the available hyperlinks.

Intuition
o Pages that are visited more often during random walks are considered more
important.
o So, PageRank represents the probability of a page being visited.

11
SOCIAL NETWORK ANALYSIS(BAD714D)

𝑅(𝑏) 1
𝑅(𝑤) = (1 − 𝛼) ∑ +𝛼
𝑁𝑏 𝑁
𝑏∈𝐵𝑤

o Bw = pages linking to w
o Nb = number of outgoing links from b
o α = damping factor (chance of random jump, usually 0.15)
o ΣR(i) = 1 (total probability = 1)
Why Random Jump Helps
o Prevents the surfer from:
▪ Getting stuck at dead-ends (pages with no links).
▪ Getting trapped in loops (A ↔ B links only) — known as a spider trap.
Matrix Manipulation and Convergence of PageRank
PageRank Vector
o For N web pages, PageRank is represented as

𝑅 = ⟨𝑟1 , 𝑟2 , . . . , 𝑟𝑛 ⟩

where 0 ≤ 𝑟𝑖 ≤ 1and initially

1
𝑅0 =
𝑁
for all pages (equal rank at the start).
Adjacency Matrix (A)
o The web links are stored in a directed adjacency matrix A:

▪ 𝐴𝑖𝑗 = 1→ if page i links to j

▪ 𝐴𝑖𝑗 = 0→ otherwise

o To account for multiple links, it’s normalized:

1
𝐴𝑖𝑗 =
𝑁𝑖

where 𝑁𝑖 = number of outgoing links from page i.

o This makes A a stochastic matrix (each row sums to 1).

12
SOCIAL NETWORK ANALYSIS(BAD714D)

Iterative Rank Update

o Initial rank: 𝑅0
o Updated each step as:

𝑅𝑖+1 = 𝑅𝑖 𝐴

o To include random jumps (like the random surfer model):

𝑅𝑖+1 = (1 − 𝛼)𝑅𝑖 𝐴 + 𝛼𝐸

where
1 1 1
▪ 𝐸 = ⟨𝑁 , 𝑁 , . . . , 𝑁⟩(uniform jump probability)

▪ 𝛼= probability of random jump

▪ 𝑑 = 1 − 𝛼= damping factor

Damping Factor
o Typically d = 0.85, meaning:
▪ 85% of the time → surfer follows links.
▪ 15% of the time → surfer jumps randomly
o The process repeats until ranks stop changing significantly:

∣ 𝑅𝑖+1 − 𝑅𝑖 ∣≤ 𝜖

where ε is a small tolerance value for precision.

o When this condition is met → PageRank has converged (stable importance
scores).

13
SOCIAL NETWORK ANALYSIS(BAD714D)

14
SOCIAL NETWORK ANALYSIS(BAD714D)

PERSONALISED PAGERANK
o Normal PageRank uses a uniform random jump (equal chance to visit any
page).
o Personalised PageRank skews this randomness towards specific pages — e.g.,
pages a user visits often or finds relevant.
o It creates customized rankings based on user preferences or topics.

How It Works
o The random jump vector (E) is adjusted:

▪ For one preferred page: 𝑒𝑙 = 1, all others = 0.

▪ For a set of preferred pages (S or Sw): weights are higher for those
pages.
o Modified formula:
𝑅(𝑏)
𝑅(𝑤) = (1 − 𝛼) ∑ + 𝛼𝐸(𝑆𝑤 )
𝑁𝑏
𝑏∈𝐵𝑤

o Used in systems like topic-sensitive or user-personalized search engines.

o Supported in tools like NetworkX (Python).

Time Homogeneous Random Walks & Stationary Distribution

Time-Homogeneous Random Walks
o Transition probabilities (links between pages) stay constant over time.
o Represented as a Markov chain, where each page is a state, and links are
transitions.
Transition Probability
𝑤(𝑢, 𝑣)
𝑝0 (𝑢, 𝑣) = (1 − 𝑑)𝑝∗ (𝑣) + 𝑑
∑𝑏∈𝐹𝑢 𝑤(𝑢, 𝑏)

o 𝑑: damping factor

o 𝑝∗ (𝑣): prior/random jump probability (personalised or uniform)

o The Markov chain reaches a stationary distribution (π) where

15
SOCIAL NETWORK ANALYSIS(BAD714D)

𝑝𝑇+1 (𝑣) ≈ 𝑝𝑇 (𝑣)

o This π(v) gives the final PageRank score — i.e., the long-term probability of
visiting each page.
Advantages of PageRank

• Fast computation (vectorized equations).

• Guaranteed convergence to a unique solution.
• Pre-computable ranks (independent of queries).
• Stable and robust (harder to manipulate in-links).
• Real-world relevance — mirrors influence spread (e.g., social or sports rankings).

Disadvantages of PageRank

• Ignores page content — can be spam-prone.

• A page can gain rank by linking to many trivial pages or buying links.
• Static system — any change in network requires full recomputation.

DIVRANK
• PageRank ranks pages based on popularity (prestige) — but often top results are too
similar (lack diversity).
• DivRank (Diverse Rank) solves this by combining prestige + diversity.
• It introduces competition between nodes — ensuring that top-ranked nodes are
important but from different groups/topics.

16
SOCIAL NETWORK ANALYSIS(BAD714D)

Vertex-Reinforced Random Walks (VRRW)

• In real-world systems, popular nodes become even more popular over time.
• VRRW updates the transition probabilities dynamically based on how often a node
is visited.
• So,

𝑝𝑇 (𝑢, 𝑣) ∝ 𝑝0 (𝑢, 𝑣) × 𝑁𝑇 (𝑣)

o 𝑁𝑇 (𝑣): number of visits to node v up to time T.

• This makes the random walk time-variant — probabilities evolve as nodes gain more
visits.

DivRank Random Walk Formula

1. Base probability:
𝑤(𝑢, 𝑣)
𝛼 𝑢≠𝑣
𝑝0 (𝑢, 𝑣) = { ∑𝑏∈𝐹𝑢 𝑤(𝑢, 𝑏)
1−𝛼 𝑢=𝑣

o 𝛼: probability of moving to a neighbor;

o 1 − 𝛼: probability of staying on the same node (self-loop).

2. Time-varying transition:
𝑝0 (𝑢, 𝑣) 𝑁𝑇 (𝑣)
𝑝𝑇 (𝑢, 𝑣) = (1 − 𝑑)𝑝∗ (𝑣) + 𝑑
∑𝑏∈𝐹𝑢 𝑝0 (𝑢, 𝑏) 𝑁𝑇 (𝑏)

3. Updated probability for node v at next step:

𝑝0 (𝑢, 𝑣) 𝑁𝑇 (𝑣)
𝑝𝑇+1 (𝑣) = (1 − 𝑑)𝑝∗ (𝑣) + ∑ 𝑑 𝑝𝑇 (𝑢)
∑𝑏∈𝐹𝑢 𝑝0 (𝑢, 𝑏) 𝑁𝑇 (𝑏)
𝑢∈𝐵𝑣

SIMRANK
• SimRank (Jeh & Widom, 2002) measures similarity between two nodes based on
network structure — not content or domain data.
• Idea: “Two nodes are similar if they are linked to by similar nodes.”
• It’s domain-independent and works purely on the graph topology.

17
SOCIAL NETWORK ANALYSIS(BAD714D)

How It Works
• Uses shared relationships to calculate similarity.
• For every pair of nodes (u, v), SimRank gives a score based on how their neighbours
(or citations) overlap directly or indirectly.
• Produces n² similarity scores for a network of n nodes (unlike PageRank, which gives
one score per node).

Example
• In a citation network:
o Papers P3 and P4 are similar because both are cited by P5.
o Papers P2 and P7 are similar because both are cited by P8.
o Papers P1 and P2 don’t share direct citations, but may be indirectly similar
through common intermediates (like P3, P4, or P8).
• SimRank captures this indirect similarity, unlike simple neighborhood overlap.

• SimRank measures how similar two nodes (a, b) are based on their in-neighbours.
• The key idea: “Two nodes are similar if their in-neighbours are similar.”

Notation

• 𝐼(𝑣): Set of in-neighbours of node v (nodes linking to v).

• 𝑂(𝑣): Set of out-neighbours of node v (nodes v links to).

• 𝑠(𝑎, 𝑏): Similarity score between nodes a and b, ranging from 0 to 1.

18
SOCIAL NETWORK ANALYSIS(BAD714D)

Formula
1, if 𝑎 = 𝑏
0, if 𝐼(𝑎) = ∅ or 𝐼(𝑏) = ∅
𝑠(𝑎, 𝑏) = { 𝐶 ∣𝐼(𝑎)∣ ∣𝐼(𝑏)∣
∑ ∑ 𝑠(𝐼𝑖 (𝑎), 𝐼𝑗 (𝑏)), otherwise
∣ 𝐼(𝑎) ∣∣ 𝐼(𝑏) ∣ 𝑖=1 𝑗=1

• C = decay factor (0 < C < 1), controls how quickly similarity weakens with distance.
• The formula averages similarities between the in-neighbours of a and b, adjusted by
C.
Intuition

• 𝑠(𝑤, 𝑤) = 1: A node is fully similar to itself.

• If u and v are referred by w, then

𝑠(𝑢, 𝑣) = 𝐶 ⋅ 𝑠(𝑤, 𝑤)

• If they are 2 hops away:

𝑠(𝑝1 , 𝑝2 ) = 𝐶 2 ⋅ 𝑠(𝑤, 𝑤)

• So, similarity decreases with network distance — the farther apart two nodes are, the
less similar they become.

19
SOCIAL NETWORK ANALYSIS(BAD714D)

Naive Solution to SimRank

• For a network with n nodes, SimRank maintains n² similarity scores 𝑅𝑘 (𝑎, 𝑏).
Iteration process:
o Start with:
1, if 𝑎 = 𝑏
𝑅0 (𝑎, 𝑏) = {
0, if 𝑎 ≠ 𝑏

o Update at each step:

𝐶
𝑅𝑘+1 (𝑎, 𝑏) = ∑ ∑ 𝑅𝑘 (𝐼𝑖 (𝑎), 𝐼𝑗 (𝑏))
∣ 𝐼(𝑎) ∣∣ 𝐼(𝑏) ∣
𝑖 𝑗

• As 𝑘 → ∞, 𝑅𝑘 (𝑎, 𝑏)→ SimRank similarity 𝑠(𝑎, 𝑏).

• The metric is monotonically increasing:

0 ≤ 𝑅𝑘 (𝑎, 𝑏) ≤ 𝑅𝑘+1 (𝑎, 𝑏) ≤ 1

• Scores propagate along edges until convergence.

SimRank in Heterogeneous Bipartite Networks

• Applied to two object types (e.g., users and products).
• Two users are similar if they buy similar products.
• Two products are similar if they are bought by similar users.
• The relationships are mutually reinforced.
Formulas
• User similarity:
𝐶1
𝑠(𝑢1 , 𝑢2 ) = ∑ ∑ 𝑠(𝑂𝑖 (𝑢1 ), 𝑂𝑗 (𝑢2 ))
∣ 𝑂(𝑢1 ) ∣∣ 𝑂(𝑢2 ) ∣
𝑖 𝑗

• Product similarity:
𝐶2
𝑠(𝑝1 , 𝑝2 ) = ∑ ∑ 𝑠(𝐼𝑖 (𝑝1 ), 𝐼𝑗 (𝑝2 ))
∣ 𝐼(𝑝1 ) ∣∣ 𝐼(𝑝2 ) ∣
𝑖 𝑗

20
SOCIAL NETWORK ANALYSIS(BAD714D)

21
SOCIAL NETWORK ANALYSIS(BAD714D)

PATHSIM
• Proposed by Sun et al. (2011) for measuring semantic similarity in heterogeneous
information networks.
• Unlike PageRank or SimRank (which ignore types), PathSim considers types of nodes
and relationships.
• It captures how semantically related two entities are based on path patterns (meta-
paths).
Introduction to Heterogeneous Network
A heterogeneous network has multiple types of:
• Nodes (entities)
• Edges (relations)
Formally, it’s defined as:

𝐺 = (𝑉, 𝐸, 𝐴, 𝑅, 𝜙, 𝜓)
Where:
• V: nodes
• E: edges
• A: node types
• R: edge types
• φ(v): maps a node to its type
• ψ(e): maps an edge to its relation type

Types of Heterogeneous Networks

Case 1: |A| > 1 and |R| = 1
o Multiple node types, single relation type.
o Example: Users → Products (buy relationship).
o E.g., U1 → {I1, I2, I3}

22
SOCIAL NETWORK ANALYSIS(BAD714D)

Case 2: |A| = 1 and |R| > 1

o Single node type, multiple relation types.
o Example: Professors network
▪ Relations: same department, co-author.
▪ Different edges represent different relationships between same-type
nodes.
Example : Professors Network
• The network consists of teachers (T1, T2, …) connected bi-directionally, meaning
relationships are symmetric.
• T2 and T5 are co-authors, but not from the same department.
• T2 and T1 are from the same department, but have not collaborated.
• T3 and T4 are both from the same department and co-authors.
• This shows that nodes of the same type (teachers) can be connected through different
types of relationships, such as co-author and same department.

Case 3: |A| > 1 and |R| > 1

o Multiple node types and relation types.
o Example: Bibliographic network
▪ Node types: papers, authors, venues, keywords
▪ Relations: author–paper, paper–venue, paper–term, co-author, etc.
o Enables identifying semantic similarities like “authors working in the same
field” or “papers with similar keywords.”

23
SOCIAL NETWORK ANALYSIS(BAD714D)

Example : Bibliography Network

• The network includes different node types:
o Papers (Pᵢ)
o Authors (Aᵢ)
o Venues (Vᵢ)
o Keywords (Tᵢ)
• Connections:
o A₂ and A₃ co-authored paper P₃ → they are linked as co-authors.
o A₁ and A₂ are not directly linked, but both published their papers (P₁ and P₂)
at the same venue (V₁) → indirectly related through “PublishedAt” links.
o Each paper is also linked to several keywords (T₁, T₂, T₃), which may appear
in other papers → helps identify similar papers.
• Bidirectional Relationships:
o For every directed edge (e.g., A₁ → P₁, meaning “Author A₁ writes Paper P₁”),
there is an implicit reverse edge (P₁ → A₁, meaning “Paper P₁ written by
Author A₁”**).
o This ensures semantic completeness in the heterogeneous network.
Network Schema and Meta-Paths

Network Schema

• A network schema (TG) gives a meta-level (schema-level) overview of a

heterogeneous network.
• It summarizes:
o A → different types of nodes (objects)
o R → different types of edges (relations)
• Defined as:
TG = (A, R)
where
o ϕ : V → A → maps nodes to their types
o ψ : E → R → maps edges to their relation types
• It is similar to an Entity–Relationship (ER) diagram in databases — showing what
entity types exist and how they connect.

24
SOCIAL NETWORK ANALYSIS(BAD714D)

Meta-Paths
• A meta-path is a schema-level sequence of node and edge types that shows how
entities are connected.
• It represents different semantic relationships between nodes.
• Example (in a bibliographic network):
o Author–Paper–Author (A–P–A): co-authorship path
o Author–Paper–Paper–Author (A–P–P–A): citation-based relationship
• Each meta-path captures different meanings or similarities among entities (like co-
author similarity vs citation similarity).

25
SOCIAL NETWORK ANALYSIS(BAD714D)

Heuristic Measures of Object Similarity via Meta-Path

1. Path Count

• Counts the number of path instances connecting objects 𝑥and 𝑦via meta-path 𝑃𝑙 .
• Formula:
𝑠(𝑥, 𝑦) =∣ {𝑝 ∈ 𝑃𝑙 ∣ 𝑥 ∈ 𝐴1 , 𝑦 ∈ 𝐴𝑙+1 } ∣
• Meaning: More paths = higher similarity.

2. Random Walk

• Measures the probability that a random walker starting at 𝑥following path 𝑃𝑙 ends at 𝑦.
• Formula:
𝑠(𝑥, 𝑦) = ∑ 𝑃𝑟𝑜𝑏(𝑝)
𝑝∈𝑃𝑙

• Only valid if: 𝑥 ∈ 𝐴1 and 𝑦 ∈ 𝐴𝑙+1.

3. Pairwise Random Walk

• Considers two walkers, one from 𝑥and one from 𝑦, meeting at a mid-point node 𝑧.
• Formula:
𝑠(𝑥, 𝑦 ∣ 𝑧) = ∑ 𝑃𝑟𝑜𝑏(𝑝1 ) × 𝑃𝑟𝑜𝑏(𝑝2− )
(𝑝1 ,𝑝2− )

• Uses reverse path 𝑃2− to form (𝑥 → 𝑧 ← 𝑦).

Formulation of PathSim

PathSim essentials

• Round-trip meta-path: 𝑃 = (𝑃ℓ , 𝑃ℓ− )starts and ends at the same type (e.g., Author–
Venue–Author).

26
SOCIAL NETWORK ANALYSIS(BAD714D)

• Why PathSim? Path count / random walk can bias toward high-degree nodes; PathSim
balances connectivity with visibility.
Core formula (symmetric similarity)
2 ∣ {𝑝𝑥⇝𝑦 ∈ 𝑃} ∣
𝑠(𝑥, 𝑦) =
∣ {𝑝𝑥⇝𝑥 ∈ 𝑃} ∣ +∣ {𝑝𝑦⇝𝑦 ∈ 𝑃} ∣

• Numerator = Connectivity 𝐶𝑝 (𝑥, 𝑦)(how many 𝑥 ⁣ → ⁣𝑦path instances under

meta-path 𝑃)

• Denominator = Visibility 𝑉𝑝 (𝑥) + 𝑉𝑝 (𝑦)(round-trip counts at 𝑥and 𝑦)

Properties

• Symmetric: 𝑠(𝑥, 𝑦) = 𝑠(𝑦, 𝑥)

• Normalized: 𝑠(𝑥, 𝑦) ∈ [0,1]

• Self-maximized: 𝑠(𝑥, 𝑥) = 1

Example (AVA: Author–Venue–Author)

Given publishing frequencies (W_{AV})

Author MOD VLDB ICDE KDD

Mike 2 1 0 0

Jim 50 20 0 0

Mary 2 0 1 0

Bob 2 1 0 0

Ann 0 0 1 1

1) Visibility 𝑽𝒑 (round-trip counts per author)

Vp (Mike) = 2 × 2 + 1 × 1 + 0 × 0 + 0 × 0 = 5
Vp (Jim) = 50 × 50 + 20 × 20 + 0 × 0 + 0 × 0 = 2900
Vp (Mary) = 2 × 2 + 0 × 0 + 1 × 1 + 0 × 0 = 5
Vp (Bob) = 2 × 2 + 1 × 1 + 0 × 0 + 0 × 0 = 5
Vp (Ann) = 0 × 0 + 0 × 0 + 1 × 1 + 1 × 1 = 2

27
SOCIAL NETWORK ANALYSIS(BAD714D)

2) Connectivity 𝑪𝒑 (Mike,⋅)(sum over venues of forward×backward)

Cp (Mike, Jim) = 2 × 50 + 1 × 20 + 0 × 0 + 0 × 0 = 120

Cp(Mike, Mary) = 2 × 2 + 1 × 0 + 0 × 1 + 0 × 0 = 4
Cp(Mike, Bob) = 2 × 2 + 1 × 1 + 0 × 0 + 0 × 0 = 5
Cp(Mike, Ann) = 2 × 0 + 1 × 0 + 0 × 1 + 0 × 1 = 0
𝟐𝑪𝒑
3) PathSim scores 𝒔(Mike,⋅) = 𝑽
𝒑 (Mike)+𝑽𝒑 (⋅)

2⋅120
• 𝑠(Mike,Jim) = 5+2900 ≈ 𝟎. 𝟎𝟖𝟐𝟔
2⋅4
• 𝑠(Mike,Mary) = 5+5 = 𝟎. 𝟖
2⋅5
• 𝑠(Mike,Bob) = 5+5 = 𝟏. 𝟎
0
• 𝑠(Mike,Ann) = 5+2 = 𝟎

PathSim gives high similarity only when both authors share venues and have comparable
visibility.

28