Networks are largely used for modelling and analysing data and relations among them. Recently, it has been shown that the use of a single network may not be the optimal choice, since a single network may misses some aspects. Consequently, it has been proposed to use a pair of networks to better model all the aspects, and the main approach is referred to as dual networks (DNs). A DN consists of pair of related graphs (one weighted, the other unweighted) that share the same set of vertices and two different edge sets. It is often interesting to extract common subgraphs in the two networks that are dense in the conceptual network and connected in the physical one. The simplest instance of this problem is finding a common densest connected subgraph (DCS), while here we focus on 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. We formalise the problem and then 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). Top-k Connected Overlapping Densest Subgraphs in Dual Networks . Retrieved from http://hdl.handle.net/10446/200850

Top-k Connected Overlapping Densest Subgraphs in Dual Networks

Dondi, R.;Hosseinzadeh, M. M.
2021-01-01

Abstract

Networks are largely used for modelling and analysing data and relations among them. Recently, it has been shown that the use of a single network may not be the optimal choice, since a single network may misses some aspects. Consequently, it has been proposed to use a pair of networks to better model all the aspects, and the main approach is referred to as dual networks (DNs). A DN consists of pair of related graphs (one weighted, the other unweighted) that share the same set of vertices and two different edge sets. It is often interesting to extract common subgraphs in the two networks that are dense in the conceptual network and connected in the physical one. The simplest instance of this problem is finding a common densest connected subgraph (DCS), while here we focus on 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. We formalise the problem and then 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
Dondi, Riccardo; Guzzi, P. H.; Hosseinzadeh, Mohammad Mehdi
File allegato/i alla scheda:
File Dimensione del file Formato  
ComplexNetworks202021.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 410.77 kB
Formato Adobe PDF
410.77 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/200850
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact