Social Media

Analytics
Module 4
Link Analysis
Overview – Link Analysis

• Applications of Link Analysis,

• Signed Networks - Balance Theory of
Undirected Signed Networks, Status
Theory of Signed Networks, Triad
Balance vs Status,
• Strong and Weak Ties - Strength of a
Ties, Triadic Closure, Dunbar Number,
Local Bridges and Importance of
Weak Ties.
Link Analysis in Social Graphs & Its Applications
• Link analysis is the study of connections between entities (nodes) in a graph.
• It helps uncover hidden patterns, influential nodes, and relationships in a
social network.
• In social graphs (like Instagram, Facebook, LinkedIn, etc.), nodes represent
users, and edges represent relationships (friendships, follows, interactions).
• Link analysis helps us:
– Identify influencers in a network
– Detect communities & subgroups
– Predict new connections
– Identify spam or fake accounts
Method Purpose Example Application
Centrality Measures (Degree, Identifies key influential nodes Detecting opinion leaders on
Betweenness, etc.) Instagram
PageRank Ranks influential nodes Finding top influencers on
Twitter
HITS (Hubs & Authorities) Finds hubs & trusted sources Identifying experts on LinkedIn

Modularity Maximization Detects dense communities Finding niche groups on

Facebook
Link Partitioning Identifies overlapping groups Communities with shared
interests on Instagram
Common Neighbors Predicts future links Friend suggestions on LinkedIn

Adamic-Adar Index Weighs rare shared connections Twitter follow

recommendations
Preferential Attachment "Rich get richer" effect Growing followership of top
influencers
Network Densities Detects spam & fake accounts Identifying bot networks on
social media
Signed Networks
• In our discussion of networks thus far, we have generally viewed the
relationships contained in these networks as having positive
connotations
• links have typically indicated such things as friendship, collaboration,
sharing of information, or membership in a group.
• The terminology of on-line social networks reflects a largely similar view,
through its emphasis on the connections one forms with friends, fans,
followers, and so forth.
• But in most network settings, there are also negative effects at work.
• Some relations are friendly, but others are antagonistic or hostile
Motivation for Signed Social Networks & Link Analysis
• In traditional social networks (Facebook, Instagram, LinkedIn), connections are usually positive
(friendship, follows, likes).
• However, real-world relationships also include negative ties (dislikes, rivalries, conflicts).
• Signed networks represent both positive (+1) and negative (-1) relationships.
• Captures Real-World Social Dynamics
– Example: Twitter arguments, Reddit downvotes, YouTube dislikes.
• Improves Community Detection
– Positive & negative links influence group formation.
– Helps separate strongly connected allies vs. opposing factions.
• Better Link Prediction
– Instead of just predicting if a link will form, we can predict if it will be positive or negative.
– Example: Will two users on Twitter become friends or rivals?
• Detects Anomalies & Fake Engagement
– Signed networks help spot manipulative behaviors, like:
– Fake followers who never interact (neutral relationships).
– Coordinated dislike campaigns on YouTube.
Signed Networks
Direction of a link in a network captures the direction of
information flow across the link
Weight of a link in a network represents the strength of
influence of information passing through that link
Neither of the above express how the information is
perceived by the receiving node!
There often exist element pairs in perception/reaction
towards information content –
like/dislike (YouTube),
agree/disagree (Reddit),
Positive review/negative review (Amazon), etc.
Signed network captures the above opinion/relationship
dynamics across entities
Examples of Signed Networks
Platform Positive Links (+1) Negative Links (-1)
Blocks, report abuse,
Twitter Follows, retweets, likes
unfollows
Unfriends, group bans,
Facebook Friendships, group joins
reports
Follows, likes, story Unfollows, restricted
Instagram
reactions accounts
Downvotes, comment
Reddit Upvotes, awards, follows
removals
Dislikes (before removal),
YouTube Subscriptions, likes, shares
report content
Removing connections,
LinkedIn Connections, endorsements
reporting profiles
 Theories of Signed Networks
• When analyzing signed social networks, two major theories help us understand
– relationship stability
– polarization, and influence
• Balance Theory
• Explains how relationships evolve in social networks.
• Helps detect stable vs. unstable groups.
• Used in friend recommendation, conflict detection, and community formation.
• Core Idea
– People prefer balanced relationships (friend of a friend is a friend).
– Unbalanced structures cause tension and often change over time.
• Example in Social Graphs
– Twitter Politics: If two users oppose the same leader, they are more likely to follow each
other.
– Facebook Groups: Users with common interests form strong groups, avoiding those with
conflicting views.
 Status Theory
