Temporal network compression via network hashing
Abstract Pairwise temporal interactions between entities can be represented as temporal networks, which code the propagation of processes such as epidemic spreading or information cascades, evolving on top of them. The largest outcome of these processes is directly linked to the structure of the und...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2024-01-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s41109-023-00609-9 |
| _version_ | 1797350040195301376 |
|---|---|
| author | Rémi Vaudaine Pierre Borgnat Paulo Gonçalves Rémi Gribonval Márton Karsai |
| author_facet | Rémi Vaudaine Pierre Borgnat Paulo Gonçalves Rémi Gribonval Márton Karsai |
| author_sort | Rémi Vaudaine |
| collection | DOAJ |
| description | Abstract Pairwise temporal interactions between entities can be represented as temporal networks, which code the propagation of processes such as epidemic spreading or information cascades, evolving on top of them. The largest outcome of these processes is directly linked to the structure of the underlying network. Indeed, a node of a network at a given time cannot affect more nodes in the future than it can reach via time-respecting paths. This set of nodes reachable from a source defines an out-component, which identification is costly. In this paper, we propose an efficient matrix algorithm to tackle this issue and show that it outperforms other state-of-the-art methods. Secondly, we propose a hashing framework to coarsen large temporal networks into smaller proxies on which out-components are more easily estimated, and then recombined to obtain the initial components. Our graph hashing solution has implications in privacy respecting representation of temporal networks. |
| first_indexed | 2024-03-08T12:39:04Z |
| format | Article |
| id | doaj.art-1748671e14d2483bb36305150c37a966 |
| institution | Directory Open Access Journal |
| issn | 2364-8228 |
| language | English |
| last_indexed | 2024-03-08T12:39:04Z |
| publishDate | 2024-01-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj.art-1748671e14d2483bb36305150c37a9662024-01-21T12:13:54ZengSpringerOpenApplied Network Science2364-82282024-01-019111910.1007/s41109-023-00609-9Temporal network compression via network hashingRémi Vaudaine0Pierre Borgnat1Paulo Gonçalves2Rémi Gribonval3Márton Karsai4Univ Lyon, EnsL, UCBL, CNRS, Inria, LIPCNRS, Univ de Lyon, ENS de Lyon, Laboratoire de PhysiqueUniv Lyon, EnsL, UCBL, CNRS, Inria, LIPUniv Lyon, EnsL, UCBL, CNRS, Inria, LIPDepartment of Network and Data Science, Central European UniversityAbstract Pairwise temporal interactions between entities can be represented as temporal networks, which code the propagation of processes such as epidemic spreading or information cascades, evolving on top of them. The largest outcome of these processes is directly linked to the structure of the underlying network. Indeed, a node of a network at a given time cannot affect more nodes in the future than it can reach via time-respecting paths. This set of nodes reachable from a source defines an out-component, which identification is costly. In this paper, we propose an efficient matrix algorithm to tackle this issue and show that it outperforms other state-of-the-art methods. Secondly, we propose a hashing framework to coarsen large temporal networks into smaller proxies on which out-components are more easily estimated, and then recombined to obtain the initial components. Our graph hashing solution has implications in privacy respecting representation of temporal networks.https://doi.org/10.1007/s41109-023-00609-9Temporal networksOut-component calculationStreaming matrix algorithmsGraph hashing |
| spellingShingle | Rémi Vaudaine Pierre Borgnat Paulo Gonçalves Rémi Gribonval Márton Karsai Temporal network compression via network hashing Applied Network Science Temporal networks Out-component calculation Streaming matrix algorithms Graph hashing |
| title | Temporal network compression via network hashing |
| title_full | Temporal network compression via network hashing |
| title_fullStr | Temporal network compression via network hashing |
| title_full_unstemmed | Temporal network compression via network hashing |
| title_short | Temporal network compression via network hashing |
| title_sort | temporal network compression via network hashing |
| topic | Temporal networks Out-component calculation Streaming matrix algorithms Graph hashing |
| url | https://doi.org/10.1007/s41109-023-00609-9 |
| work_keys_str_mv | AT remivaudaine temporalnetworkcompressionvianetworkhashing AT pierreborgnat temporalnetworkcompressionvianetworkhashing AT paulogoncalves temporalnetworkcompressionvianetworkhashing AT remigribonval temporalnetworkcompressionvianetworkhashing AT martonkarsai temporalnetworkcompressionvianetworkhashing |