Forward--Backward Green Cosine Geometry for Directed Community Detection and Overlap Expansion
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915979363090432 |
|---|---|
| author | Do, Duy Hieu |
| author_facet | Do, Duy Hieu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03318 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Forward--Backward Green Cosine Geometry for Directed Community Detection and Overlap Expansion Do, Duy Hieu Social and Information Networks 05C82, 68R10, 62H30 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. |
| title | Forward--Backward Green Cosine Geometry for Directed Community Detection and Overlap Expansion |
| topic | Social and Information Networks 05C82, 68R10, 62H30 |
| url | https://arxiv.org/abs/2605.03318 |