• Explains hierarchical relationships in networks.
• Helps in ranking influence, trust, and authority.
• Used in influencer detection, corporate networks, and online reputation analysis.
• Core Idea
– Social ties reflect status differences.
– Positive (+1): High-status endorses lower-status.
– Negative (-1): Lower-status challenges high-status.
• Example in Social Graphs
– LinkedIn Endorsements: High-ranking professionals endorse others, but lower-
status users may criticize them.
– Reddit Moderation: Senior moderators receive respect, while newcomers may
challenge them.
Signed Network in Twitter Political Discussions

•Green edges (+1): Represent

agreements (e.g., Amit agrees with
Priya, Amit supports Neha).
•Red edges (-1): Represent conflicts
(e.g., Priya blocks Ravi, Ravi criticizes
Amit).
This structure follows Balance Theory:
•Amit and Priya agree, and both
dislike Ravi, forming a stable
network.
•Neha supports Amit but argues
with Ravi, reinforcing social
divisions.
 Example: Signed Social Network on Instagram
Example Dataset (Friendships & Rivalries in an Instagram Influencer Circle)
• On Instagram, users can interact in different ways:
•Positive (+1) relationships: Following, liking posts, supporting in comments.
•Negative (-1) relationships: Blocking, reporting, leaving hate comments.
• This forms a signed social network with influencer rivalries and friendships.
•Aditi and Karan are friends and both dislike Rohan → Balanced structure.
•Sneha supports Aditi but argues with Rohan, leading to polarization.

User A User B Interaction Type Signed Edge

Aditi Karan Follows, likes posts +1
Karan Rohan Blocks, reports -1
Rohan Aditi Leaves negative comments -1
Aditi Sneha Collaborates on posts +1
Sneha Rohan Calls out Rohan’s content -1
•Green edges (+1): Positive
interactions (e.g., Aditi follows and
likes Karan, Aditi collaborates with
Sneha).
•Red edges (-1): Negative interactions
(e.g., Karan blocks Rohan, Rohan
criticizes Aditi, Sneha calls out Rohan).
This network shows influencer
rivalries and friendships, following
Balance Theory:
•Aditi and Karan are friends and
both dislike Rohan, forming a
stable structure.
•Sneha supports Aditi but
criticizes Rohan, reinforcing
polarization in the network.
Theories of signed networks: Balance

• Positive links represent friendship while negative links represent antagonism,

and an important problem in the study of social networks is to understand the
tension between these two forces.
• The notion of structural balance is one of the basic frameworks for doing this.
• The crucial idea is the following.
–If we look at any two people in the group in isolation, the edge between
them can be labeled + or −; that is, they are either friends or enemies.
–But when we look at sets of three people at a time, certain configurations of
+’s and −’s are socially and psychologically more plausible than others.
–In particular, there are four distinct ways (up to symmetry) to label the three
edges among three people with +’s and −’s;
 Balance Theory
Introduced as a theory of attitude change
by Fritz Heider in 1958
Popular as P-O-X model in psychology
Model states – an individual tends to
choose balance state in her interpersonal
relation
If the person perceive imbalance in his
relationship, will be motivated to correct
the imbalance somehow
Extension proposed by Frank Harary and
Dorwin Cartwright in social network
analysis
Balance Theory
1. Given a set of people A, B, and C, having three pluses among them is a very natural
situation: it corresponds to three people who are mutual friends.
2. Having a single plus and 2 minuses in the relations among the 3 people is also very
natural: it means that 2 of the 3 are friends, and they have a mutual enemy in the third.
3. The other two possible labelings of the triangle on A, B, and C introduce some amount
of psychological “stress” or “instability” into the relationships.
– A triangle with two pluses and one minus corresponds to a person A who is friends with
each of B and C, but B and C don’t get along with each other.
– In this type of situation, there would be implicit forces pushing A to try to get B and C to
become friends (thus turning the B-C edge label to +); or else for A to side with one of B
or C against the other (turning one of the edge labels out of A to a −).
4. Similarly, there are sources of instability in a configuration where each of A, B, and C are
mutual enemies .
In this case, there would be forces motivating two of the three people to “team up”
against the third (turning one of the three edge labels to a +).
 3+ 2 +, 1 -

