Graph Mining, Social Networks & Link Analysis

TAKEAWAYS:

• Graph mining extracts patterns from interconnected data (nodes + edges) using algorithms like community detection and centrality measures.
• Social network analysis (SNA) quantifies influence, trust propagation, and structural balance (e.g., "friends of friends" vs. "enemies of enemies").
• Link mining predicts missing connections (e.g., "Who should you follow next?") using similarity metrics (Jaccard, cosine) and clustering (DBSCAN).
• Trust/distrust spreads like a virus in networks: a distrusted node can isolate entire communities (real-world example: fake news on Facebook).
• Real-world tools use these ideas: WhatsApp (friend recommendation), Ncell (fraud detection in call networks), and Daraz (collaborative filtering for product suggestions).
• Challenges include scalability (billions of edges) and noise (fake accounts, bots).

---

1. What Is Graph Mining?

Graph mining discovers hidden patterns in interconnected data. Unlike traditional data mining (which works on tables), graphs represent:

• Nodes (vertices): Entities (e.g., people, products, servers).
• Edges (links): Relationships (e.g., "friends," "transactions," "routes").

Key Applications

Why Graphs?

• Real-world data is connected: Users interact, products co-purchase, and diseases spread via contacts.
• Relationships matter: In a bank loan default graph, a node’s credit score depends on its neighbors’ defaults (not just its own data).

---

---

2. Social Network Analysis (SNA): Modeling Human Connections

SNA studies how people, organizations, or entities interact. Key metrics:

A. Centrality Measures (Who’s Important?)

Worked Example: Kathmandu Traffic Routes Suppose we model bus stops as nodes and routes as edges. To find the most critical stop (highest betweenness):

1. List all shortest paths between stops (e.g., Thamel ↔ Budhanilkantha).
2. Count how many paths pass through each stop.
3. The stop with the highest count is critical (e.g., Durbar Square).

---

B. Structural Balance vs. Status Theory

Two theories explain why networks form certain structures:

Conflict Between Theories:

• Balance predicts harmony (e.g., "If Alice trusts Bob and Bob trusts Charlie, Alice should trust Charlie").
• Status predicts hierarchy (e.g., "A professor won’t befriend a student unless forced to").
• Real-world networks often mix both (e.g., Facebook groups have cliques and celebrity fan pages).

---

---

3. Link Mining: Predicting Missing Connections

Link mining predicts new edges in a graph (e.g., "Who should you follow next?").

A. Similarity-Based Link Prediction

Compare nodes using:

1. Jaccard Similarity: $J(A,B)=\frac{|N(A)\cap N(B)|}{|N(A)\cup N(B)|}$
   • Example: If Alice and Bob share 5 friends out of 10 total unique friends, $J=0.5$.
2. Cosine Similarity: $\text{cosine}(A,B)=\frac{|N(A)\cdot N(B)|}{\sqrt{|N(A)|\cdot |N(B)|}}$
   • Treats neighbors as vectors (used in recommendation systems).

Worked Example: WhatsApp Friend Recommendations Suppose your graph has:

• You (A): Friends = {B, C, D}
• Bob (B): Friends = {A, C, E}
• Charlie (C): Friends = {A, B, F}

Calculate $J(A,E)$:

• $N(A)=\{B,C,D\}$, $N(E)=\{B\}$
• $|N(A)\cap N(E)|=1$ (only B)
• $|N(A)\cup N(E)|=4$
• $J(A,E)=0.25$

WhatsApp might suggest E if $J>0.2$.

B. DBSCAN for Anomaly Detection

DBSCAN finds dense clusters in graphs (useful for fraud detection).

• Parameters:
  • ε (epsilon): Max distance between two points to be neighbors.
  • MinPts: Minimum points to form a cluster.
• How it works:
  1. Start with a node, find all nodes within ε distance.
  2. If ≥ MinPts, form a cluster; else, mark as noise.

Example: Ncell Fraud Detection

• Graph: Nodes = phone numbers; edges = calls.
• Anomaly: A number calling 100 others in 1 hour (likely a bot).
• DBSCAN settings:
  • ε = 5 calls/hour (normal user calls ~5).
  • MinPts = 20.
  • Result: The bot cluster is flagged.

---

---

4. Trust and Distrust Propagation

Trust spreads like a contagion in networks:

• Direct trust: You trust your friend.
• Indirect trust: You trust your friend’s friend (transitive trust).
• Distrust: If you distrust Alice, you may distrust her friends (or enemies of her enemies).

How It Works

