Algorithmica Прикладные компьютерные науки
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Аннотация
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.