Louvain Algorithm for Community Detection in Anti‑Fraud Systems

With the rapid development of internet technology, users enjoy its benefits while malicious actors (black‑market activities) threaten the healthy growth of the web through coupon grabbing, fake orders, traffic/follower inflation, fraud, and other illicit behaviors. Anti‑fraud systems serve as the main force to combat these threats, ensuring objective search/feed results and protecting advertisers' legitimate rights.

The Louvain algorithm, a classic community‑detection method, has become a powerful tool for uncovering hidden small‑scale collusive groups in modern anti‑fraud scenarios. Below is a detailed introduction.

1. Overview of Louvain

The algorithm aims to maximize modularity, a metric that evaluates the quality of a graph partition. Higher modularity indicates dense intra‑community connections and sparse inter‑community links.

Modularity definition

Modularity is defined by the following formula:

where the symbols represent:

Total edge weight sum:

Weight between nodes i and j :

Sum of weights of edges incident to node i :

Community assignment of node i :

Indicator function (1 if x and y belong to the same community, 0 otherwise):

After algebraic manipulation, the modularity gain when moving a node from community D to community C can be expressed as:

2. Louvain Algorithm Steps

Initialization : Treat each node as an individual community.

Phase 1 – Node Merging : For every node, compute the modularity gain of moving it to each neighboring community and relocate it to the community that yields the highest positive gain. This phase repeats until no further gain is possible.

Phase 2 – Community Aggregation : Collapse each community into a single super‑node, preserving the total weight of edges between the new super‑nodes. The resulting graph is then fed back into Phase 1. The process iterates until the graph structure stabilizes.

The overall computational complexity is approximately O(n log n) on average, assuming the number of nodes roughly halves each iteration.

3. Advantages and Disadvantages

Advantages

Low average time complexity, enabling fast computation.

Supports weighted edges, allowing richer graph representations.

Produces a hierarchical community structure, which can be constrained by community size or custom attributes.

Disadvantages

Requires multiple iterations; not suitable for streaming systems.

Worst‑case time complexity can be high for pathological graphs.

When node degrees are highly uneven, the second term of the modularity definition may introduce negative interference.

4. Optimization Ideas

The modularity maximization problem is NP‑hard. While Louvain provides a greedy approximation, further improvements include:

Prioritizing edge merges based on edge attributes (e.g., edge betweenness) to eliminate multiple iterations and adapt to streaming pipelines.

Reducing the weight of the second term in the modularity formula when community size distribution is highly skewed.

5. Application in Anti‑Fraud

In e‑commerce risk control, a small number of stores create fake user‑experience scores or manipulate recommendation algorithms by forming collusive groups that generate fraudulent orders and reviews. By modeling the relationships among accounts and transactions as a weighted graph and applying the Louvain algorithm, hierarchical community structures are uncovered, enabling precise identification of fraudulent groups, interception of malicious orders, and cooperation with legal teams for arrests.

Community detection results (risk accounts and transaction orders) are illustrated below:

6. References

[1] Original paper: https://arxiv.org/abs/0803.0476

[2] Stanford lecture slides: http://web.stanford.edu/class/cs224w/slides/14-communities.pdf

[3] Louvain algorithm article: https://towardsdatascience.com/louvain-algorithm-93fde589f58c