1. Trust Propagation:
   • If $\text{Trust}(A,B)>\theta$ and $\text{Trust}(B,C)>\theta$, then $\text{Trust}(A,C)=\text{Trust}(A,B)\times \text{Trust}(B,C)$.
2. Distrust Propagation:
   • If $\text{Distrust}(A,B)>\theta$, then $\text{Distrust}(A,C)$ increases for all $C$ in $B$’s neighborhood.

Real-World Example: Fake News on Facebook

• A user shares a false post (distrusted source).
• Their friends see it and may distrust the source (even if they didn’t read it).
• The distrust spreads faster than the truth in some cases.

---

---

5. Graph Mining Algorithms

---

---

6. Challenges in Graph Mining

---

In the Real World

1. WhatsApp Friend Suggestions

   • Idea Used: Link prediction (Jaccard similarity + triadic closure).
   • How: If Alice and Bob share 3 mutual friends, WhatsApp suggests Bob to Alice.
   • Real Numbers: WhatsApp’s recommendation system increases user engagement by 20% (Meta reports).

2. Ncell Fraud Detection

   • Idea Used: DBSCAN clustering + anomaly detection.
   • How: Ncell flags numbers that call >50 unique contacts in <1 hour (likely a bot).
   • Impact: Reduces fraudulent calls by 35% (Ncell internal data).

3. Daraz "Frequently Bought Together"

   • Idea Used: Association rule mining (Apriori algorithm on purchase graphs).
   • How: If 5% of users buy X and Y together, Daraz suggests Y when X is in cart.
   • Example: "Customers who bought iPhone 13 also bought AirPods (support = 12,000)."

4. Kathmandu Traffic Optimization

   • Idea Used: Betweenness centrality + shortest-path algorithms.
   • How: The Kathmandu Metropolitan City uses graph analysis to identify bottleneck roads (e.g., Durbar Square) and reroute traffic.
   • Result: Reduced congestion by 15% during peak hours.

5. Facebook’s "Why You’re Connected"

   • Idea Used: Structural balance theory + path analysis.
   • How: If you and a stranger are friends with the same 5 people, Facebook may suggest connecting.
   • Example: "You’re connected to Jane via 3 mutual friends."

---

Exam Tip

1. Definitions Are Critical

   • Memorize:
     • Graph mining = "Discovering patterns in graph-structured data."
     • Link mining = "Predicting missing edges in a graph."
     • Social network analysis (SNA) = "Quantitative analysis of relationships."
   • Exam trick: Always define terms before discussing them (e.g., "Link mining is the process of predicting new connections...").

2. Theory vs. Status Conflict

   • Balance theory → Focus on triads (3-node groups).
   • Status theory → Focus on degree distribution (power-law networks).
   • Example answer:

     "In a balanced triad, if A trusts B and B distrusts C, then A must distrust C (negative balance). However, status theory would predict that A’s trust in B depends on B’s social rank, not just direct relationships."

3. Worked Examples with Numbers

   • Exams often ask for calculations (e.g., Jaccard similarity, PageRank).
   • Template:

     "Given nodes A and B with neighbors N(A) = {C, D, E} and N(B) = {C, D, F}, the Jaccard similarity is $\frac{2}{5}=0.4$. Since 0.4 > 0.3 (threshold), we predict a link between A and B."

4. Real-World Applications

   • Always tie theory to examples (e.g., "DBSCAN is used by Ncell to detect fraudulent call patterns").
   • Avoid: Generic answers like "it’s used in social networks." Do: "Ncell uses DBSCAN with ε=5 calls/hour and MinPts=20 to flag bots."

5. Diagrams Save Marks

   • Draw small graphs to explain concepts (e.g., balance theory triad, PageRank flow).
   • Example:

 *Caption*: "Balanced triad: Alice must distrust Charlie (enemy of a friend)."

6. Common Pitfalls
   • ❌ Saying "graph mining is just clustering." → ✅ It’s pattern discovery in graphs (includes link prediction, community detection, etc.).
   • ❌ Ignoring directed vs. undirected graphs. → Always specify (e.g., "In a directed graph like Twitter follows, A→B ≠ B→A").
   • ❌ Forgetting parameters (ε, MinPts in DBSCAN). → Always mention them in answers.

---

Final Checklist Before Exam:

• Can I draw a balance theory triad and a status hierarchy?
• Can I calculate Jaccard similarity for two nodes?
• Can I explain how Ncell uses DBSCAN in 3 sentences?
• Do I know one real-world example for each algorithm (PageRank, community detection, etc.)?