We demonstrate EGG (Evolving Graph Generator), an opensource framework for generating evolving RDF graphs based on nelytuned temporal constraints given by the user. During the demonstration, we will showcase the highly-expressive constraints that the user can specify in EGG to generate evolving graphs over various real-world use cases, the accuracy and scalability of the generator, and the ease of using EGG in performance comparisons of evolving graph processing systems.
Evolving graph con guration # of snapshots Evolving properties (nodes and edges) Evolution constraints
Static graph con guration
Size Node and edge types Occurrence constraints Degree distributions
EGG Evolving graph generator
gMark Static graph generator
RDF annotated
with temporal
information
In this section, we present gMark static graph con gurations, EGG evolving graph
con gurations, and we brie y discus EGG implementation challenges. Similarly to
gMark, EGG is schema-driven and domain-independent. We use next as running
example a geographical database, but we have been additionally able to easily
encode di erent domains such as a social network, a DBLP-like bibliographical
network, or an online shop. All these schemas will be part of our demonstration.
Static graph con gurations. Assume that a user wants to generate graphs
simulating a geographical database storing data about cities, and di erent
facilities such as transportation and hotels. The user can specify as gMark input the
following types of constraints: (i) graph size, given as # of nodes; (ii) node types
e.g., city and hotel, and edge types e.g., train and contains; (iii) occurrence
constraints e.g., 10% of the graph nodes should be of type city, whereas 90%
of the graph nodes should be of type hotel; (iv) degree distributions e.g.,
source type predicate target type In-distribution Out-distribution
city contain!s hotel Uniform [
!
meaning that we can have an edge of type contains from a node of type city
to a node of type hotel, with a Zip an out-distribution (since it is realistic to
assume that the number of hotels in a city follows such a power-law distribution)
and a uniform [
We call such gMark graph con gurations as being static since the nodes of type e.g., city and hotel are rarely created or deleted. Nonetheless, such nodes (as well as the di erent edges connecting them) possess properties that naturally evolve over time, in an interdependent manner. The user can specify such evolving properties as input of EGG, as we illustrate next.
Evolving graph con gurations. Assume that our user generates with gMark
a graph having nodes of type city and hotel, and edges of type train
(connecting two cities) and contains (connecting a city to a hotel). Next, the user wants
to add properties that evolve over time for the aforementioned nodes and edges,
assuming that a graph snapshot corresponds to a day. We next give examples of
such properties, together with nely-tuned constraints to evolve among
consecutive snapshots. A node of type hotel has the following evolving properties:
{ availableRooms (quantitative discrete), which can have as values integers
in the interval [
{ star (ordered qualitative), which can have ve possible values, following a geometric distribution. It can only change every thirty snapshots, with a probability of 10%, and it can only increment or decrement by 1.
{ hotelPrice (quantitative continuous), whose values follow a normal distribution in an interval that is dynamically constructed based on the value of the property star. Moreover, hotelPrice is anti-correlated with availableRooms i.e., if availableRooms decreases, then hotelPrice increases, and vice-versa.
The user can similarly specify evolving properties and evolution constraints for the node type city (e.g., properties weather and airQuality) and for the edge type train (e.g., property trainPrice). It is worth noting that we allow the EGG user to specify validity properties i.e., Boolean properties encoding whether a given node or edge exists at a given snapshot e.g., a train connection between two cities may not be valid during all snapshots.
Implementation challenges. Building a system like EGG is an ambitious goal since we allow the user to specify very expressive constraints. This leads to some interesting challenges that we brie y discuss next:
Computational complexity. As illustrated earlier, we allow the user to specify evolution constraints where the value of a property among consecutive snapshots depends on another property. We model the inter-dependencies between such evolving properties with a dependency graph. It is easy to see that if the aforementioned dependency graph is cyclic, the generation algorithm may not halt. Consequently, in our implementation we require that the dependency graph is acyclic and we sort it topologically to decide in which order we should apply the evolution constraints. Even for acyclic dependency graphs, we suspect that it is NP-complete to decide whether there exists a sequence of graph snapshots satisfying the input constraints. The exact complexity is an open question.
Storage redundancy. A naive solution to store the generated evolving graphs
would be to entirely store each snapshot, which would yield a redundant storage
due to the graph parts that are static throughout the snapshots. To minimize
such redundancy, we rely on a storage format inspired by [
During the demonstration, we will (i) introduce via examples the nely-tuned
temporal constraints that the user can specify in EGG, (ii) emphasize the
accuracy and scalability of EGG, and (iii) point out the ease of using EGG in
performance comparisons of evolving graph processing systems.
(i) Finely-tuned constraints by example. We will show to the attendees
how nely-tuned temporal constraints as those exempli ed in Section 2 can be
easily encoded in JSON as EGG input. In addition to our running example, we
will also rely on several EGG real-world use cases: a social network in the spirit
of the datasets used in [