2011 DiscoveringHighlyReliableSubgra

• (Jin et al., 2011) ⇒ Ruoming Jin, Lin Liu, and Charu C. Aggarwal. (2011). “Discovering Highly Reliable Subgraphs in Uncertain Graphs.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020569

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Discovering+Highly+Reliable+Subgraphs+in+Uncertain+Graphs
• http://dl.acm.org/citation.cfm?id=2020408.2020569&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; data mining; frequent cohesive set; reliable subgraph; theory; uncertain graph

Abstract

In this paper, we investigate the highly reliable subgraph problem, which arises in the context of uncertain graphs. This problem attempts to identify all induced subgraphs for which the probability of connectivity being maintained under uncertainty is higher than a given threshold. This problem arises in a wide range of network applications, such as protein-complex discovery, network routing, and social network analysis. Since exact discovery may be computationally intractable, we introduce a novel sampling scheme which enables approximate discovery of highly reliable subgraphs with high probability. Furthermore, we transform the core mining task into a new frequent cohesive set problem in deterministic graphs. Such transformation enables the development of an efficient two-stage approach which combines novel peeling techniques for maximal set discovery with depth-first search for further enumeration. We demonstrate the effectiveness and efficiency of the proposed algorithms on real and synthetic data sets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 DiscoveringHighlyReliableSubgra	Charu C. Aggarwal Ruoming Jin Lin Liu			Discovering Highly Reliable Subgraphs in Uncertain Graphs				10.1145/2020408.2020569		2011