The problem of finding the densest subgraph in a given graph has several real-world applications, particularly in areas like social network analysis, protein, and gene networks. Depending on the application, finding dense subgraphs can be used to determine regions of high importance, similar characteristics, or enhanced interaction. The densest subgraph extraction problem is fundamentally a non-linear optimization problem. Nevertheless, it can be solved in polynomial time by an exact algorithm based on iteratively solving a series of max-flow subproblems. Despite its polynomial-time complexity, the computing time required by exact algorithms on very large graphs could be prohibitive. Thus, to approach graphs with millions of vertices and edges, one has to resort to heuristic algorithms. We provide an efficient implementation of a greedy heuristic from the literature that is extremely fast and has some nice theoretical properties. We also introduce a new heuristic algorithm that is built on top of the greedy and the exact methods. An extensive computational study is presented to evaluate the performance of various algorithms on a benchmark composed of 86 instances taken from the literature and real world. This analysis shows that the proposed heuristic algorithm is very effective on a large number of test instances, often providing either the optimal solution or a near-optimal solution within short computing times.

In search of dense subgraphs: How good is greedy peeling?

Gudapati N. V. C.;Malaguti E.
;
Monaci M.
2021

Abstract

The problem of finding the densest subgraph in a given graph has several real-world applications, particularly in areas like social network analysis, protein, and gene networks. Depending on the application, finding dense subgraphs can be used to determine regions of high importance, similar characteristics, or enhanced interaction. The densest subgraph extraction problem is fundamentally a non-linear optimization problem. Nevertheless, it can be solved in polynomial time by an exact algorithm based on iteratively solving a series of max-flow subproblems. Despite its polynomial-time complexity, the computing time required by exact algorithms on very large graphs could be prohibitive. Thus, to approach graphs with millions of vertices and edges, one has to resort to heuristic algorithms. We provide an efficient implementation of a greedy heuristic from the literature that is extremely fast and has some nice theoretical properties. We also introduce a new heuristic algorithm that is built on top of the greedy and the exact methods. An extensive computational study is presented to evaluate the performance of various algorithms on a benchmark composed of 86 instances taken from the literature and real world. This analysis shows that the proposed heuristic algorithm is very effective on a large number of test instances, often providing either the optimal solution or a near-optimal solution within short computing times.
Gudapati N.V.C.; Malaguti E.; Monaci M.
File in questo prodotto:
File Dimensione Formato  
densest-Networks.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 710.39 kB
Formato Adobe PDF
710.39 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/850095
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact