💰 quantitative finance

Selecting representative community partitions under modularity degeneracy: the STAR method

The paper introduces the STAR method, a simple, model-agnostic post-processing technique that selects a representative community partition from degenerate modularity solutions by identifying shared structural features, offering a robust and broadly applicable alternative to complex consensus clustering methods for both positive and negative weighted networks.

Original authors: Francesca Grassetti, Rossana Mastrandrea

Published 2026-02-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Francesca Grassetti, Rossana Mastrandrea

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive, chaotic party where thousands of people are mingling. Your goal is to figure out who belongs to which "clique" or friend group. This is what scientists call Community Detection in complex networks.

The most popular tool for doing this is called Modularity Maximization. Think of it as a super-smart but slightly confused DJ who tries to group people based on how much they talk to each other. The DJ wants to maximize the "noise" inside the groups and minimize the noise between them.

However, there's a big problem: The Degeneracy Trap.

The Problem: The "Too Many Perfect Answers" Dilemma

Imagine the DJ runs the party 100 times. Every time, they come up with a grouping that is almost perfect. In fact, all 100 groupings have nearly the exact same "score" of how well they worked.

But here's the catch: The groups are completely different.

In Run #1, Alice is with Bob and Charlie.
In Run #2, Alice is with Dave and Eve.
In Run #3, Alice is with Frank and Grace.

All three scenarios have the same "perfect score." This is called degeneracy. It's like having 1,000 different maps of a city that all claim to be the "shortest route" to the same destination, but they take completely different roads. Which one do you trust? If you just pick the one with the highest score, you might get a map that looks mathematically perfect but makes no sense in the real world (like a route that goes through a river).

The Solution: The STAR Method

The authors of this paper propose a new, simple way to solve this. They call it STAR (Similarity-based Top ARI Representative).

Here is the analogy:

The Old Way (Consensus Clustering):
Imagine you ask 100 people to draw the party groups on a whiteboard. Then, you take a giant eraser and try to blend all 100 drawings into one "average" drawing. This is hard work, requires special software, and sometimes the final drawing looks muddy and blurry because you erased too much detail. Also, this method breaks if the party has "negative" relationships (people who hate each other).

The STAR Way (The "Popular Vote" Approach):
Instead of blending the drawings, STAR acts like a social butterfly.

It takes all 100 different groupings the DJ made.
It asks: "Which of these 100 groupings is the most popular?"
It looks for the grouping that is most similar to all the others. It's the "center of gravity" of the solutions.
If there's a tie, it picks the one that has the highest score.

Why is this better?

It's Simple: You don't need to blend anything or run complex math. You just look for the "most normal" answer among the crowd.
It's Robust: It finds the group structure that keeps showing up, which is usually the most reliable truth.
It Handles "Negative" Relationships: This is a huge deal. Many real-world networks (like stock markets or social media) have "negative" links (people who dislike each other or stocks that move in opposite directions). The old "blending" methods break when you introduce negativity. STAR works perfectly with both positive and negative links.

Real-World Examples from the Paper

The authors tested this on two very different "parties":

The World Trade Web (Countries):
- They looked at how countries trade with each other.
- The "highest score" method grouped countries in a way that looked mathematically neat but geographically weird (e.g., lumping very different African nations together just because they traded a little bit).
- The STAR method grouped them by actual regions (North America, Europe, South America), which made much more sense to economists and matched real-world trade blocs.
The Stock Market (FTSE 100):
- They looked at how 93 companies move together.
- The "highest score" method split the companies into messy, confusing groups.
- The STAR method grouped them by industry sectors (Finance, Tech, Healthcare), which is exactly how investors actually think about the market.

The Takeaway

When you are trying to find patterns in complex data, chasing the single "perfect" mathematical answer can lead you astray because there are often thousands of "perfect" answers that look nothing like each other.

Instead of hunting for the single best answer, STAR suggests you find the answer that everyone else agrees on. It's the "wisdom of the crowd" approach to data science: Don't look for the loudest voice; look for the one that sounds most like the chorus.

It's a simple, free, and powerful tool that works even when the data is messy, negative, or confusing.

1. Problem Statement

Community detection (CD) via modularity maximization is a standard approach for identifying mesoscale structures in complex networks. However, the modularity function suffers from a highly degenerate optimization landscape.

Degeneracy: A vast number of structurally distinct partitions can achieve modularity values arbitrarily close to the global maximum.
Instability: Small variations in the network or the optimization algorithm (e.g., stochasticity in the Louvain method) lead to different "optimal" partitions that are nearly indistinguishable in terms of the objective function but structurally different.
Limitations of Existing Solutions:
- Consensus Clustering (CC): While effective at stabilizing results by merging an ensemble of partitions, it is computationally intensive, requires constructing auxiliary consensus matrices, and typically fails on signed networks (networks with negative edge weights), which are common in finance, neuroscience, and social sciences.
- Direct Maximization: Simply selecting the partition with the absolute highest modularity often yields unstable or uninterpretable results due to the ruggedness of the modularity landscape.

