DBScholar

Back to papers

Distance-Constraint Reachability Computation in Uncertain Graphs

Summary: Approximates the #P-complete probability that two vertices are connected within distance d in an uncertain graph. Introduces unequal-probability Horvitz–Thompson and recursive sampling estimators that reduce variance and improve online efficiency over direct sampling. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hb401abfd2d1cb73e
Venue
VLDB
Year
2011
Pagerank
0.00011296964
Overall Rank
1,260 | 91.53%
DOI
10.14778/2002938.2002941

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{jin_vldb11,
        title = {{Distance-Constraint Reachability Computation in Uncertain Graphs}},
        author = {Jin, Ruoming and Liu, Lin and Ding, Bolin and Wang, Haixun},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {9},
        pages = {551--562},
        doi = {10.14778/2002938.2002941},
        url = {https://doi.org/10.14778/2002938.2002941},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
2,086 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 9.0689711e-05
2,604 K-Reach: Who is in Your Small World 2012 VLDB 8.2302549e-05
3,036 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 7.731521e-05
3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.3926236e-05
3,604 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 7.1706333e-05
3,632 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.1494448e-05
3,820 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.005206e-05
4,732 Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach 2022 SIGMOD 6.4461271e-05
5,301 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.189668e-05
5,754 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.0058421e-05
5,951 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.9366845e-05
5,986 Querying Uncertain Data with Aggregate Constraints 2011 SIGMOD 5.9260205e-05
6,161 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.8647415e-05
6,475 Clustering Uncertain Graphs 2018 VLDB 5.7736095e-05
7,589 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 5.4882381e-05
9,240 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.2056825e-05
9,452 Sage: A System for Uncertain Network Analysis 2022 VLDB 5.1745448e-05
9,840 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1230858e-05
9,914 Efficient Stochastic Routing in Path-Centric Uncertain Road Networks 2024 VLDB 5.1103839e-05
10,132 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.0751052e-05
11,770 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 4.9793485e-05
12,396 Indexing Metric Uncertain Data for Range Queries 2015 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
274 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022490994
693 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00014734389
1,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012208695
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD
2 3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB
3 9,240 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD
4 5,951 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB
5 6,161 On Uncertain Graphs Modeling and Queries 2015 VLDB
6 1,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB
7 2,534 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD
8 5,754 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB
9 6,475 Clustering Uncertain Graphs 2018 VLDB
10 3,820 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD