Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a gi...Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given cardinality from networks (or connected undirected graphs in networks). The first algorithm is a variant of a previous wellknown algorithm. The algorithm enumerates all connected induced subgraphs of cardinality k in a bottom-up manner. Thedata structures that lead to unit time element checking and linear space are presented. Different from previous algorithmsthat work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected inducedsubgraphs of cardinality k in a top-down manner is proposed. The correctness and complexity of the top-down algorithmare theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of realworld networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms thestate-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithmcan achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.61404069the Scientific Research Project of Colleges and Universities in Guangdong Province of China under Grant No.2021ZDZX1027+1 种基金the Guangdong Basic and Applied Basic Research Foundation under Grant Nos.2022A1515110712 and 2023A1515010077the STU Scientific Research Foundation for Talents under Grant Nos.NTF20016 and NTF20017.
文摘Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given cardinality from networks (or connected undirected graphs in networks). The first algorithm is a variant of a previous wellknown algorithm. The algorithm enumerates all connected induced subgraphs of cardinality k in a bottom-up manner. Thedata structures that lead to unit time element checking and linear space are presented. Different from previous algorithmsthat work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected inducedsubgraphs of cardinality k in a top-down manner is proposed. The correctness and complexity of the top-down algorithmare theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of realworld networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms thestate-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithmcan achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.
