Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2509.14193 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914043086766080 |
|---|---|
| author | Diaz-Diaz, Fernando Devriendt, Karel Lambiotte, Renaud |
| author_facet | Diaz-Diaz, Fernando Devriendt, Karel Lambiotte, Renaud |
| contents | This article deals with the characterization and detection of community and faction structures in signed networks. We approach the study of these mesoscale structures through the lens of the Gremban expansion. This graph operation lifts a signed graph to a larger unsigned graph, and allows the extension of standard techniques from unsigned to signed graphs. We develop the combinatorial and algebraic properties of the Gremban expansion, with a focus on its inherent involutive symmetry. The main technical result is a bijective correspondence between symmetry-respecting cut-sets in the Gremban expansion, and regular cut-sets and frustration sets in the signed graph (i.e., the combinatorial structures that underlie communities and factions respectively). This result forms the basis for our new approach to community-faction detection in signed networks, which makes use of spectral clustering techniques that naturally respect the required symmetries. We demonstrate how this approach distinguishes the two mesoscale structures, how to generalize the approach to multi-way clustering and discuss connections to network dynamical systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14193 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gremban Expansion for Signed Networks: Algebraic and Combinatorial Foundations for Community-Faction Detection Diaz-Diaz, Fernando Devriendt, Karel Lambiotte, Renaud Discrete Mathematics Combinatorics Physics and Society G.2; I.5 This article deals with the characterization and detection of community and faction structures in signed networks. We approach the study of these mesoscale structures through the lens of the Gremban expansion. This graph operation lifts a signed graph to a larger unsigned graph, and allows the extension of standard techniques from unsigned to signed graphs. We develop the combinatorial and algebraic properties of the Gremban expansion, with a focus on its inherent involutive symmetry. The main technical result is a bijective correspondence between symmetry-respecting cut-sets in the Gremban expansion, and regular cut-sets and frustration sets in the signed graph (i.e., the combinatorial structures that underlie communities and factions respectively). This result forms the basis for our new approach to community-faction detection in signed networks, which makes use of spectral clustering techniques that naturally respect the required symmetries. We demonstrate how this approach distinguishes the two mesoscale structures, how to generalize the approach to multi-way clustering and discuss connections to network dynamical systems. |
| title | Gremban Expansion for Signed Networks: Algebraic and Combinatorial Foundations for Community-Faction Detection |
| topic | Discrete Mathematics Combinatorics Physics and Society G.2; I.5 |
| url | https://arxiv.org/abs/2509.14193 |