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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1312_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">$G=(V,E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1312_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$O(k^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1312_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">$k = O(1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, as it is often the case in practical settings, these algorithms are the first to achieve constant time per solution.

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size

期刊论文
出版模式：

开放获取
发表日期：

2025年5月13日

查看全文

Alessio Conte,
Roberto Grossi,
Yasuaki Kobayashi,
Kazuhiro Kurita,
Davide Rucci,
Takeaki Uno,
Kunihiro Wasa

摘要

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.