Forward--Backward Green Cosine Geometry for Directed Community Detection and Overlap Expansion
For researchers working on community detection in directed graphs, this work provides a novel geometric framework that addresses the challenge of non-reversible diffusion and direction-dependent roles.
The paper develops a Green-based cosine geometry for directed community detection and overlap expansion, using forward-backward Green coordinates to handle edge asymmetry. Experiments show the method improves over raw hitting-time variants and is competitive with directed spectral and flow-based baselines on synthetic benchmarks.
Community detection in directed graphs is challenging because edge asymmetry induces non-reversible diffusion, direction-dependent accessibility, and distinct source and target roles. This paper develops a Green-based cosine geometry for directed community detection and for expanding a disjoint partition into an overlapping cover. The key observation is that hitting-time information is natural for directed graphs, but raw hitting-time vectors are not well suited for cosine comparison: they contain a source-independent stationary baseline, whereas cosine similarity is not translation-invariant. We therefore replace raw hitting-time profiles by centered Green profiles of the directed random walk and use the diffusive part of the truncated Green profile, excluding the time-zero self-spike. To account for asymmetry, we concatenate the Green profile of the original walk with the corresponding profile on the edge-reversed graph, yielding forward--backward Green coordinates. The framework gives two algorithms. Di-Green-FB-cosine-KMeans clusters vertices in the Green cosine space to obtain a disjoint directed partition. Di-Green-FB-Cosine Overlap expands an initial partition into an overlapping cover using a community-adaptive cosine rule. The initial partition can be supplied by any disjoint method; in the main pipeline it is produced by Di-Green-FB-cosine-KMeans. Experiments on synthetic directed benchmarks show that the proposed geometry improves over raw hitting-time cosine variants and is competitive with directed spectral and flow-based baselines. Real-network experiments, evaluated by directed modularity as an internal quality measure, indicate that the same geometry produces coherent directed partitions. Synthetic overlap experiments further show that the method recovers additional memberships effectively, especially in moderately and weakly separated directed networks.