Algorithmica Прикладные компьютерные науки

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size

Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
Springer Nature · 2025-05-13 · DOI 10.1007/s00453-025-01312-0

Аннотация

Abstract Graphlets of order k in a graph G are connected subgraphs induced by k nodes (called k -graphlets) or by k edges (called edge k -graphlets). They are among the interesting subgraphs in network analysis to get insights on both the local and global structure of a network. While several algorithms exist for discovering and enumerating graphlets, the amortized time complexity of such algorithms typically depends on the size of the graph G , or its maximum degree. In real networks, even the latter can be in the order of millions, whereas k is typically required to be a small value. In this paper we provide the first algorithm to list all graphlets of order k in a graph $$G=(V,E)$$ G = ( V , E ) with an amortized time complexity depending solely on the order k , contrarily to previous approaches where the cost depends also on the size of G or its maximum degree. Specifically, we show that it is possible to list k -graphlets in $$O(k^2)$$ O ( k 2 ) time per solution, and to list edge k -graphlets in O ( k ) time per solution. Furthermore we show that, if the input graph has bounded degree, then the amortized time for listing k -graphlets is reduced to O ( k ). Whenever $$k = O(1)$$ k = O ( 1 ) , as it is often the case in practical settings, these algorithms are the first to achieve constant time per solution.

Читать у издателя →