Multiscale Local Community Detection: Breaking the Single-Scale Barrier

TL;DR

In social networks, a single node often belongs to multiple layers of communities (e.g., a research lab, a department, and an entire scientific field). Existing local detection methods usually only find one of these. This paper introduces LQ, a new local modularity metric, and an algorithm that "zooms out" from a starting node to discover meaningful communities at multiple scales without ever needing the full graph's data.

Context: Why "Local" and Why "Multiscale"?

Most community detection research assumes we have the whole map of the network. In reality, we often only see a node's immediate neighbors (like on a private social network or a massive web-scale graph).

The Resolution Limit is a notorious problem where modularity-based methods fail to find small communities in large networks. In the local context, the problem is reversed: methods get stuck in a "single scale" and can't see the bigger picture surrounding a node.

Methodology: The Logic of LQ

The authors propose a local modularity $LQ$ defined as: $LQ=\frac{e_c}{S}-(\frac{d_c}{2S}{)}^2$

Where:

• $e_c$: Internal edges in the local community.
• $d_c$: Total degree of nodes in the local community.
• $S$: The number of edges associated with the local community nodes.

The "Look Forward" Mechanism

The core innovation is Algorithm 2 (ExpandCommunityC). When the algorithm reaches a point where no more nodes increase modularity (the resolution limit), it doesn't stop. Instead, it temporarily increases the virtual edge count ($S$) to "relax" the threshold, allowing the community to jump over sparse boundaries to find the next, larger scale of organization.

Fig 1. Illustration of Core, Boundary (B), and Neighbors (N) in a local community structure.

Experimental Proof

The researchers tested the algorithm on the Dolphins social network and LFR synthetic networks.

One of the most striking results is shown in the multi-step detection of the Dolphins dataset. Starting from node 25, the algorithm progressively identifies a tight-knit group, then a larger functional cluster, and finally the broad social affiliation.

Fig 2. The algorithm successfully "zooms out" from the 25th node in the Dolphins dataset to identify three distinct scales of community.

Performance Comparison

As shown in the table below, while traditional methods (R and M) stop after Scale 1, the proposed LQ method continues to Scales 2, 3, and 4 with high F-scores.

Table 1. Quantitative comparison showing LQ's ability to maintain high precision and recall across multiple scales where others provide no data.

Critical Insight: The Equivalence Theorem

A significant contribution of this paper is the mathematical proof that LQ is equivalent to the classic M and R modularities under specific conditions (when core nodes are empty). This provides a theoretical bridge between existing single-scale metrics and this new multiscale framework, proving that $LQ$ is a robust generalization of previous work.

Conclusion & Future Work

This work effectively solves the "tunnel vision" of local community detection. By allowing the local parameter $S$ to adjust dynamically, the authors have created a "lens" that can refocus on different social layers.

Limitations: The algorithm's speed depends on the community density (Complexity $O(m^{2}d)$). For extremely dense, massive communities, the computational cost of the merging step might scale poorly. Future research could focus on optimizing this for billion-node graphs.