Paper abstract

Finding Reliable Subgraphs from Large Probabilistic Graphs

Petteri Hintsanen - University of Helsinki, Finland
Hannu Toivonen - University of Helsinki, Finland

Session: Graph Mining
Springer Link:

We propose two new heuristics for solving the most reliable subgraph problem (MRSP) on large, undirected probabilistic graphs. The MRSP poses a probabilistic graph G subject to random edge failures, a set of terminal vertices, and an integer K. The objective is to remove K edges from G such that the probability of connecting the terminals in the remaining subgraph is maximized. Reliable subgraphs can be used, for example, to find and rank indirect, nontrivial links between terminals, and to concisely visualize large graphs. Previous methods for solving the MRSP on general graphs scale poorly or produce inferior results on large probabilistic graphs. On the contrary, our proposed methods are both scalable and robust, as demonstrated by our experiments on real probabilistic graphs from the biological domain.