Aproximação de parâmetros de clustering em redes complexas e complexidade de amostra

Abstract

Recognizing small-world networks is a key task in graph theory, since such networks can model properties that are usually observed in many social and natural phenomena. Several strategies can be adopted to identify these graphs, one of the most common being the local clustering coefficient. Although this metric is relatively recent, numerous algorithms have already been proposed to compute it. Approaches range from exact algorithms—whose core is the triangle-counting problem—to a variety of approximation methods based on different sampling strategies. While exact triangle counting has cubic time complexity and thus becomes prohibitively expensive for large complex-network graphs, approximation algorithms alleviate this cost at the expense of precision. Among these alternatives, Lima (2022) introduced an algorithm grounded in sample-complexity theory that not only reduces the running time but also adapts more effectively to the combinatorial structure of each input graph. The present work implements the algorithm Lima (2022) and provides a literature review of the theoretical foundations required for a comprehensive understanding of its operation.