Hypergraph Change Point Detection using Adapted Cardinality-Based Gadgets: Applications in Dynamic Legal Structures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916436431077376 |
|---|---|
| author | Matsumoto, Hiroki Yoshida, Takahiro Kondo, Ryoma Hisano, Ryohei |
| author_facet | Matsumoto, Hiroki Yoshida, Takahiro Kondo, Ryoma Hisano, Ryohei |
| contents | Hypergraphs provide a robust framework for modeling complex systems with higher-order interactions. However, analyzing them in dynamic settings presents significant computational challenges. To address this, we introduce a novel method that adapts the cardinality-based gadget to convert hypergraphs into strongly connected weighted directed graphs, complemented by a symmetrized combinatorial Laplacian. We demonstrate that the harmonic mean of the conductance and edge expansion of the original hypergraph can be upper-bounded by the conductance of the transformed directed graph, effectively preserving crucial cut information. Additionally, we analyze how the resulting Laplacian relates to that derived from the star expansion. Our approach was validated through change point detection experiments on both synthetic and real datasets, showing superior performance over clique and star expansions in maintaining spectral information in dynamic settings. Finally, we applied our method to analyze a dynamic legal hypergraph constructed from extensive United States court opinion data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08106 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hypergraph Change Point Detection using Adapted Cardinality-Based Gadgets: Applications in Dynamic Legal Structures Matsumoto, Hiroki Yoshida, Takahiro Kondo, Ryoma Hisano, Ryohei Social and Information Networks Hypergraphs provide a robust framework for modeling complex systems with higher-order interactions. However, analyzing them in dynamic settings presents significant computational challenges. To address this, we introduce a novel method that adapts the cardinality-based gadget to convert hypergraphs into strongly connected weighted directed graphs, complemented by a symmetrized combinatorial Laplacian. We demonstrate that the harmonic mean of the conductance and edge expansion of the original hypergraph can be upper-bounded by the conductance of the transformed directed graph, effectively preserving crucial cut information. Additionally, we analyze how the resulting Laplacian relates to that derived from the star expansion. Our approach was validated through change point detection experiments on both synthetic and real datasets, showing superior performance over clique and star expansions in maintaining spectral information in dynamic settings. Finally, we applied our method to analyze a dynamic legal hypergraph constructed from extensive United States court opinion data. |
| title | Hypergraph Change Point Detection using Adapted Cardinality-Based Gadgets: Applications in Dynamic Legal Structures |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2409.08106 |