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.
Extending these reliability queries, where source and sink node(s) are specified, the corresponding graph mining problem is to find, for a given probabilistic graph, the set of most reliable k-terminal subgraphs REF .
Fast Discovery of Reliable k-terminal Subgraphs
PAKDD
Computer Science