A is friend with B and C, but B and C do not get well together

Mutual friends

1 +, 2 - 3-

Are there all

equally possible?

A and B are friends with a mutual enemy Mutual enemies

 Structural Balance
3+ 2 +, 1 -
Stable or Unstable
balanced

A is friend with B and C, but B and C do not get well together

Mutual friends Implicit force to make B and C friends (- => +) or turn one of the + to -
“the friend of my friend is my friend”
1 +, 2 - 3-
Stable or
balanced Unstable

A and B are friends with a mutual enemy Mutual enemies

“the enemy of my enemy is my friend” Forces to team up against the third (turn one of the – to +)
 Theory of Structural Balance
• Triangles with one or three +’s are called balanced, since they are free of instability, and
triangles with zero or two +’s as unbalanced.
• The argument of structural balance is that because unbalanced triangles are sources of
stress or some distress, people strive to minimize them in their personal relationships,
and hence they will be less abundant in real social settings than balanced triangles.
• Balanced triangles with three positive edges exemplify the principle that
– “the friend of my friend is my friend,”
• whereas those with one positive and two negative edges capture the notions that
– “the friend of my enemy is my enemy,”
– “the enemy of my friend is my enemy,”
– “the enemy of my enemy is my friend.”
 Balance state occurs in triads when all sign
multiplication of its sentiment relation
Balance Theory: Triads charges positive
Three Positive links
mutual trust and respect
Stable
Two negative, one positive
trust between friends established based
on distrust towards a common enemy
Stable
Two positive, one negative
 mutual friends would be under stress to
take sides
Unstable
Three negative links
No mutual trust
Positive = Friendship, Negative = Enmity Unstable and likely to be disintegrated
 Structural Balance
A labeled complete graph is balanced if every one of its triangles is balanced

local property,
individual triangles

Structural Balance Property: For every set of three nodes, if we consider the three
edges connecting them, either all three of these are labeled +, or else exactly one of
them is labeled +, ie odd number of +
Key Applications In Different Platforms:
Platform Structural Balance Example
Mutual friends tend to dislike the same person;
Facebook Friendships and conflicts
friend groups split if conflicts arise.
Two influencers supporting each other may block a
Instagram Influencer alliances and rivalries
common competitor, reinforcing network balance.
Users retweet people with shared views and
Twitter Political and opinion polarization block/report opposing voices, forming echo
chambers.
Professional connections and If two professionals endorse each other, they are
LinkedIn
corporate rivalries unlikely to connect with a shared rival.
Community-based upvotes and Users in strongly polarized subreddits (e.g., gaming
Reddit
bans vs. anti-gaming) reinforce group identity.
Developers contributing to a project are likely to
Open-source project
GitHub collaborate with common peers but avoid rival
collaborations
projects.
Case Study: Political Polarization on Twitter

• On Twitter, users often form echo chambers, reinforcing structural

balance theory:
–Users follow and retweet those who share their political beliefs (+1
edges).
–They block, report, or argue with opposing viewpoints (-1 edges).
–If two users agree with the same person but dislike a third user,
balance theory holds.
–If a user follows both sides, they face pressure to pick one side, leading
to network polarization.
 Structural Balance Theory in Action
1. Balanced Triad: Amit and Priya are
friends and both dislike Rohan,
forming a stable structure.
2. Unstable Relationship: If Amit remains
neutral about Rohan, he may feel
pressure to take sides.
3. Network Polarization: Over time, users
cluster into like-minded groups,
reducing cross-ideological discussion.

• Green edges (+1) for agreement (e.g., retweets, follows).

• Positive interactions (e.g., Amit supports Priya and Sneha).
• Red edges (-1) for conflict (e.g., blocks, arguments).
• Negative interactions (e.g., Priya blocks Rohan, Rohan argues with
Amit, Sneha criticizes Rohan).
 How Balance Leads to Polarization
Phase Network Change Outcome
Users have mixed connections
Initial Diverse opinions in network
(some positive, some negative)
Users adjust relationships to
Pressure to Balance Fewer neutral opinions
match their friends
Like-minded users cluster
Group Formation Formation of echo chambers
together
Opposing groups become Reduced dialogue, increased
Polarization
disconnected conflicts

