Proceedings of the VLDB Endowment · 2010 · 241 citations · 44 references
ComputingComputer ScienceAlgorithmsData MiningUncertainty QuantificationGraph AlgorithmsGraph MiningGraph TheoryNearest Neighbor SearchShortest Path AlgorithmsGraph QueryingGraph SimilarityGraph Similarity SearchK-nearest NeighborsNearest Neighbor QueriesSearch Space PruningShortest PathsSimilarity Search
Complex networks, such as biological, social, and communication networks, often entail uncertainty, and thus, can be modeled as probabilistic graphs . Similar to the problem of similarity search in standard graphs, a fundamental problem for probabilistic graphs is to efficiently answer k-nearest neighbor queries ( k -NN), which is the problem of computing the k closest nodes to some specific node. In this paper we introduce a framework for processing k -NN queries in probabilistic graphs. We propose novel distance functions that extend well-known graph concepts, such as shortest paths. In order to compute them in probabilistic graphs, we design algorithms based on sampling. During k -NN query processing we efficiently prune the search space using novel techniques. Our experiments indicate that our distance functions outperform previously used alternatives in identifying true neighbors in real-world biological data. We also demonstrate that our algorithms scale for graphs with tens of millions of edges.
44
Pattern Recognition and Machine Learning
Journal of Electronic Imaging · 2007 · 22.1K citations
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Global landscape of protein complexes in the yeast Saccharomyces cerevisiae
Nevan J. Krogan, Gerard Cagney, Haiyuan Yu et al. · Nature · 2006 · 3K citations
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations