Fast Discovery of Reliable k-terminal Subgraphs Authors: Melissa Kasari, Hannu Toivonen, Petteri Hintsanen
Abstract:
We present a novel and efficient algorithm for solving the most reliable subgraph problem with multiple query nodes on undirected random graphs. Reliable subgraphs are useful for summarizing connectivity between given query nodes. Formally, we are given a graph G?=?(V, E), a set of query (or terminal) nodes Q???V, and a positive integer B. The objective is to find a subgraph H???G containing Q, such that H has at most B edges, and the probability that H is connected is maximized. Previous algorithms for the problem are either computationally demanding, or restricted to only two query nodes. Our algorithm extends a previous algorithm to handle k query nodes, where 2???k???|V|. We demonstrate experimentally the usefulness of reliable k-terminal subgraphs, and the accuracy, efficiency and scalability of the proposed algorithm on real graphs derived from public biological databases.
Uses biological data from the Biomine project, to demonstrate a solution to the reliable subgraph problem. Nodes are judged on the basis of their network “reliability,” that is connectedness to the query nodes.
Wonder what it would like to have a quality of the nodes in addition to “connectedness” as the basis for the reliable subgraph calculation?
Also available at CiteSeer, Fast Discovery of Reliable k-terminal Subgraphs