Practical Applications
•Detecting online polarization using graph algorithms.
•Breaking echo chambers through recommendation diversity.
•Understanding influence networks in social platforms.
Signed Networks: Status Theory
 Balance theory views signed links as model of likes and dislikes
 a signed link from can have other possible interpretation!
X  Interpretation of link-sign as an indicator of relative status/prestige of a
node with respect to the other
+ -  Status Theory
 Assumes a signed, directed network of the entities
 𝐴 initiates a positive link to 𝐵 ⟹ 𝐴 considers 𝐵 to have a higher status than
Y Z itself
 𝐴 initiates a negative link to 𝐵 ⟹ 𝐴 considers 𝐵 to have a lower status than
itself
𝑌>𝑋>𝑍 • Example:
Status relative to X – Student → Professor (+) → The student acknowledges the professor’s
authority.
– Rival CEO → Competitor CEO (-) → The rival dismisses the competitor’s
influence.
Theory of Status
• Considers directed networks of signed links
• Positive cycles are directed triads with positive A
links from A to B to C back to A

B C
Creator views recipient as having higher status

Creator views recipient as having lower status

Note:
The sign of a link from A to B is generated by A
 A Theory Of Status - Directed Networks
A positive edge (A, B) means A
A negative edge
A
that A regards B as having (A, B) means that
higher status than A - A regards B as
+ having lower
B status than A
B

Assuming that all participants A

agree on status ordering, status -
theory predicts that when the +
direction of an edge is flipped,
B
its sign should flip as well.
 A Theory Of Status
• For any edge (𝒖, 𝒗), and any third node 𝒘, if it
possible to assign distinct numerical “status
values” to 𝑢, 𝑣, and 𝑤 in such a way that:
• the positive edges among them (if any) go from
nodes of lower status to nodes of higher status,
and the negative edges among them (if any) go
from nodes of higher status to nodes of lower
status.
• Three nodes u, v, and w are status-consistent if
this condition holds. – Local Property
• Let 𝐺 be a signed, directed graph & suppose that
all sets of three nodes in 𝐺 are status-consistent.
• Then if it is possible to order the nodes of 𝐺 as
𝑣1, 𝑣2, . . . , 𝑣𝑛 in such a way that each positive edge
(𝑣𝑖, 𝑣𝑗) satisfies 𝑖 < 𝑗, and each negative edge
(𝑣𝑖, 𝑣𝑗 ) satisfies 𝑖 > 𝑗. - Global Property
Balance vs. Status

? Since C is a friend of A’s friend

B, the link should be
B C

Since A regards B as having higher status, B

?
and B regards C as having higher status,
C should regard A has having lower status
and the link should be A
Comparison: Balance Theory and Status Theory
Theory of status makes sense for directed networks
only A

Theory of balance, though originated for undirected + +

A graphs, are also applicable for directed graphs
In directed network 𝐺, if C forms a link to A, which B C
+ ? +
link-sign is most likely to occur for that link?
According to theory of balance, link CA is predicted Balance Theory
B + C to be a positive link A
G According to theory of status, link CA is predicted to
be a negative link!
+ -
The two theories may infer conflicting predictions, as B C
+
they have different interpretations altogether
Status Theory
Signed Networks: Status Theory
• Node-level metrics defined in this connection:
– Generative Baseline (g): The fraction of positive signs
- generated by a node
A
+ – Receptive Baseline (r): The fraction of positive signs
received by a node
+ + • Scores for generative baselines of the nodes of the signed
graph beside are as follows:
B C -
- 1
– 𝐴𝑔 = = 1,
0
𝐵𝑔 = = 0,
1
𝐶𝑔 = =1
- - 1 2 1
• Scores for receptive baselines of the nodes of the signed
graph beside are as follows:
Snapshot of a signed graph
2 1 0
– 𝐴𝑟 = = 0.67, 𝐵𝑟 = = 1, 𝐶𝑔 = = 0
3 1 3
Status Theory: Motivating Example

• Ask Coder A about another employee Coder B: “A, how do you think the skill of
Coder B compares to your own?”
• Suppose all employees agree on ranking by skill (status)
• Produce signed directed graph
– Nodes: Coders
– Directed edges: from A to B if we asked A for her opinion of B
• Positive link: A thinks highly of B’s skill relative to her own
• Negative link: A thinks she is better than B

