Finding reliable subgraphs from large probabilistic graphs

Show simple item record

dc.contributor.author Hintsanen, Petteri
dc.contributor.author Toivonen, Hannu
dc.date.accessioned 2014-11-17T12:23:00Z
dc.date.available 2014-11-17T12:23:00Z
dc.date.issued 2008
dc.identifier.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
dc.identifier.other PURE: 942277
dc.identifier.other PURE UUID: fb219758-8889-4f91-a5c6-33e81ad38eca
dc.identifier.other dawa_publication: 177785
dc.identifier.other WOS: 000258290700002
dc.identifier.other Scopus: 48349139682
dc.identifier.other ORCID: /0000-0003-1339-8022/work/29478251
dc.identifier.uri http://hdl.handle.net/10138/143972
dc.description.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. sv
dc.description.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. fi
dc.description.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. en
dc.format.extent 21
dc.language.iso eng
dc.relation.ispartof Data Mining and Knowledge Discovery
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 113 Computer and information sciences
dc.title Finding reliable subgraphs from large probabilistic graphs en
dc.type Article
dc.contributor.organization COMBI TUTKIJAKOULU (-2009)
dc.contributor.organization Helsinki Institute for Information Technology HIIT (-2009)
dc.contributor.organization Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
dc.contributor.organization Department of Computer Science
dc.contributor.organization Discovery Research Group/Prof. Hannu Toivonen
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.1007/s10618-008-0106-1
dc.relation.issn 1384-5810
dc.rights.accesslevel openAccess
dc.type.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 simple item record