The authors aim to develop a simple, model-agnostic, post-processing method that selects a single representative partition from an ensemble of high-modularity solutions, capable of handling both positive and negative edge weights.

2. Methodology: The STAR Method

The authors propose the Similarity-based Top ARI Representative (STAR) method. It is a post-processing step applied after running a modularity-based algorithm (e.g., Louvain) multiple times.

Key Steps:

Ensemble Generation: Run the modularity maximization algorithm $T$ times on the graph $G$ to generate a set of candidate partitions $\sigma = \{\sigma_1, \dots, \sigma_T\}$ .
Similarity Calculation: Compute the pairwise similarity between all partitions in the ensemble using the Adjusted Rand Index (ARI).
- Why ARI? Unlike Normalized Mutual Information (NMI), ARI corrects for chance agreement, making it robust for comparing partitions with different numbers of clusters and sizes.
Similarity Network Construction: Construct a fully connected weighted network where:
- Nodes represent the $T$ partitions.
- Edge weights represent the ARI score between two partitions.
Strength Calculation: Calculate the "strength" ( $s_i$ ) of each partition node, defined as the sum of its edge weights (i.e., the average similarity to all other partitions in the ensemble).
$s_i = \sum_{j=1}^{T} \text{ARI}(\sigma_i, \sigma_j)$
Selection Criterion:
- Identify the partition(s) with the maximum strength (most representative of the ensemble).
- If multiple partitions share the maximum strength, select the one with the highest modularity value among them.

Key Characteristics:

Model-Agnostic: Works with any modularity-based algorithm.
Signed Network Compatibility: Since ARI relies on node co-assignment rather than edge weights directly, STAR works seamlessly with networks containing negative weights (correlation matrices, signed social networks).
Simplicity: Requires no additional optimization steps or external software packages beyond standard CD outputs.

3. Key Contributions

A Parsimonious Alternative to Consensus Clustering: STAR achieves results comparable to Consensus Clustering (CC) but through a significantly simpler procedure that avoids the construction of complex consensus matrices and additional optimization loops.
Extension to Signed Networks: The method overcomes a major limitation of standard CC techniques by naturally handling networks with both positive and negative edge weights, making it applicable to financial correlation networks and signed social networks.
Shift from Optimality to Representativeness: The paper argues that in degenerate landscapes, the "best" partition (global maximum) is often unstable. Instead, the goal should be to find the structurally central partition that captures the robust features shared across the ensemble.

4. Results

The authors validated STAR using synthetic benchmarks and real-world economic data.

A. Synthetic Benchmarks (LFR Graphs):

Setup: 100 LFR networks with varying mixing parameters ( $\mu$ ) to control community fuzziness.
Performance:
- Accuracy: STAR achieved Adjusted Rand Index (ARI) scores against the ground truth nearly identical to Consensus Clustering across all levels of mixing.
- Modularity: STAR maintained modularity values close to the global optimum, unlike CC which sometimes sacrificed modularity for stability.
- Robustness: The method remained effective even when the ensemble size was reduced from 150 to 50 runs, indicating it does not require massive computational overhead.
- Baseline Comparison: Selecting the partition with the absolute highest modularity or the most frequent partition resulted in significantly lower accuracy compared to STAR and CC.

B. Real-World Applications:

World Trade Web (WTW):
- Context: Directed, weighted network of 193 countries (2015).
- Finding: The STAR/Consensus partition identified geographically and economically coherent regions (e.g., distinct North American, European, and South American blocks).
- Contrast: The "Max-Modularity" partition merged heterogeneous African and Asian economies into large, less interpretable blocks, demonstrating that higher modularity does not guarantee economic interpretability.
FTSE 100 Stock Market:
- Context: Correlation network of 93 stocks with negative weights (making CC inapplicable).
- Finding: STAR identified 4 communities with clear sectoral alignment (e.g., grouping Financials, Industrials, and Defensive sectors coherently).
- Contrast: The Max-Modularity partition yielded 5 fragmented clusters with mixed sectors.
- Significance: This case proved STAR's unique ability to handle signed networks where standard consensus methods fail.

5. Significance and Implications

Practical Utility: STAR provides a "plug-and-play" tool for researchers dealing with modularity degeneracy, eliminating the need for complex consensus clustering pipelines.
Broad Applicability: By supporting signed networks, the method unlocks robust community detection for critical fields like financial risk management (correlation matrices), neuroscience (functional connectivity with inhibitory/excitatory links), and social science (signed trust/distrust networks).
Theoretical Insight: The paper reinforces the concept that in complex systems with degenerate optimization landscapes, structural stability and representativeness are more valuable metrics for community detection than the marginal pursuit of the global modularity maximum.

In conclusion, the STAR method offers a robust, computationally efficient, and versatile solution to the problem of selecting representative community structures, bridging the gap between theoretical optimality and practical interpretability in complex network analysis.