Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs

• Item type: Journal(1)
• 公開日: 2024-11-15
• タイトル: Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs
• タイトル / 言語: en
• タイトル: Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] enumeration algorithms, subgraph enumeration, support-closed connected induced subgraphs, protein-protein network, GWAS
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Kyoto University
• 著者所属: Kyoto University
• 著者所属: Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者名: Daiki, Watanabe; Takumi, Tada; Kazuya, Haraguchi
• 著者名(英): Daiki, Watanabe; Takumi, Tada; Kazuya, Haraguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Suppose that we are given a tuple (G,I,σ) of an undirected graph G=(V,E), an itemset I={1,2,...,q}, and a mapping σ:V → 2I. For S ⊆ V, let us denote Iσ(S):=∩v∈sσ(v). We say that S induces a support-closed connected subgraph if S is maximal with respect to the connectivity and the common itemset (i.e., the subgraph G[S] induced by S is connected and, for any v ∈ V ＼ S, G[S∪{v}] is disconnected or Iσ(S∪{v}) ⊊ Iσ(S)). Several algorithms have been developed for enumerating all support-closed connected induced subgraphs, where some of them are shown to be polynomial-amortized or polynomial-delay. However, a theoretical complexity bound does not necessarily represent the empirical performance of an algorithm. In this paper, we compare the empirical performance of four enumeration algorithms named COPINE (branch-and-bound), COOMA (dynamic programming), FT (family-tree) and BP (binary partition), respectively. We observe that, for random instances, COOMA is generally the fastest, followed by BP, and that these two algorithms are more robust to parameters of random instances than the other two. We then extend BP to a problem that arises from bacterial GWAS (Genome-Wide Association Studies) and observe that its implementation is much faster than an existing implementation of CALDERA, a previous algorithm.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); DOI http://dx.doi.org/10.2197/ipsjjip.32.894; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Suppose that we are given a tuple (G,I,σ) of an undirected graph G=(V,E), an itemset I={1,2,...,q}, and a mapping σ:V → 2I. For S ⊆ V, let us denote Iσ(S):=∩v∈sσ(v). We say that S induces a support-closed connected subgraph if S is maximal with respect to the connectivity and the common itemset (i.e., the subgraph G[S] induced by S is connected and, for any v ∈ V ＼ S, G[S∪{v}] is disconnected or Iσ(S∪{v}) ⊊ Iσ(S)). Several algorithms have been developed for enumerating all support-closed connected induced subgraphs, where some of them are shown to be polynomial-amortized or polynomial-delay. However, a theoretical complexity bound does not necessarily represent the empirical performance of an algorithm. In this paper, we compare the empirical performance of four enumeration algorithms named COPINE (branch-and-bound), COOMA (dynamic programming), FT (family-tree) and BP (binary partition), respectively. We observe that, for random instances, COOMA is generally the fastest, followed by BP, and that these two algorithms are more robust to parameters of random instances than the other two. We then extend BP to a problem that arises from bacterial GWAS (Genome-Wide Association Studies) and observe that its implementation is much faster than an existing implementation of CALDERA, a previous algorithm.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); DOI http://dx.doi.org/10.2197/ipsjjip.32.894; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 65, 号 11, 発行日 2024-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764
• 公開者 / 言語: ja
• 公開者 / 出版者: 情報処理学会