• Can use network context to make inferences about the signs of links we haven’t
yet observed
Status Theory: Motivating Example
• Suppose A and B have each received a positive evaluation from a third employee X
– Since B has been positively evaluated by another team member, B is more likely to
have above-average skill
• So, the evaluation that A gives B should be more likely to be positive than an
evaluation given by A to a random team member
– Since A has been positively evaluated by another team member, A is more likely to
have above-average skill
• So, the evaluation that A gives B should be less likely to be positive than an
evaluation received by B from a random team member

• Context causes the sign of the A-B link to deviate from the random baseline in
different directions depending on point of view
 Status Theory: Contextualized Links
• For a type t of c-link, look at the set of all
c-links of this type B
– Generative Baseline for type t
• Sum of the generative baselines for all nodes
Ai A X
– Generative Surprise sg(t)
• Signed number of standard deviations by
which the actual number of positive Ai-Bi
edges differs from the expectation
Triple (A, B; X) with the property that a
– Receptive Baseline for type t link forms from A to B after each of A and
• Sum of the receptive baselines for all nodes Bi
B already has a link either to or from X
– Receptive Surprise sr(t)
• Signed number of standard deviations of
difference
Status Theory: Contextualized Links
Status Theory: Role of Status

• Assign status values to c-links

– Assign node X status 0
– If X links positively to A, or if A links negatively to X
• Assign node A status 1
– Otherwise, assign node A status -1
– If X links positively to B, or if B links negatively to X
• Assign node A status 1
– Otherwise, assign node B status -1

interaction between A's generative characteristics and B's receptive

characteristics plays a pivotal role in determining the sign of the new edge.
Status Theory
• Now, for a particular type of c-link, we look at the set of all c-links (A,B;X)
of this type, and ask: what fraction of the links from A to B in this set are
positive?
• Moreover, how does this fraction compare to what one would expect
from the generative baselines of the nodes A and the receptive baselines
of the nodes B that are involved in the creation of these A-B links?
• If we can quantify the answer to this question in our data, we can look for
effects like we saw in our motivating example—
• In the case of positive links from X to A and B,
–the likelihood of a positive A-B edge should exceed the generative
baseline of A but should lie below the receptive baseline of B.
Theory Evaluation
• Generative surprise for type t is

if it has the same sign as B’s status

• Receptive surprise for type t is

if it has the opposite sign as A’s status

 Generative surprise for type t is

if it has the same sign as the edge predicted by balance

 Receptive surprise for type t is

if it has the same sign as the edge predicted by balance

Tie Strength
• The type of relationships between people depends on many
things like their history and similarity, each person's personal
background and preferences, environmental factors, and more.
• Relationships are also multifaceted, and many relationship
types can be used in social network analysis.
• One of the most useful is the idea of tie strength.
• Tie strength is a measure of the strength of a relationship
between people.
• Appear generally in three varieties: strong, weak or absent
Tie Strength
• Tie strength refers to a general sense of closeness with another person:
• The concept was introduced by Mark Granovetter in 1973.(A prof of
Sociology at Stanford)
• He asserted that "the strength of a tie is a ... combination of the amount
of time, the emotional intensity, the intimacy (mutual confiding), and the
reciprocal services which characterize the tie" (Granovetter, 1973).
• Granovetter defined two main types: strong ties and weak ties.
–Strong ties: the stronger links,corresponding to friends, dependable
sources of social or emotional support;
–Weak ties: the weaker links, corresponding to acquaintances.
 Factors Determining Tie Strength
• Tie strength is influenced by
multiple factors, including:
–Interaction frequency (How
often two people
communicate)
–Emotional intensity (The
depth of their connection)
–Reciprocity (Mutual exchange
of information or support)
–Network overlap (How many
common friends they share)
Importance of Tie Strength

• How information flows through a social network

• How different nodes can play structurally distinct roles in this
process
• How these structural considerations shape the evolution of the
network itself over time
Type of Tie Description Example in Social Networks Strength
Close relationships with frequent
Friends & Best friends on Facebook, family
interactions and emotional Strong
Relatives members on WhatsApp.
bonding.
Distant connections with
Associates & LinkedIn connections, Twitter
occasional interactions; useful for Weak
Acquaintances followers.
spreading new information.
Potential connections that exist Suggested friends on Facebook,
Latent Ties Weak
but are not actively used. mutual LinkedIn connections.
Links between different groups, A LinkedIn connection linking
Bridging Ties Weak
helping in knowledge transfer. two industries.
Strengthens connections within a Private Facebook groups for
Bonding Ties Strong
close-knit community. family or college alumni.
Relationships that exist in multiple A co-worker who is also a
Multiplex Ties Strong
contexts (e.g., work & personal). gaming buddy on Discord.
Relationships marked by conflict Blocking someone on Instagram,
Negative Ties Weak
or rivalry. Twitter feuds.
 The Strength of Weak Ties

Mark Granove er
creater of the concepts:

Strong es
Weak es
•Professor
One in theof the
School firstatefforts
of Humanities Stanford. to
understand
Research the
areas: Social foundations of theimportance
economy. of tie
strength was Granovetter’s study
on how people get jobs.
• He published the results of the
study in his paper, “The Strength of
Weak Ties” (1973), and again in
greater depth in his book Getting a
Job (1974).
 “Finding a job”
• Mark Granovetter (1960s)
– interviewed people who had recently changed
employers
– how they discovered their new jobs?
– many learned information through personal contacts
– these contacts often described as acquaintances
(weak ties) rather than close friends (strong ties)
• A bit surprising:
– your close friends have the most motivation to help
– why more distant acquaintances who are to thank?

”It is the distant acquaintances who are

actually to thank for crucial information
leading to your new job, rather than your close
friends!”
STRONG TIES WEAK TIES
Granovetter argues that
weak ties serve primarily
to build local bridges
between groups of actors
who otherwise would be
isolated, which justify the
strength of the weak ties
(the richness of
communication).

So, the weak ties help to

the information flow
through different social
circles (strong ties).
Example LinkedIn

• A typical LinkedIn user, probably has somewhere between 300 and 999
connections.
• Some of these might be cold-connects, people met in passing, and others
might be ex-colleagues with min. contact
• Do we need all of these connections? ?
–Surprisingly this extended network carries more value than others.
–According to a popular social network theory, “strength of Weak Ties”
lesser-known contacts are access points to professional circles outside your
own.
–Through these individuals, you’re always just one person removed
from their network of contacts — people from different industries and
companies who might help you in your career one day.
 Proof - 50 years later in Social Networks
• A large-scale experiment co-directed by
an MIT scholar shows that on LinkedIn
weak connections are more likely to
land you new employment, compared
to your ties with people you know
better.
• “When we look at the experimental
data, weak ties are better, on average,
for job mobility than strong ties,” says
Sinan Aral, a management professor at
MIT and co-author of a new paper
detailing the results of the study, which
involved millions of LinkedIn users.
The Experiment
• The current study was a five-year experiment involving LinkedIn’s “People You May
Know” (PYMK) algorithm, which suggests new connections to site users.
• To conduct the expt, from 2015 through 2019, LinkedIn adjusted the PYMK algorithm, so
that some site users saw a higher no. of PYMK suggestions to whom they had strong ties,
and others received more PYMK suggestions to people with whom they had weak ties.
• The scholars also defined tie strength in two ways: by interaction intensity, based on the
number of messaging interactions people had, and in structural terms, based on the
number of mutual friends two users had in common.
• The experiment involved around 20 million LinkedIn users, creating about 2 billion new
connections on the site, recorded over 70 million job applications, and wound up
accepting 600,000 new jobs identified through the site.
• And from that mass of data, a clear pattern emerged. As the researchers write in the
paper, “the stronger the newly added ties were, the less likely they were to lead to a
job transmission.”
 Strength of Weak Ties
• The most notable role of weak ties in social networks is their
structural significance as connectivity-generating factors: they
tend to be bridges that connect distant clusters within social
structures.
• Weak ties are less subject to the closure-producing transitivity
pressures that operate on stronger ones, and hence less likely to
be confined within local social environments.
• They bring circles of networks into contact with each other,
strengthening relationships and forming new bonds between
existing relationship circles.
Strength of a Tie

• strength of ties captures a sense of closeness among entities/people

• Simplest metric to capture the same is via Jaccard score
• Corresponding metric, called Neighborhood Overlap (NO) is defined as:
|𝚪 𝐱 ∩𝚪 𝐲 |
– 𝐍 𝐱, 𝐲 =
|𝚪 𝐱 ∪𝚪 𝐲 |
• where Γ(∙) denotes the neighbourhood of a node
• Higher the 𝑁𝑂(∙) score, higher the overlap between the nodes, and
higher the chance forming a link in between
 Neighborhood Overlap: Example
