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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Birnbaum ZW (1969) On the importance of different components in a multicomponent system. Multivar Anal II:581–592
Bryant RE (1986) Graph-based algorithms for boolean function manipulation. IEEE Trans Comput 35: 677–691
Colbourn CJ (1987) The combinatorics of network reliability. Oxford University Press, Oxford
De Raedt L, Kersting K, Kimmig A, Revoredo K, Toivonen H (2008) Compressing probabilistic Prolog programs. Mach Learn 70: 151–168
Duffin RJ (1965) Topology of series–parallel networks. J Math Anal Appl 10: 303–318
Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28: 652–673
Faloutsos C, McCurley KS, Tomkins A (2004) Fast discovery of connection subgraphs. In: Proceedings of the 10th ACM SIGKDD international conference on knowledge discovery and data mining, pp 118–127
Hershberger J, Maxel M, Suri S (2007) Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans Algorithms 3: 45
Hintsanen P (2007) The most reliable subgraph problem. In: Proceedings of the 11th European conference on principles and practice of knowledge discovery in databases, pp 471–478
Lawler EL (1972) A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manage Sci 18: 401–405
Roditty L (2007) On the k-simple shortest paths problem in weighted directed graphs. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, pp 920–928
Sevon P, Eronen L, Hintsanen P, Kulovesi K, Toivonen H (2006) Link discovery in graphs derived from biological databases. In: Proceedings of data integration in the life sciences. Third international workshop, pp 35–49
Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series–parallel digraphs. SIAM J Comput 11: 298–313
Author information
Authors and Affiliations
Corresponding author
Additional information
Responsible editors: Walter Daelemans, Bart Goethals, and Katharina Morik.
Rights and permissions
About this article
Cite this article
Hintsanen, P., Toivonen, H. Finding reliable subgraphs from large probabilistic graphs. Data Min Knowl Disc 17, 3–23 (2008). https://doi.org/10.1007/s10618-008-0106-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10618-008-0106-1