Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on -cliques, i.e. complete subgraphs on nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called -diamonds and defined as cliques of size with one missing edge. We first provide a sequential algorithm that, in time, counts and lists all the -diamonds in large graphs, for any constant ⁠. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for -cliques. The running time is optimal on dense graphs and larger than -clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors.

From Stars to Diamonds: Counting and Listing Almost Complete Subgraphs in Large Networks / Finocchi, Irene; Leon Garcia, Renan; Sinaimeri, Blerina. - In: COMPUTER JOURNAL. - ISSN 1460-2067. - (In corso di stampa), pp. 1-11. [10.1093/comjnl/bxad129]

From Stars to Diamonds: Counting and Listing Almost Complete Subgraphs in Large Networks

Irene Finocchi
;
Blerina Sinaimeri
In corso di stampa

Abstract

Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on -cliques, i.e. complete subgraphs on nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called -diamonds and defined as cliques of size with one missing edge. We first provide a sequential algorithm that, in time, counts and lists all the -diamonds in large graphs, for any constant ⁠. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for -cliques. The running time is optimal on dense graphs and larger than -clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors.
In corso di stampa
Network analysis, community detection, MapReduce
From Stars to Diamonds: Counting and Listing Almost Complete Subgraphs in Large Networks / Finocchi, Irene; Leon Garcia, Renan; Sinaimeri, Blerina. - In: COMPUTER JOURNAL. - ISSN 1460-2067. - (In corso di stampa), pp. 1-11. [10.1093/comjnl/bxad129]
File in questo prodotto:
File Dimensione Formato  
ComputerJournalProof-bxad129.pdf

Solo gestori archivio

Descrizione: Proof (accepted November 2023)
Tipologia: Documento in Pre-print
Licenza: Tutti i diritti riservati
Dimensione 1.2 MB
Formato Adobe PDF
1.2 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

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: https://hdl.handle.net/11385/235399
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact