Graph Mining & Social Networks: Models, Algorithms & Applications

TAKEAWAYS:

• Graphs model relationships (nodes = entities, edges = interactions) and are used in social networks, fraud detection, and recommendation systems like Daraz’s "customers who bought this also bought" feature.
• Graph traversal algorithms (BFS/DFS) uncover hidden patterns in networks (e.g., identifying influential users in Pathao’s driver network or detecting money-laundering rings in bank transactions).
• Community detection (e.g., Louvain method) groups similar nodes (e.g., clustering Khalti users by transaction behavior or Ncell subscribers by call patterns).
• Centrality measures (degree, betweenness, closeness) rank nodes by importance (e.g., identifying key influencers in Nepali political or business networks on Facebook).
• Path analysis (shortest paths, PageRank) powers recommendation engines (e.g., YouTube’s "because you watched" or Daraz’s delivery route optimization).
• Graph databases (Neo4j) outperform SQL for connected data (e.g., tracking eSewa’s interlinked transactions or NTC’s network outages).

1. Graphs: The Foundation of Network Data

Graphs represent data as nodes (vertices) connected by edges (relationships). Unlike tables, they capture non-hierarchical, interconnected relationships—ideal for social networks, fraud detection, and recommendation systems.

Key Graph Components

graph TD
    A["Node (Vertex)"] -->|"represents"| B["Entity: User, Transaction, Product"]
    C["Edge (Link)"] -->|"represents"| D["Relationship: Friendship, Purchase, Call"]
    E["Weight"] -->|"on edge"| F["Strength: Likelihood, Cost, Time"]
    G["Direction"] -->|"edge"| H["Directed: Follows, Transfers Money"]
    I["Label"] -->|"on node/edge"| J["Attributes: Age, Transaction Amount"]

Real-world analogy:

• eSewa’s transaction network: Nodes = users/businesses; edges = money transfers (weight = amount, direction = sender→receiver).
• Pathao’s driver-passenger graph: Nodes = drivers/passengers; edges = rides (weight = distance/time; direction = driver→passenger).

Graph Types

2. Graph Representations for Mining

How to store graphs for efficient querying and analysis?

A. Adjacency Matrix

• Definition: 2D array where matrix[i][j] = 1 if edge exists between node i and j.
• Pros: Fast lookup for edge existence.
• Cons: Inefficient for sparse graphs (wastes space).
• Example: Representing 4 users in a friendship network:

  # Adjacency matrix for nodes A, B, C, D
  [[0, 1, 0, 1],  # A is friends with B, D
   [1, 0, 1, 0],  # B is friends with A, C
   [0, 1, 0, 1],  # C is friends with B, D
   [1, 0, 1, 0]]  # D is friends with A, C
  

B. Adjacency List

• Definition: List of lists where each node points to its neighbors.
• Pros: Space-efficient for sparse graphs.
• Cons: Slower edge existence checks.
• Example: Same graph as above:

  {
      "A": ["B", "D"],
      "B": ["A", "C"],
      "C": ["B", "D"],
      "D": ["A", "C"]
  }
  

C. Edge List

