Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
<|reference_start|>Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size: 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 cost per solution 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)$ with an amortized cost per solution depending \emph{solely} on the order $k$, contrarily to previous approaches where the cost depends \emph{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)$ 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 cost per solution for listing $k$-graphlets is reduced to $O(k)$. Whenever $k = O(1)$, as it is often the case in practical settings, these algorithms are the first to achieve constant time per solution.<|reference_end|>
@article{conte2024enumerating,
    title={Enumerating Graphlets with Amortized Time Complexity Independent of
  Graph Size},
    author={Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita,
  Davide Rucci, Takeaki Uno, Kunihiro Wasa},
    journal={arXiv preprint arXiv:2405.13613},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13613},
    primaryClass={cs.DS}
}