Quasiquadratic Time Algorithms for Square and Pentagon Counting in Real-World Networks

Guzman G.E.C.; León J. · Communications in Computer and Information Science (2021) · DOI: 10.1007/978-3-030-76228-5_33

Resumen

Counting structures in graphs (triangles, cliques, graphlets, etc.) is an important task when analyzing real-world networks given its usefulness to make link prediction, community discovery, graph classification, etc. Among many structures in graphs, triangle counting (cycles of length 3) has been a hot research topic in recent years. As a result of that, a number of algorithms have been developed for counting triangles and many closely related structures. However, square and pentagon counting (cycles of length 4 and 5 respectively) have received less attention despite its importance when analyzing real-world bipartite graphs and its influence on the graph spectrum. In this work, we propose quasiquadratic time algorithms for approximately counting the number of squares and pentagons in a simple graph as a whole, and also obtain such counts per vertices.

Instituciones: Universidad Nacional de San Antonio Abad del Cusco