Finding reliable subgraphs from large probabilistic graphs

Show full item record



Permalink

http://hdl.handle.net/10138/143972

Citation

Hintsanen , P & Toivonen , H 2008 , ' Finding reliable subgraphs from large probabilistic graphs ' , Data Mining and Knowledge Discovery , vol. 17 , no. 1 , pp. 3-23 . https://doi.org/10.1007/s10618-008-0106-1

Title: Finding reliable subgraphs from large probabilistic graphs
Author: Hintsanen, Petteri; Toivonen, Hannu
Contributor organization: COMBI TUTKIJAKOULU (-2009)
Helsinki Institute for Information Technology HIIT (-2009)
Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
Department of Computer Science
Discovery Research Group/Prof. Hannu Toivonen
Date: 2008
Language: eng
Number of pages: 21
Belongs to series: Data Mining and Knowledge Discovery
ISSN: 1384-5810
DOI: https://doi.org/10.1007/s10618-008-0106-1
URI: http://hdl.handle.net/10138/143972
Abstract: Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by 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. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by 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. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by 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. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.
Subject: 113 Computer and information sciences
Peer reviewed: Yes
Usage restriction: openAccess
Self-archived version: acceptedVersion


Files in this item

Total number of downloads: Loading...

Files Size Format View
dmkd08.pdf 381.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record