Probabilistic subgraph matching on huge social networks

Matthias Bröcheler*, Andrea Pugliese, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
Pages271-278
Number of pages8
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011 - Kaohsiung, Taiwan, Province of China
Duration: Jul 25 2011Jul 27 2011

Publication series

NameProceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011

Other

Other2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
Country/TerritoryTaiwan, Province of China
CityKaohsiung
Period7/25/117/27/11

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Probabilistic subgraph matching on huge social networks'. Together they form a unique fingerprint.

Cite this