• Definition: Simple list of (node1, node2) pairs.
• Use case: Input for graph algorithms (e.g., community detection).
• Example:

  [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
  

3. Graph Traversal: Exploring Networks

Traversal algorithms visit all nodes and uncover hidden patterns (e.g., shortest paths, connected components).

A. Breadth-First Search (BFS)

• How it works: Explores all neighbors at the present depth before moving deeper.
• Use cases:
  • Finding shortest paths (e.g., Pathao’s optimal driver-passenger matching).
  • Detecting communities (e.g., groups of users with similar transaction patterns in eSewa).
• Visualization:

Worked Example: Find all users within 2 hops of User A in Khalti’s network.

• Input: Adjacency list of Khalti users (nodes = users; edges = transactions).
• Steps:
  1. Start at A, visit neighbors B and C (Level 1).
  2. From B, visit D and E (Level 2).
  3. From C, visit F (Level 2).
• Output: Users reachable in ≤2 transactions: A, B, C, D, E, F.

B. Depth-First Search (DFS)

• How it works: Explores as far as possible along a branch before backtracking.
• Use cases:
  • Detecting cycles (e.g., fraud rings in bank transfers).
  • Topological sorting (e.g., dependency resolution in software projects).
• Visualization:

Worked Example: Detect a cycle in Ncell’s call network (indicating potential spam calls).

• Input: Edge list of calls: (A→B, B→C, C→A, C→D).
• Steps:
  1. Start at A, visit B.
  2. From B, visit C.
  3. From C, visit A (already visited) → cycle detected (A→B→C→A).

4. Centrality Measures: Who Matters in the Network?

Centrality identifies influential nodes (e.g., key users, critical infrastructure).

A. Degree Centrality

• Definition: Number of edges connected to a node.
• Formula: $\text{Degree}(v)=\text{number of edges incident to }v$.
• Example: In a Twitter network, a user with 10,000 followers has high degree centrality.
• Limitation: Ignores edge weights or network structure.

B. Betweenness Centrality

• Definition: How often a node lies on the shortest path between others.
• Formula: $$C_B(v)=\sum _{s\ne v\ne t}\frac{{\sigma }_{st}(v)}{{\sigma }_{st}}$$ where ${\sigma }_{st}$ = total shortest paths from s to t, ${\sigma }_{st}(v)$ = paths passing through v.
• Real-world use:
  • Pathao: Identify drivers who act as "hubs" for ride requests in Kathmandu traffic.
  • NTC: Find critical nodes in the power grid whose failure causes outages.
• Worked Example: Calculate betweenness for node B in this graph:

  graph TD
    A --> B
    B --> C
    B --> D
    C --> D

  • Shortest paths:
    • A→C: A→B→C (passes B).
    • A→D: A→B→D (passes B).
    • C→D: C→D (does not pass B).
  • Betweenness of B: $$C_B(B)=\frac{1}{1}+\frac{1}{1}+0=2$$
  • Interpretation: B is critical for connectivity between A and C/D.

C. Closeness Centrality

• Definition: How close a node is to all others (inverse of average shortest-path distance).
• Formula: $$C_C(v)=\frac{1}{{\sum }_{u\ne v}d(u,v)}$$ where $d(u,v)$ = shortest-path distance.
• Use case: eSewa’s fraud detection: Users with high closeness centrality in transaction networks may be money mules.

D. Eigenvector Centrality

• Definition: Nodes connected to other high-centrality nodes are themselves important.
• Formula: Solve $A\mathbf{x}=\lambda \mathbf{x}$, where $A$ = adjacency matrix.
• Example: Google’s PageRank (a variant) ranks web pages by importance.

5. Community Detection: Finding Groups in Networks

Communities are densely connected subgroups (e.g., friend circles, interest groups).

A. Modularity

• Definition: Measures how well a division of a network into communities improves over random connections.
• Formula: $$Q=\frac{1}{2m}\sum _{ij}\left[A_{ij}-\frac{k_i{k}_j}{2m}\right]\delta (c_i,c_j)$$ where $A_{ij}$ = edge between i and j, $k_i$ = degree of i, $m$ = total edges, $\delta$ = 1 if i and j are in the same community.
• High modularity = strong community structure.

B. Louvain Method (Algorithm)

1. Phase 1: Assign each node to its own community.
2. Phase 2: Iteratively move nodes to neighboring communities to maximize modularity.
3. Phase 3: Build a new graph where each community is a "super-node" and repeat.

Worked Example: Detect communities in a Daraz customer graph (nodes = users; edges = co-purchases).

• Input: Edge list of co-purchases (e.g., A and B bought the same product).
• Output: Communities like:
  • {A, B, C} (bought electronics).
  • {D, E, F} (bought groceries).
• Application: Daraz can recommend products within the same community.

6. Path Analysis: Shortest Paths and Recommendations

A. Dijkstra’s Algorithm

• Purpose: Find the shortest path from a source to all other nodes (weighted graphs).
• Use case: Pathao’s route optimization for drivers.
• Worked Example: Find the shortest path from A to D in Kathmandu traffic (weights = travel time in minutes):

  graph TD
    A["A: Thapathali"] -->|"5"| B["B: Putalisadak"]
    A -->|"3"| C["C: Durbar Marg"]
    B -->|"2"| D["D: Kantipath"]
    C -->|"4"| D

  • Steps:
    1. Start at A (distance = 0).
    2. Update neighbors: B = 5, C = 3.
    3. Pick C (smallest distance), update D = 3 + 4 = 7.
    4. Pick B, update D = min(7, 5 + 2) = 7.
  • Shortest path: A→C→D (total time = 7 minutes).

B. PageRank (Google’s Algorithm)

• Purpose: Rank nodes by importance (e.g., web pages, users).
• Formula: $$PR(p_i)=\frac{1-d}{N}+d\sum _{p_j\in M(i)}\frac{PR(p_j)}{L(p_j)}$$ where $d$ = damping factor (~0.85), $N$ = total nodes, $M(i)$ = pages linking to i, $L(p_j)$ = out-links from p_j.
• Real-world use:
  • YouTube: Ranks videos by "importance" in recommendations.
  • LinkedIn: Identifies influential professionals.

7. Graph Mining Applications in Nepal

8. Graph Databases: Storing Connected Data

Traditional SQL struggles with graphs. Graph databases (e.g., Neo4j) store data as nodes/edges and query using Cypher (a graph query language).

Example Query in Neo4j:

// Find all friends of "User123" who also bought "Product456"
MATCH (u:User {id: "User123"})-[:FRIEND]->(friend)-[:PURCHASED]->(p:Product {id: "Product456"})
RETURN friend.name

Why use Neo4j?

• eSewa: Tracks interconnected transactions (user→business→user).
• NTC: Models power grid nodes and outage dependencies.

In the Real World

1. Pathao’s Driver-Passenger Matching:

   • Graph idea: Bipartite graph (drivers ↔ passengers) + shortest-path algorithms to match riders to nearby drivers efficiently.
   • How it works: When you request a ride, Pathao’s system:
     • Represents drivers as nodes in a spatial graph (edges = distance).
     • Uses Dijkstra’s algorithm to find the closest available driver.
     • Updates the graph in real-time as drivers accept/reject requests.

2. eSewa’s Fraud Detection:

   • Graph idea: Transaction network graph (nodes = users/businesses; edges = money flows) + anomaly detection via centrality measures.
   • How it works:
     • A sudden spike in a user’s out-degree (sending money to many new recipients) triggers a fraud alert.
     • Betweenness centrality helps identify money mules (users who frequently route money between others).

3. Daraz’s "Frequently Bought Together":

   • Graph idea: Market basket analysis on a user-product bipartite graph.
   • How it works:
     • Nodes: Users and products.
     • Edges: Purchases (weight = frequency).
     • Apriori algorithm finds frequent co-purchases (e.g., "users who bought phone cases also bought screen protectors").
     • Visualized as a co-occurrence graph to recommend bundles.

Exam Tip

1. Graph Representations:

   • Must know: When to use adjacency matrix vs. list (sparse vs. dense graphs).
   • Exam trick: For a graph with n nodes and m edges, adjacency matrix uses $O(n^2)$ space; adjacency list uses $O(n+m)$.

2. Traversal Algorithms:

   • BFS vs. DFS:
     • BFS: Use for shortest paths (e.g., Pathao routes).
     • DFS: Use for cycle detection (e.g., fraud rings).
   • Practice: Given a graph, draw the traversal tree and list the order of visited nodes.

3. Centrality Measures:

   • Degree: Count edges.
   • Betweenness: Count how often a node is a "bridge."
   • Closeness: Average distance to all others.
   • Eigenvector: "Important friends make you important."
   • Exam question: "Which centrality would you use to find a key influencer in a political network?" → Betweenness (they connect disparate groups).

4. Community Detection:

   • Louvain method: Iterative modularity maximization.
   • Real-world link: "How would Daraz use community detection?" → Group users by purchase behavior to personalize recommendations.

5. Path Analysis:

   • Dijkstra: Shortest path in weighted graphs (e.g., traffic routes).
   • PageRank: Ranking nodes by importance (e.g., YouTube recommendations).
   • Worked example: Always show the priority queue steps for Dijkstra.

6. Graph Databases:

   • Neo4j vs. SQL: Use Neo4j for highly connected data (e.g., social networks, fraud detection).
   • Cypher query: Know the basic syntax (MATCH, RETURN).

Practice Questions for Full Marks

1. Short Answer:

   • Define betweenness centrality and give a Nepali example.
   • What is the time complexity of BFS on a graph with n nodes and m edges?

2. Worked Example:

   • Given the adjacency list below, perform BFS starting from node A and list the nodes in order of discovery.

     {
         "A": ["B", "C"],
         "B": ["A", "D"],
         "C": ["A", "D"],
         "D": ["B", "C"]
     }
     

3. Application-Based:

   • How would you use graph mining to detect fake accounts on Facebook in Nepal? Describe the steps using centrality measures and community detection.

4. Compare:

   • Algorithm	Use Case	Time Complexity
     BFS
     Dijkstra
     PageRank

Final Visual Summary

mindmap
  root((Graph Mining))
    Applications
      Fraud Detection
      Recommendations
      Traffic Optimization
    Algorithms
      Traversal
        BFS
        DFS
      Centrality
        Degree
        Betweenness
        Closeness
      Community Detection
        Louvain Method
      Path Analysis
        Dijkstra
        PageRank
    Representations
      Adjacency Matrix
      Adjacency List
      Edge List
    Real-World
      Pathao: Shortest Paths
      eSewa: Transaction Graphs
      Daraz: Co-Purchase Graphs