<p>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 well-known algorithm. The algorithm enumerates all connected induced subgraphs of cardinality <i>k</i> in a bottom-up manner. The data structures that lead to unit time element checking and linear space are presented. Different from previous algorithms that work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected induced subgraphs of cardinality <i>k</i> in a top-down manner is proposed. The correctness and complexity of the top-down algorithm are theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of real-world networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms the state-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithm can achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Novel Algorithms for Efficient Mining of Connected Induced Subgraphs of a Given Cardinality

  • Shan-Shan Wang,
  • Cheng-Long Xiao

摘要

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 well-known algorithm. The algorithm enumerates all connected induced subgraphs of cardinality k in a bottom-up manner. The data structures that lead to unit time element checking and linear space are presented. Different from previous algorithms that work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected induced subgraphs of cardinality k in a top-down manner is proposed. The correctness and complexity of the top-down algorithm are theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of real-world networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms the state-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithm can achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.