ECML PKDD 2008
Paper abstractFinding Reliable Subgraphs from Large Probabilistic GraphsPetteri Hintsanen - University of Helsinki, FinlandHannu Toivonen - University of Helsinki, Finland Session: Graph Mining Springer Link: http://dx.doi.org/10.1007/978-3-540-87479-9_13 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. |