Interactions among objects are usually modelled using graphs. Nevertheless, these relations may change over time and there exist different kind of relations among object that need to be integrated. We introduce a new network model, called temporal dual networks, to deal with interactions that changes over time and to integrate information coming from two different networks. We consider a fundamental problem in graph mining, that is finding densest subgraphs on this new model. We propose an approach based on both network alignment and dynamic programming. Given two temporal graphs, we obtain a dual temporal graph via alignment and then we look for densest subgraphs in the obtained graph. We present a dynamic programming algorithm to solve the problem in polynomial time. Since this algorithm is not applicable even to medium size network, we present a heuristic that is based on (1) constraining the dynamic programming to consider only bounded temporal graphs and (2) a local search procedure. We show that our method is able to return optimal or near optimal solution even for temporal graphs having 10,000 vertices and 10,000 timestamps.
(2023). Integrating Temporal Graphs via Dual Networks: Dense Graph Discovery . Retrieved from https://hdl.handle.net/10446/262332
Integrating Temporal Graphs via Dual Networks: Dense Graph Discovery
Dondi, Riccardo;
2023-01-01
Abstract
Interactions among objects are usually modelled using graphs. Nevertheless, these relations may change over time and there exist different kind of relations among object that need to be integrated. We introduce a new network model, called temporal dual networks, to deal with interactions that changes over time and to integrate information coming from two different networks. We consider a fundamental problem in graph mining, that is finding densest subgraphs on this new model. We propose an approach based on both network alignment and dynamic programming. Given two temporal graphs, we obtain a dual temporal graph via alignment and then we look for densest subgraphs in the obtained graph. We present a dynamic programming algorithm to solve the problem in polynomial time. Since this algorithm is not applicable even to medium size network, we present a heuristic that is based on (1) constraining the dynamic programming to consider only bounded temporal graphs and (2) a local search procedure. We show that our method is able to return optimal or near optimal solution even for temporal graphs having 10,000 vertices and 10,000 timestamps.File | Dimensione del file | Formato | |
---|---|---|---|
Dondi_ComplexNetworks202223.pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
348.1 kB
Formato
Adobe PDF
|
348.1 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo