Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Dense Subgraphs in Biological Networks
verfasst von : Mohammad Mehdi Hosseinzadeh
Erschienen in: SOFSEM 2020: Theory and Practice of Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A fundamental problem in analysing biological networks is the identification of dense subgraphs, since they are considered to be related to relevant parts of networks, like communities. Many contributions have been focused mainly in computing a single dense subgraph, but in many applications we are interested in finding a set of dense, possibly overlapping, subgraphs. In this paper we consider the Top-k-Overlapping Densest Subgraphs problem, that aims at finding a set of k dense subgraphs, for some integer \(k \ge 1\), that maximize an objective function that consists of the density of the subgraphs and the distance among them. We design a new heuristic for the Top-k-Overlapping Densest Subgraphs and we present an experimental analysis that compares our heuristic with an approximation algorithm developed for Top-k-Overlapping Densest Subgraphs (called DOS) on biological networks. The experimental result shows that our heuristic provides solutions that are denser than those computed by DOS, while the solutions computed by DOS have a greater distance. As for time-complexity, the DOS algorithm is much faster than our method.