@inproceedings{5b2a663cd8374602aa8ce52ae5bbe1ce,
title = "Parallel Triangles and Squares Count for Multigraphs Using Vertex Covers",
abstract = "Triangles and squares count are widely-used graph analytic metrics providing insights into the connectivity of a graph. While the literature has focused on algorithms for global counts in simple graphs, this paper presents parallel algorithms for global and per-node triangle and square counts in large multigraphs. The algorithms have linear improvements in computational complexity as the number of cores increases. The triangle count algorithm has the same complexity as the best-known algorithm in the literature. The squares count algorithm has a lower execution time than previous methods. The proposed algorithms are evaluated on six real-world graphs and multigraphs, including protein-protein interaction graphs, knowledge graphs and large web graphs.",
keywords = "Count, Graph, Multigraph, Squares, Triangles",
author = "Luca Cappelletti and Tommaso Fontana and Oded Green and David Bader",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; 23rd International Conference on Computational Science, ICCS 2023 ; Conference date: 03-07-2023 Through 05-07-2023",
year = "2023",
doi = "10.1007/978-3-031-36027-5_50",
language = "English (US)",
isbn = "9783031360268",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "635--646",
editor = "Ji{\v r}{\'i} Miky{\v s}ka and {de Mulatier}, Cl{\'e}lia and Krzhizhanovskaya, {Valeria V.} and Sloot, {Peter M. A.} and Maciej Paszynski and Dongarra, {Jack J.}",
booktitle = "Computational Science – ICCS 2023 - 23rd International Conference, Proceedings",
address = "Germany",
}