Γ 𝐴 = 𝐵, 𝐶, 𝐷, 𝐸, 𝑀 ,
F H Γ 𝑀 = 𝐴, 𝐼, 𝐽, 𝐾, 𝐿 ,
Γ 𝐸 = {𝐴, 𝐷, 𝐹, 𝐺}
G
Γ 𝐴 ∩ Γ 𝑀 = |𝜙| = 0
E I Γ 𝐴 ∩Γ 𝐸 = 𝐷 =1

Γ 𝐴 ∪Γ 𝑀 = |{𝐵, 𝐶, 𝐷, 𝐸, 𝐼, 𝐽, 𝐾, 𝐿}| = 8

D A M J Γ 𝐴 ∪Γ 𝐸 = |{𝐵, 𝐶, 𝐷, 𝐹, 𝐺, 𝑀}| = 6

0
𝑁𝑂 𝐴, 𝑀 = = 0
8
C B L K 1
𝑁𝑂 𝐴, 𝐸 =
6
Triadic Closure
 Triadic Closure
• A friend of a friend is also a friend – is the philosophy

A A A Reasons behind Triadic closure

formation
 Opportunity: of meeting via
mutual connection
B C B C B C  Trust: link formation based
on mutual trust
𝑡 − Δ𝑡 𝑡 𝑡 + Δ𝑡
B & C are not
 Incentive: nodes may have
B & C gets B & C are friends
friends yet introduced (via A) now
incentives to bring their
mutual friends together
 Quantifying Strength of Triadic Closures

• Strength of a triadic closure with respect to node A and the

nodes B and C of which A is a mutual friend can be quantified
A using the clustering coefficient of node A

• Clustering coefficient of a node (𝐶𝐶𝐴 ) measures the probability

that the pair of friends (B and C) of the given node (A) are
B C
friends of each other
2×σ𝑖,𝑗∈Γ(𝐴) 𝑰 𝑖,𝑗 ∈𝐸
• 𝐶𝐶𝐴 =
𝑘𝐴 (𝑘𝐴 −1)
• where 𝑰(∙) is the indicator function that returns 1 if condition is
true, and 0, otherwise
Bridges
Local Bridge
 Local Bridges/Weak Ties

F H An edge can be considered a local

G
bridge if its Neighborhood Overlap
Score (NO) is zero
E I In other words, end-points of a local
bridge have no mutual friends
Local bridges are not a part of any
D A M J triad in the network
 𝐴, 𝑀 is a local bridge/weak tie

C B L K
Strong Triadic Closure Property
Local Bridges: Importance
Close friends tend to move in the same circles that we do
Information close friends receive overlaps considerably
Acquaintances, by contrast, know people that we do not,
People receive more novel information through acquaintances than from close
friends
Weaker ties act as a bridge and help a person gain access to newer and wider
information (strength of weak ties)
In case of stress/conflict between two groups, weak ties act as mediators
In an adversarial setting, removing local bridges can lead to the formation of echo
chambers
During disease outbreaks, local bridges may cause the disease to transmit from one
group to another
Relevance of Weak Ties - DiffusionWeak es
Relevance
“Intuitively speaking, this means that whatever is to be
diffused can reach a larger number of people, and
traverse greater social distance (i.e., path length),
when passed through weak ties rather than strong.”

e.g.
Granovetter 1973
Rumors diffusion process
Hysteria incident
Small Worlds Weak es
Relevance
If ones tells a rumour to all his closed friends, then is probable that
each person will hear the same rumour more than ones.

If the rumour spreads strong ties moves few clicks

(bridges won’t be crossed)
 Diffusion – Propogation
