Risk-Averse Matchings over Uncertain Graph Databases

摘要: A large number of applications such as querying sensor networks, and analyzing protein-protein interaction (PPI) rely on mining uncertain graph hypergraph databases. In this work we study the following problem: given an uncertain, weighted (hyper)graph, how can efficiently find a (hyper)matching with high expected reward, low risk? This problem naturally arises in context several important applications, online dating, kidney exchanges, team formation. We introduce novel formulation for finding matchings maximum reward bounded risk under general model (hyper)graphs that work. Our generalizes probabilistic models used prior work, captures both continuous discrete probability distributions, thus allowing to handle privacy related inject appropriately distributed noise (hyper)edge weights. Given our optimization is NP-hard, turn attention designing efficient approximation algorithms. For case graphs, provide $\frac{1}{3}$-approximation algorithm, $\frac{1}{5}$-approximation algorithm near optimal run time. hypergraphs, $\Omega(\frac{1}{k})$-approximation where $k$ rank (i.e., any hyperedge includes at most nodes), runs almost (modulo log factors) linear We complement theoretical results by testing algorithms wide variety synthetic experiments, observe controlled setting interesting findings trade-off between risk. also application providing recommendations teams are likely collaborate, have impact.