Graph Clustering

Example 1: Modularity

Modularity is a measure of the strength of a network’s division into clusters or communities. It is often used as an optimization function in algorithms like the Louvain method to find the best possible community structure. Higher modularity values indicate a denser intra-cluster connectivity compared to a random graph.

Q = (1 / 2m) * Σ [A_ij - (k_i * k_j / 2m)] * δ(c_i, c_j)
Where:
- m is the number of edges.
- A_ij is the adjacency matrix.
- k_i and k_j are the degrees of nodes i and j.
- c_i and c_j are the communities of nodes i and j.
- δ is the Kronecker delta function.

Example 2: Graph Laplacian Matrix

The Graph Laplacian is a matrix representation of a graph used in spectral clustering. Its eigenvalues and eigenvectors reveal important structural properties of the network, allowing the data to be projected into a lower-dimensional space where clusters are more easily separated, especially for irregularly shaped clusters.

L = D - A
Where:
- L is the Laplacian matrix.
- D is the degree matrix (a diagonal matrix of node degrees).
- A is the adjacency matrix of the graph.

Example 3: Edge Betweenness Centrality

Edge betweenness centrality measures how often an edge serves as a bridge on the shortest path between two other nodes. In the Girvan-Newman algorithm, edges with the highest betweenness are iteratively removed to separate communities, as these edges are most likely to connect different clusters.

C_B(e) = Σ_{s≠t} (σ_st(e) / σ_st)
Where:
- e is an edge.
- s and t are source and target nodes.
- σ_st is the total number of shortest paths from s to t.
- σ_st(e) is the number of those paths that pass through edge e.

• Social Network Analysis: Identify communities, influential users, and opinion leaders within social media platforms to target marketing campaigns and understand social dynamics.
• Recommendation Systems: Group similar users or items together based on behavior and preferences, enabling more accurate and personalized recommendations for e-commerce and content platforms.
• Fraud Detection: Uncover rings of fraudulent activity by identifying clusters of colluding accounts, transactions, or devices that exhibit unusual, coordinated behavior.
• Bioinformatics: Analyze protein-protein interaction networks to identify functional modules or groups of genes that work together, aiding in drug discovery and understanding diseases.

Example 1: Customer Segmentation

Cluster C_k = {customers | similarity(customer_i, customer_j) > threshold}
Use Case: An e-commerce company uses graph clustering on a customer interaction graph (views, purchases, reviews). The algorithm groups customers into segments like "budget shoppers," "brand loyalists," and "seasonal buyers," allowing for highly targeted marketing promotions and personalized product recommendations.

Example 2: Financial Fraud Ring Detection

FraudRing = Find_Communities(Graph(Transactions, Accounts))
where Community_Density(C) > Density_Threshold AND Inter_Community_Edges(C) < Edge_Threshold
Use Case: A bank models transactions as a graph and applies community detection algorithms. It identifies a small, densely connected cluster of accounts involved in rapid, circular money transfers, flagging it as a potential money laundering ring for investigation.

This example demonstrates how to perform spectral clustering on a simple graph using scikit-learn and NetworkX. The code creates a graph, computes the adjacency matrix, and then applies spectral clustering to partition the nodes into two clusters.

import networkx as nx
from sklearn.cluster import SpectralClustering
import numpy as np

# Create a graph
G = nx.karate_club_graph()

# Get the adjacency matrix
adjacency_matrix = nx.to_numpy_array(G)

# Apply Spectral Clustering
sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(adjacency_matrix)

# Print the cluster labels for each node
print('Cluster labels:', sc.labels_)

This example uses the Louvain community detection algorithm, which is highly efficient for large networks. NetworkX provides a simple function to find the best partition of a graph by optimizing modularity.

import networkx as nx
from networkx.algorithms import community

# Use a social network graph example
G = nx.karate_club_graph()

# Find communities using the Louvain method
communities = community.louvain_communities(G)

# Print the communities found
for i, c in enumerate(communities):
    print(f"Community {i}: {sorted(list(c))}")

This example illustrates the Girvan-Newman algorithm, a divisive method that identifies communities by progressively removing edges with the highest betweenness centrality.

import networkx as nx
from networkx.algorithms.community import girvan_newman

# Use the karate club graph again
G = nx.karate_club_graph()

# Apply the Girvan-Newman algorithm
communities_generator = girvan_newman(G)

# Get the top-level communities
top_level_communities = next(communities_generator)

# Print the communities at the first level of division
print(tuple(sorted(c) for c in top_level_communities))

• Spectral Clustering: This method uses the eigenvalues (the spectrum) of the graph's similarity matrix to project data into a lower-dimensional space where clusters are more easily separated. It is particularly effective for identifying non-convex or irregularly shaped clusters that other algorithms might miss.
• Hierarchical Clustering: This approach creates a tree-like structure of clusters, known as a dendrogram. It can be agglomerative (bottom-up), where each node starts as its own cluster and pairs are merged, or divisive (top-down), where all nodes start in one cluster that is progressively split.
• Modularity-Based Clustering: These algorithms, like the Louvain method, aim to partition a graph into communities by maximizing a metric called modularity. This metric quantifies how densely connected the nodes within a cluster are compared to a random network, making it excellent for community detection.
• Density-Based Clustering: This method identifies clusters as dense areas of nodes separated by sparser regions. Algorithms like DBSCAN work by grouping core points that have a minimum number of neighbors within a certain radius, making them robust at handling noise and discovering arbitrarily shaped clusters.
• Edge Betweenness Clustering: This divisive method, exemplified by the Girvan-Newman algorithm, progressively removes edges with the highest "betweenness centrality"—a measure of how often an edge acts as a bridge between different parts of the graph. This process naturally breaks the network into its constituent communities.