Community Detection Algorithms in TGraphX
Community detection asks a deceptively simple question: given a graph, which nodes naturally belong together? The question matters across virtually every domain where graphs appear — social networks, citation graphs, protein interaction networks, and infrastructure dependency maps all exhibit community structure that carries interpretable meaning. Detecting those communities reliably, and knowing when a method is appropriate, is a core graph analysis skill.
TGraphX provides community detection through the tgraphx.mining.communities module. This article covers the major algorithm families, how modularity-based optimization differs from spectral approaches, and how to apply and evaluate community detection on a practical graph.
What Community Detection Is Solving
A community in a graph is loosely defined as a set of nodes with more internal edges than would be expected by chance. Formally, this is measured by modularity:
Q = (1 / 2m) * Σ_{ij} [ A_ij - k_i * k_j / (2m) ] * δ(c_i, c_j)
Where m is the total number of edges, A_ij is the adjacency matrix, k_i is the degree of node i, and δ(c_i, c_j) is 1 if nodes i and j are in the same community and 0 otherwise. A modularity value of 0 means the partition is no better than random; values approaching 1 indicate strong community structure. In practice, values above 0.3 are considered meaningful.
Community detection is unsupervised: there are no ground-truth labels during optimization. This means evaluation is inherently harder than supervised classification, and the number of communities is typically not fixed in advance.
Algorithm Families
Modularity optimization methods (Louvain, Leiden) start from singleton communities and iteratively merge nodes or communities to increase modularity. They are fast in practice — Louvain runs in roughly O(n log n) on sparse graphs — and produce hierarchical community structures. The main weakness is that modularity has a resolution limit: very small communities inside large graphs may be merged into larger ones even if they are structurally distinct.
Divisive methods (Girvan-Newman) work in reverse: they start with the full graph and iteratively remove the edge with the highest betweenness centrality. Removing the bridge between communities first reveals community structure progressively. Girvan-Newman is computationally expensive — O(m * n) per step — making it impractical for graphs with more than a few thousand edges.
Spectral methods use the eigenvalues and eigenvectors of the graph Laplacian. The second-smallest eigenvalue (the Fiedler value) and its corresponding eigenvector (the Fiedler vector) encode how the graph splits at its weakest cut. Spectral clustering applies k-means to a low-dimensional embedding derived from the top-k eigenvectors. This approach is principled but requires specifying the number of communities in advance and computing eigenvectors, which is O(n^2) or O(n^3) depending on the implementation.
Label propagation methods assign each node a random label and iteratively update each node to the most common label among its neighbors. Convergence is fast but non-deterministic, and results can vary significantly between runs on the same graph.
TGraphX Community Detection: Basic Usage
The tgraphx.mining.communities module provides a unified interface across these algorithms:
import torch
from tgraphx import Graph
from tgraphx.mining.communities import detect_communities
# Build a simple graph
edge_index = torch.tensor([
[0, 1, 2, 3, 4, 5, 0, 3],
[1, 2, 0, 4, 5, 3, 3, 6],
], dtype=torch.long)
g = Graph(
node_features=torch.randn(7, 16),
edge_index=edge_index,
)
# Louvain method (default)
communities = detect_communities(g, method="louvain")
print(communities)
# Returns a list of sets, e.g. [{0,1,2}, {3,4,5,6}]
Each detected community is a Python set of node indices. The number of communities is determined automatically by the algorithm.
Applying Multiple Methods and Comparing
from tgraphx.mining.communities import detect_communities, modularity_score
methods = ["louvain", "label_propagation", "spectral"]
for method in methods:
if method == "spectral":
# Spectral requires specifying k
comms = detect_communities(g, method=method, n_communities=2)
else:
comms = detect_communities(g, method=method)
score = modularity_score(g, comms)
print(f"{method}: {len(comms)} communities, modularity = {score:.4f}")
The modularity_score function takes the graph and a community partition and returns Q. This allows direct comparison between methods on the same graph. A method that produces a higher modularity is not necessarily better — it may be overfitting the resolution limit or finding communities that are artifacts of degree heterogeneity rather than genuine structure.
Spectral Community Detection
For spectral clustering, the module computes the normalized Laplacian and uses its eigenvectors as a low-dimensional node embedding. You can also access the spectral analysis tools directly from tgraphx.mining.spectral:
from tgraphx.mining.spectral import compute_laplacian_eigenvectors
# Get the top-4 eigenvectors of the normalized Laplacian
eigenvalues, eigenvectors = compute_laplacian_eigenvectors(
g, k=4, normalization="symmetric"
)
print(eigenvalues.shape) # [4]
print(eigenvectors.shape) # [N, 4]
# Use these as node embeddings for downstream k-means or GNN input
The resulting eigenvectors can be used directly as node features in a GNN. This is a classical connection between spectral graph theory and modern GNN theory: spectral GNNs approximate polynomial functions of the graph Laplacian, and the eigenvectors are the natural basis for those polynomials.
Social Network Use Case
Community detection is most intuitive on social networks. Consider a graph where nodes are users and edges represent mutual connections. Communities correspond to friend groups, professional circles, or interest-based clusters:
import torch
from tgraphx import Graph
from tgraphx.mining.communities import detect_communities, modularity_score
# Simulated social graph: 100 users, 400 edges
num_nodes = 100
# In practice, load real edge_index from your data source
edge_index = torch.stack([
torch.randint(0, num_nodes, (400,)),
torch.randint(0, num_nodes, (400,)),
])
# Remove self-loops
mask = edge_index[0] != edge_index[1]
edge_index = edge_index[:, mask]
social_graph = Graph(
node_features=torch.eye(num_nodes), # identity features as placeholder
edge_index=edge_index,
)
communities = detect_communities(social_graph, method="louvain")
q = modularity_score(social_graph, communities)
print(f"Found {len(communities)} communities, modularity = {q:.4f}")
for i, c in enumerate(communities):
print(f" Community {i}: {len(c)} members")
Evaluating with Ground-Truth Labels
When ground-truth community labels are available (as in citation network benchmarks), you can measure the quality of detected communities using Normalized Mutual Information (NMI):
from tgraphx.mining.communities import normalized_mutual_information
# ground_truth: list of sets (true communities)
# detected: list of sets (algorithm output)
nmi = normalized_mutual_information(ground_truth, detected)
print(f"NMI: {nmi:.4f}")
# 1.0 = perfect recovery, 0.0 = no better than random
NMI is bounded between 0 and 1 and is symmetric: NMI(A, B) == NMI(B, A). It accounts for the fact that community labels are permutation-equivalent — detecting the same structure with different label assignments should not be penalized.
For the special case of overlapping communities (where nodes can belong to multiple groups), NMI has extensions but the standard implementation in TGraphX assumes non-overlapping partitions.
Using Community Structure as Graph Features
Detected communities can feed back into a GNN as additional node features. A common pattern is to one-hot encode community membership and concatenate it with existing node features:
import torch
import torch.nn.functional as F
from tgraphx import Graph
from tgraphx.mining.communities import detect_communities
communities = detect_communities(g, method="louvain")
# Build community membership tensor
num_nodes = g.node_features.shape[0]
num_comms = len(communities)
membership = torch.zeros(num_nodes, dtype=torch.long)
for comm_idx, comm in enumerate(communities):
for node in comm:
membership[node] = comm_idx
# One-hot encode and concatenate
comm_onehot = F.one_hot(membership, num_classes=num_comms).float()
augmented_features = torch.cat([g.node_features, comm_onehot], dim=1)
g_augmented = Graph(
node_features=augmented_features,
edge_index=g.edge_index,
)
This is one way community detection and GNNs interact in a hybrid pipeline: structural analysis provides soft supervision signals that improve learned representations.
Limitations and Honest Notes
Modularity has a resolution limit. Communities smaller than roughly sqrt(m) nodes tend to be absorbed into larger communities during modularity optimization. If you expect fine-grained clusters in a large graph, Louvain and similar methods may not find them.
Label propagation is non-deterministic. Running the same algorithm twice on the same graph with different random seeds can produce different community partitions. Results should be reported with multiple runs or a fixed seed via tgraphx.reproducibility.
Girvan-Newman is impractical beyond ~5,000 edges. The betweenness recalculation after each removal dominates runtime. Do not use it as a general-purpose method.
Ground-truth communities are rarely available. Most real-world community detection is unsupervised. Modularity and NMI are proxies, not ground truth. High modularity does not guarantee that communities are semantically meaningful.
TGraphX community detection works on unweighted graphs by default. For weighted graphs, edge weights can be passed but behavior varies by method — verify that the method you select supports weighted edges before interpreting results.
For related structural analysis tools, see the graph mining overview and the link prediction scoring guide.
Community Detection vs GNN-Based Approaches
It is worth situating community detection in the broader graph learning landscape. Classical community detection (Louvain, spectral, label propagation) is unsupervised: it finds structure without any labels. This is powerful when you have a new graph and no training data.
GNN-based approaches, on the other hand, require labeled training data and learn to distinguish classes through supervision. For node classification tasks where ground-truth labels exist, a GNN with proper training will almost always outperform a community detection followed by a labeling rule. The appropriate question is not which is better in general, but which is appropriate for your task.
Community detection fits when:
- You have no labels and need to explore graph structure
- You want interpretable structural groupings, not learned embeddings
- Your task is discovery rather than prediction (e.g., finding cohesive user groups in a new social network)
- Computational budget is tight and the graph changes frequently (re-running Louvain is fast; retraining a GNN is not)
GNNs fit when:
- You have labeled examples and want to predict new labels
- Node features are informative and should influence the clustering
- You need to capture multi-hop structural patterns, not just immediate neighborhoods
TGraphX supports both approaches, and the two can be combined in the hybrid pipeline described in the "Using Community Structure as Graph Features" section above.
What This Article Builds On
This article assumes basic familiarity with TGraphX Graph objects. Community detection operates on the structural level and does not require node features to be meaningful — you can run detect_communities on a graph with placeholder features. However, for downstream GNN training that uses detected communities, feature quality matters. The shape-aware validation guide covers how to validate feature consistency before training.
For spectral analysis tools used internally by the spectral clustering method, see the graph spectral analysis article. For the broader context of when graph mining fits versus GNN message passing, see the articles hub.
Frequently Asked Questions
How many communities does Louvain find? The number of communities is determined automatically by maximizing modularity. It typically produces between 2 and O(sqrt(n)) communities on real-world graphs. You cannot directly specify the number; use spectral clustering if you need a fixed-k partition.
Does community detection work on directed graphs? The algorithms in TGraphX's mining.communities module operate on undirected graphs by default. For directed graphs, symmetrize the adjacency matrix first, or use algorithms specifically designed for directed community detection (not currently in scope for this module).
What is the Fiedler vector and is it available in TGraphX? Yes. tgraphx.mining.spectral.compute_laplacian_eigenvectors(g, k=2) returns the two smallest eigenvalues and their eigenvectors. The second eigenvector (corresponding to the second-smallest eigenvalue, the Fiedler value) gives the classic spectral bipartition.
Can detected communities overlap? The current implementation assumes non-overlapping (hard) communities. Overlapping community detection (as in the BIGCLAM or ego-splitting algorithms) is not in the current module.
How do I pick between Louvain and label propagation? Use Louvain when you want stable, reproducible results and are willing to pay slightly higher computational cost. Use label propagation when you want a fast rough estimate and understand that results will vary between runs.