- (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
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.
|2011 DiscoveringHighlyReliableSubgra||Ruoming Jin|
Charu C. Aggarwal
|Discovering Highly Reliable Subgraphs in Uncertain Graphs||10.1145/2020408.2020569||2011|
|Author||Ruoming Jin +, Lin Liu + and Charu C. Aggarwal +|
|proceedings||Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining +|
|title||Discovering Highly Reliable Subgraphs in Uncertain Graphs +|