• Many factors play in to how things propagate through networks, and tie strength is
one of them.
• Normally a person’s strong ties tend to be connected to one another, often by
more strong ties.
• Granovetter proposes that as the strength of a tie becomes stronger, the overlap in
social circles will tend to increase.
• This means that if we follow all edges from our strong ties, we will re- encounter
many of our own friends.
• That in turn implies that if we pass information to our strong ties and if they pass it
to their strong ties, it will not go very far; instead, it is likely to reach people who
have already received the message.
• If we pass that same information to our weak ties, it has a chance to go farther in
the network. Since there is usually smaller overlap in friends between a person and
their weak ties, the weakly connected people have a chance to spread the
information to new people whom the source did not know.
Measuring Tie Strength
The strength of a tie is a (probably linear) combination of
• Time can include the amount of time people spend with each other, the
duration of their relationship (i.e., how long they have known each other),
and how frequently they see one another.
• Emotional intensity is indicated by the closeness of a relationship; close
friends or family members are likely to be strong ties, while more casual
friends and acquaintances would be weaker ties.
• Intimacy, or mutual confiding, relates to people sharing secrets or intimate
personal details with one another. The more information they exchange, the
closer the relationship is likely to be.
• Reciprocal Services are favors that people do for one another, may be
personal , financial, professional etc
Measuring Tie Strength – Other
• Structural features relate to the social network of the two
people in question. Those who have many mutual friends
are likely to have stronger ties.
• Social Distance measures how different people’s social
situations are. This includes factors like age difference,
race, education, and socioeconomic status. People with
strong ties tend to have similar social attributes.
• Emotional Support describes the communication between
people that validates their emotions, shows understanding
of their problems, and tries to alleviate stress.
Dunbar Number
An empirical study that supports the presence of strong and weak ties in real
world
Refers to a suggested cognitive limit to the number of people with whom one
can maintain stable social relationships
First proposed in 1990 by British anthropologist Robin Dunbar
Observed a correlation between primate brain size and average social group
size
Extrapolation from the results of primates using the average human brain
size
The number informally represents the set of people one can be in close
contact with (strong ties)
Rest of the social contacts are likely to be acquaintances (weak ties)
Robin Dunbar- Dunbar Number
• We have a much smaller number of strong ties than weak ties.
• Typical Numbers:
– Inner circle: 5
– sympathy group: 12-15
– Semi-regular group: 50
– stable social group: 150 (the Dunbar number)
– friends of friends group (weak ties): 500
• Dunbar’s number: a measurement of the “cognitive limit to the number of individuals with whom
any one person can maintain stable relationships (2010)
Dunbar’s Number
Social media
platforms artificially
expand networks,
but active
engagement remains
within Dunbar-like
limits.
Dunbar Number and Real life Social Networks
Implication Effect on Real-Life Social Networks Impact on Tie Strength
Platforms like Facebook allow thousands of Strong ties are maintained with a
Social Media Friend Limits connections, but only a small fraction (close small subset of friends, while weak
friends) are actively engaged. ties make up the majority.
Strong ties receive frequent
Users primarily interact with 50-150 people on engagement (likes, comments, DMs),
Engagement & Interaction
social platforms despite having larger networks. while weak ties get occasional
interactions.
Brands and influencers rely on weak ties for viral
Influencer & Marketing Weak ties help spread content, while
reach, but strong ties for trust-based
Strategies strong ties drive purchasing decisions.
engagement.
In LinkedIn, strong ties (colleagues, mentors)
Workplace & Professional Weak ties play a crucial role in job
provide career support, while weak ties expand
Networks referrals and new opportunities.
job opportunities.
Group chats, Discord servers, and Facebook Strong ties form the core of small,
Community Building groups are effective when they stay within tight-knit groups, while weak ties help
Dunbar’s number. grow communities.
Measuring Tie Strength - FaceBook
Dunbar-like numbers in social networks:
Social Network Dunbar-Like Number Description
Number of friends a user actively interacts with,
Facebook ~150-250
despite having 500+ connections.
People a user regularly engages with through
Twitter (X) ~100-200
likes, replies, and retweets.
Close circle that consistently engages (DMs,
Instagram ~50-100
story views, likes).
Professional contacts a user finds meaningful,
LinkedIn ~300-500
out of thousands of connections.
Size of an active, engaged community within
Discord/Reddit ~100-200
larger groups.
Core group of close friends frequently sending
Snapchat ~30-70
snaps.
Applications

• E-Commerce & Recommendation Systems

– Personalized Recommendations: Platforms like Amazon and Netflix use social
network analysis to recommend products/movies based on weak ties.
– Peer Reviews & Ratings: Users trust reviews from weak ties more than
advertisements, influencing purchase decisions.
• Netflix’s "Top Picks for You" suggests content based on viewing habits of weak ties
rather than strong ties.
• The #IceBucketChallenge (2014) spread through weak ties on Facebook and Twitter,
raising millions for ALS research.
– How? A celebrity or influencer (strong tie to some, weak tie to others) shares a
challenge, and their audience spreads it further.
END