In this paper we develop simple and fast multicore parallel algorithms for counting the number of k-cliques in large undirected graphs, for any small constant k ≥ 4. Clique counting is an important problem in a variety of network analytics applications. Differently from existing solutions, which mainly target distributed memory settings (e.g., MapReduce), our algorithms work on off-the-shelf shared-memory multicore platforms. We assess the effectiveness of our approach through an extensive experimental analysis on a variety of real-world graphs, considering different clique sizes and scalability on different numbers of cores. The experimental results show that our parallel algorithms largely outperform the running times of highly optimized sequential solutions and gracefully scale to non-trivial values of k even on medium/large graphs. For instance, computing hundreds of billions of cliques for rather demanding Web graphs and social networks requires about 15 min on a 32-core machine. As a by-product of our experimental analysis, we also compute the exact number of k-cliques with at most 20 nodes in many real-world networks from the SNAP repository.

Counting cliques in parallel without a cluster: engineering a fork/join algorithm for shared-memory platforms / Coppa, Emilio; Finocchi, Irene; Leon Garcia, Renan. - In: INFORMATION SCIENCES. - ISSN 0020-0255. - 496:September(2019), pp. 553-571. [10.1016/j.ins.2018.07.018]

Counting cliques in parallel without a cluster: engineering a fork/join algorithm for shared-memory platforms

Irene Finocchi;
2019

Abstract

In this paper we develop simple and fast multicore parallel algorithms for counting the number of k-cliques in large undirected graphs, for any small constant k ≥ 4. Clique counting is an important problem in a variety of network analytics applications. Differently from existing solutions, which mainly target distributed memory settings (e.g., MapReduce), our algorithms work on off-the-shelf shared-memory multicore platforms. We assess the effectiveness of our approach through an extensive experimental analysis on a variety of real-world graphs, considering different clique sizes and scalability on different numbers of cores. The experimental results show that our parallel algorithms largely outperform the running times of highly optimized sequential solutions and gracefully scale to non-trivial values of k even on medium/large graphs. For instance, computing hundreds of billions of cliques for rather demanding Web graphs and social networks requires about 15 min on a 32-core machine. As a by-product of our experimental analysis, we also compute the exact number of k-cliques with at most 20 nodes in many real-world networks from the SNAP repository.
Algorithms; Social networking; triangle counting
Counting cliques in parallel without a cluster: engineering a fork/join algorithm for shared-memory platforms / Coppa, Emilio; Finocchi, Irene; Leon Garcia, Renan. - In: INFORMATION SCIENCES. - ISSN 0020-0255. - 496:September(2019), pp. 553-571. [10.1016/j.ins.2018.07.018]
File in questo prodotto:
File Dimensione Formato  
Coppa_Counting-cliques_2019.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 1.98 MB
Formato Adobe PDF
1.98 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/11385/192575
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact