Have you ever, as a developer, come across problems and algorithms involving searching for patterns in a graph database? Are you interested in network science, for example, social network analysis, planning and designing optimal telecommunications networks, or the analysis of time-series data for discovering interesting patterns?
This paper will provide you with the fundamentals of how you can query and search a graph. The authors contribute a study of similarity graph containment search on large uncertain graph databases. These are graphs where the edges are assigned probabilities. The paper is also an attempt to “formally prove that subgraph or supergraph similarity search over uncertain graphs is #P-hard,” which is certainly better than NL-completeness.
Despite this highly specialized focus on uncertain graphs, the paper will mostly interest new researchers addressing graph-based querying or matching, information retrieval, and similarity search, as it provides an excellent list of references. It also provides a wealth of formalisms and theorems, which may also guide new researchers in how to embed formalisms in their own papers.
From a broader educational point of view, some text passages and references can be used for teaching purposes in advanced master’s level courses related to algorithms and complexity, as well as to information retrieval and search.