Aidan Hogan
ABSTRACT
Graphs are being increasingly adopted as a flexible data model in scenarios (e.g., Google's Knowledge Graph, Facebook's Graph API, Wikidata, etc.) where multiple editors are involved in content creation, where the schema is ever changing, where data are incomplete, where the connectivity of resources plays a key rolescenarios where relational models traditionally struggle. But with this flexibility comes a conceptual cost: it can be difficult to summarise and understand, at a high level, the content that a given graph contains. Hence profiling graphs becomes of increasing importance to extract order, a posteriori, from the chaotic processes by which such graphs are generated. This talk will motivate the use of graphs as a data model, abstract recent trends in graph data management, and then turn to the issue of profiling and summarising graphs: what are the goals of such profiling, the principles by which graphs can be summarised, the main techniques by which this can/could be achieved The talk will emphasise the importance of profiling graphs while highlighting a variety of open research questions yet to be tackled.
- Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv., Vol. 50, 5 (2017), 68:1--68:40. Google Scholar
Digital Library
- Renzo Angles and Claudio Gutiérrez. 2008. Survey of graph database models. ACM Comput. Surv., Vol. 40, 1 (2008), 1:1--1:39. Google ScholarDigital Library
- Dan Brickley, R.V. Guha, and Brian McBride. 2014. RDF Schema 1.1. W3C Recommendation. (25 Feb. 2014). http://www.w3.org/TR/rdf-schema/Google Scholar
- Mohamed Ben Ellefi, Zohra Bellahsene, John G. Breslin, Elena Demidova, Stefan Dietze, Julian Szymanski, and Konstantin Todorov RDF Dataset Profiling - a Survey of Features, Methods, Vocabularies and Applications. Semantic Web Journal (. ). To appear.Google Scholar
- Holger Knublauch and Dimitris Kontokostas. 2014. Shapes Constraint Language (SHACL). W3C Working Group Note. (24 June. 2014). http://www.w3.org/TR/rdf11-primer/Google Scholar
- Gabriel M. Kuper and Moshe Y. Vardi. 1984. A New Approach to Database Logic. In ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS). 86--96. Google ScholarDigital Library
- Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph Summarization Methods and Applications: A Survey. CoRR Vol. abs/1612.04883 (2018). showeprint{arxiv}1612.04883 http://arxiv.org/abs/1612.04883Google ScholarDigital Library
- Denny Vrandevcić and Markus Krötzsch. 2014. Wikidata: a free collaborative knowledgebase. Commun. ACM Vol. 57, 10 (2014), 78--85. Google ScholarDigital Library
Index Terms
- Profiling Graphs: Order from Chaos
Recommendations
Star coloring of graphs
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic number of an undirected graph G, denoted by χs(G), is ...
Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex v r-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the ...
Dually Chordal Graphs
Recently in several papers, graphs with maximum neighborhood orderings were characterized and turned out to be algorithmically useful. This paper gives a unified framework for characterizations of those graphs in terms of neighborhood and clique ...
Comments