Module 3: Link Analysis &

Related Concepts

By: Udit Gupta

Department of AI&DS
CMR Institute Of Technology
 Link Analysis
Link analysis is a core technique in network theory that examines
relationships between nodes (such as people, organizations, or web
pages) within a network to uncover hidden patterns, identify
anomalies, and support decision-making across various domains.
 Link Analysis
Why Link Analysis?
Link analysis is essential because it helps us move far beyond simple data
summaries and enables a deeper level of understanding about how entities are
connected within complex systems. Here are the main reasons why link
analysis is vital in modern data analysis
1. Reveal hidden connections
o Hidden Patterns: Many important insights in real-world data exist not in
isolated numbers but in the connections between them. Link analysis
uncovers connections between people, organizations, transactions, or
events that would remain invisible in traditional database tables.
o Influence: In social networks or marketing, it helps identify not just who is
popular but who actually has influence, which is crucial for information
diffusion, trend spotting, or targeted interventions.
2. Detecting Patterns, Clusters, Bridges, and Anomalies
o Clustering and Communities: Network visualizations can reveal tightly-
knit groups, communities, or clusters of nodes which helps in
understanding group behaviors and targeting specific segments.
 Link Analysis
o Bridges and Gatekeepers: Some nodes serve as bridges between
unconnected groups so that these can highlight vulnerabilities or
opportunities for communication, risk, or activity spread.
o Anomalies and Outliers: Abnormal links or unexpected patterns can
quickly highlight fraud, criminal relationships, security threats, or system
failures that would take much longer to find with other methods
3. Reveal hidden connections
o Complex Systems Made Understandable: As data grows in complexity
and scale, traditional tools struggle to provide clear insights. Link analysis
often using graph visualizations, organizes massive, interconnected datasets
into intuitive forms, making it easier for humans (not just algorithms) to
spot trends, risks, or opportunities at a glance.
 Applications of Link Analysis
o Web Search & Ranking: Link analysis powers foundational
algorithms for web search, such as PageRank, which determines the
relevance of web pages by analyzing the number and quality of
inbound links(An inbound link is a hyperlink from one website to
another, also known as a backlink). A page linked by many other
reputable pages is deemed more significant, guiding search engines
like Google in ranking their search results.

o Social Network Analysis: In social networks, link analysis helps

identify influencers, community clusters, and the spread of
information or influence. By mapping out connections, analysts spot
key players, trace how messages travel, and understand how closely-
knit or dispersed certain communities are.

o Recommendation Systems: Many recommendation engines use link

analysis to examine relationships among users, products, and content.
For example, platforms recommend new friends, movies, or
products by analyzing which users have similar taste or are
connected to similar items in the network.
 Applications of Link Analysis
o Fraud & Spam Detection: Link analysis exposes abnormal patterns
and suspicious activities in financial transactions, emails, or
communications. By studying links between accounts or
communication nodes, it helps flag potential fraud rings, spam
campaigns, or illicit collaborations.
o Biological & Medical Networks: In biology and medicine, link
analysis reveals relationships between genes, proteins, diseases, or
treatments. For instance, mapping protein interaction networks can
uncover critical biological pathways or targets for drug development.
 Strong & Weak Ties
• Proposed by Mark Granovetter (1973)
• Strong ties: close, frequent, emotional (family, best friends)
• Weak ties: distant, infrequent, but provide new info (acquaintances)
• Bridging ties: connect different communities
• Strong ties: trust, redundancy
• Weak ties: novelty, opportunities
 Signed Networks
What is sign networks?
Sign networks have edges with signs . Sign networks in social network
analysis allow every relationship (edge) between two entities (nodes) to have a
qualitative nature means, it can be positive or negative. This distinction is
crucial in understanding real-world systems like social media, political
networks, or fraud rings.
 Signed Networks
Positive and Negative Edges
• Positive Edges indicate friendly or supportive relationships, such as trust,
friendship, or endorsement. For example, if person A trusts person B, or if a
user “likes” another user, the edge connecting them gets a positive sign.
• Negative Edges signify hostile relationships, such as distrust, rivalry, or
dislike. For example, person A distrusts person B, or two competing
companies have a rivalry, resulting in a negative edge.
 Signed Networks
• In the sign network when sign comes into the picture, we can actually
think of different ways to analyse it. In social science theory there are
two ways to analyse a sign network. One is called a balance theory
another is called status theory .
 Signed Networks
In summary, the Balance Theory P-O-X Model provides a simple rule (the
product of signs should be positive in a triad) to understand and predict which
sets of relationships are stable (balanced) and which are psychologically or
structurally unstable (imbalanced), helping analyze complex networks in
social, political, and commercial domains.
 Signed Networks
Balance Theory and Triads
• Balance Theory (Heider, Cartwright & Harary) deals with the stability of
triads (groups of three nodes). A triad is considered balanced if the product
of the edge signs is positive.
• For example, if all three edges are positive (everyone trusts everyone), or if
there are two negative and one positive edge (e.g., “my enemy’s enemy is
my friend”), the triad is balanced.
• If the product of the signs is negative (e.g., two friends share a common
enemy but are also enemies themselves), the triad is unbalanced and tends
to “resolve itself over time for psychological or structural stability.

Status Theory
Status Theory in the context of signed networks is a framework for interpreting
the signs of directed links (edges) between nodes as indicators of relative
status or prestige rather than simply like or dislike.
 Signed Networks
• In Status Theory, a signed link from node A to node B signifies A's perception of B's
status relative to its own.
• A positive link (A → B, "+") means A considers B to have a higher status than itself.
• A negative link (A → B, "–") means A considers B to have a lower status than itself.
• Signed, Directed Network: The relationships are both signed (positive/negative)
and directional (from one entity to another).
Algorithms