Graph Layouts

Prov Viewer allows the user to interactively change the graph layout to better visualize the result. We created two provenance graph visualization layouts besides the existing JUNG layouts: temporal and spatial.

JUNG Layouts:

• Circle

• FRLayout

• FRLayout2

• ISOMLayout

• KKLayout

Temporal Layout

The temporal layout organizes the graph in a chronological order similar to a timeline (or spreadsheet) for each agent. Thus, each timeline (or line) of the graph groups activities of the same agent and each column in the graph represents the passage of time. This makes easier to know the entity or agent responsible for executing each activity by just looking at the agent responsible for that line. Furthermore, this layout considers the lowest valid temporal value as zero in order to position the entire graph. Invalid temporal values are also considered as zero for the purpose of positioning them in the graph. Furthermore, it is possible to choose the temporal scale among milliseconds, seconds, minutes, hours, days, and weeks. Thus, the graph positions the vertices in the x axis according to the chosen scale. Prov Viewer always assumes that the temporal value is in milliseconds when not using the "xml Gregorian calendar" format. The figure below illustrates an example of our temporal layout, displaying the graph similarly to a spreadsheet and organizing the vertices by their chronological order. Note that now it is much easier to identify the agent responsible for each activity as the leftmost nodes and their chronological order by looking at the activity's placement in the graph. The horizontal position represents the time axis (passage of time) and the vertical position represents the agent axis (the responsible for the activity).

A temporal layout visualization example:

Spatial Layout

The spatial layout organizes the vertices in the graph by their spatial coordinates and can be used for spatial or georeferencing the data. The layout also supports the usage of an orthographic image or maps taken from Google Maps and OpenStreetMaps as background for the graph. This is particularly useful for corresponding elements with other graphical representations, such as a map of a city or a game scene. For orthographic images, Prov Viewer uses a simple rule-of-three to compare the screenshot's width with the viewport position (i.e., coordinates of the upper left corner of the image) to determine the scale factor for the graph in order to align it with the image, which uses pixel position. It also transforms the camera's world position (i.e., camera's coordinates) to the viewport coordinates to facilitate the computation, which places the camera at (0, 0) in world coordinates and the border relative to this new position. When dealing with real world maps, Prov Viewer automatically transform the latitude and longitude to pixel coordinates. This automatic process requires only three input values to correctly align the image with the graph: orthographic images require the camera's coordinates and the upper-left corner x coordinate; for maps it requires the upper-left corner coordinates and the zoom level. When using the spatial layout in conjunction with a background image, the user sees where each event occurred just by looking at the graph's placement in the image.

An example of a graph using the spatial layout without a background image and an orthographic image taken from the scene is presented below.

By passing the graph with the background image, Prov Viewer will combine both to generate the following visualization:

Configuring the Background Image

Orthographic Image

In order to use an orthographic image in the background during graph visualization, it is necessary to follow a few steps:

1. Capture an orthographic Image of the desired scene.

2. Take note of the coordinates of the camera used to take the orthographic Image.

3. Take note of the coordinates that represent the upper left border of the image. Prov Viewer only requires the X coordinate of the upper left border of the image.

4. Subtract the coordinate from step 4 with the X coordinate from step 2. This will give us the upper left border position in relation to the camera.

5. Configure the XML file with the image location and the above coordinates from step 2 and 4.

Below is an example of this configuration process:

• Original orthographic image taken from the Angry Bots game:

• Coordinates of the camera used to capture the image:

x = 2.247497

z = -48.11044

Note: In Unity, the Z-axis is the equivalent of latitude, since the y-axis represents height.

• The upper left border x coordinate already subtracted with the x coordinate from the camera (x: 2.247497):

x = 113.404

• The graph visualization from a game session using the image as a background:

Google Maps or Open Street Map image

In order to use a map image in the background during graph visualization, it is necessary to follow a few steps:

1. Capture an image of the map from Google Maps or Open Street Map.

2. Take note of the coordinates from the upper left border of the image.

3. Take note of the zoom level used to capture the image.

4. Configure the XML file with the image location and the above coordinates from step 2 and zoom level from step 3.

Below is an example of this configuration process:

• Image taken from Google Maps:

• Upper left corner coordinates and the zoom level:

Longitude: -43.31407

Latitude: -22.87407

Zoom level: 15

• The graph visualizations using the image as background: