The use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach.
(2021). A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks [journal article - articolo]. In APPLIED NETWORK SCIENCE. Retrieved from http://hdl.handle.net/10446/200860
Citazione: | (2021). A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks [journal article - articolo]. In APPLIED NETWORK SCIENCE. Retrieved from http://hdl.handle.net/10446/200860 | |
Titolo: | A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks | |
Tipologia specifica: | articolo | |
Tutti gli autori: | Dondi, Riccardo; Hosseinzadeh, Mohammad Mehdi; Guzzi, Pietro H. | |
Data di pubblicazione: | 2021 | |
Abstract (eng): | The use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach. | |
Rivista: | ||
Nelle collezioni: | 1.1.01 Articoli/Saggi in rivista - Journal Articles/Essays |
File allegato/i alla scheda:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Applied_Network_Science2021.pdf | publisher's version - versione editoriale | ![]() | Open AccessVisualizza/Apri |