Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918019536519168 |
|---|---|
| author | Conte, Alessio Grossi, Roberto Kobayashi, Yasuaki Kurita, Kazuhiro Rucci, Davide Uno, Takeaki Wasa, Kunihiro |
| author_facet | Conte, Alessio Grossi, Roberto Kobayashi, Yasuaki Kurita, Kazuhiro Rucci, Davide Uno, Takeaki Wasa, Kunihiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13613 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size Conte, Alessio Grossi, Roberto Kobayashi, Yasuaki Kurita, Kazuhiro Rucci, Davide Uno, Takeaki Wasa, Kunihiro Data Structures and Algorithms 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. |
| title | Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.13613 |