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.展开更多
Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximu...Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.展开更多
基金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.
基金supported by National Natural Science Foundation of China under Grant,No.60873205Beijing Natural Science Foundation under Grant No. 1092011+1 种基金Foundation of Beijing Education Commission under Grant No.SM200910037005the Funding Project for Academic Human Resources Development in Institutions of Higher Learning Under the Jurisdiction of Beijing Municipality(PHR(IHLB))and Foundation of WYJD200902
文摘Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.
