TY - GEN
T1 - Probabilistic subgraph matching on huge social networks
AU - Bröcheler, Matthias
AU - Pugliese, Andrea
AU - Subrahmanian, V. S.
PY - 2011
Y1 - 2011
N2 - Users querying massive social networks or RDF databases are often not 100% certain about what they are looking for due to the complexity of the query or heterogeneity of the data. In this paper, we propose "probabilistic subgraph" (PS) queries over a graph/network database, which afford users great flexibility in specifying "approximately" what they are looking for. We formally define the probability that a substitution satisfies a PS-query with respect to a graph database. We then present the PMATCH algorithm to answer such queries and prove its correctness. Our experimental evaluation demonstrates that PMATCH is efficient and scales to massive social networks with over a billion edges.
AB - Users querying massive social networks or RDF databases are often not 100% certain about what they are looking for due to the complexity of the query or heterogeneity of the data. In this paper, we propose "probabilistic subgraph" (PS) queries over a graph/network database, which afford users great flexibility in specifying "approximately" what they are looking for. We formally define the probability that a substitution satisfies a PS-query with respect to a graph database. We then present the PMATCH algorithm to answer such queries and prove its correctness. Our experimental evaluation demonstrates that PMATCH is efficient and scales to massive social networks with over a billion edges.
UR - http://www.scopus.com/inward/record.url?scp=80052767465&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052767465&partnerID=8YFLogxK
U2 - 10.1109/ASONAM.2011.78
DO - 10.1109/ASONAM.2011.78
M3 - Conference contribution
AN - SCOPUS:80052767465
SN - 9780769543758
T3 - Proceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
SP - 271
EP - 278
BT - Proceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
T2 - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
Y2 - 25 July 2011 through 27 July 2011
ER -