They define a dynamic graph as an evolving graph where vertices and edges are added and removed over time. More formally, , a dynamic graph, is an ordered swquence of subgraphs where each is the subgraph of at time . The edges and vertices of each subgraph are non-disjointed sets, with and being their unions. So, an edge can be in multiple subgraphs if it appears across multiple time points, and likewise for a vertex. What happens if a vertex changes value over time? Are they considered the same vertex? Can we still link the two vertices as the same?
Problems with previous approaches: stability of the layout. Previous work graphed each time step individually, then either displayed them as a movie or next to each other. These authors look at clusterings across time, and produce time-varying clusters that link clusters across time to better stabilize the cross-time display.
The authors define an ordering of clusters using a weighted quotient graph, where each node is a time-varying cluster of and edges exist between nodes if there are shared nodes in the clusters. Edge weights are the number of shared nodes. They define the Linear arrangement function to find an ordering (see page 5).
A case study of autonomous systems on the internet among countries is used.
Without proving, they show their approach takes to draw a time-line ( time steps, nodes), to layout a graph, and to render the graph ( edges). However, there is “a long time” for preprocessing.
Assumption: Longitudinal network data, a “time-ordered sequence of interrelated network observations that possibly differ in actor composition, structure, and attributes.” Their problem is defined as visualizing a given sequence of snapshots of an evolving social network, with intelligible connections between time slices (snapshots) so that the changes can be easily distinguished.
They consider only a node-link diagram, with actors as vertices and ties are edges. There are 4 objectives in layout (with reference, page 4):
Specifically, the authors abandon the force-directed methods commonly used for the older stress minimization, or multidimensional scaling.
When drawing dynamic visualizations of social networks, knowledge of the future changes can aid in organizing the network layout. Can we store this information in our time-dependent data structures? Can we capture this change information and use it to display the future/past? The authors of this paper assume an offline model, so they know the future structure of the social network when trying to visualize the structure at any point in time.
Current proposals for addressing stability in dynamic network visualization are:
Case study: connections among 69 students at 15 intervals over a 1.5 year period.
Resources: Long list of social network visualization papers on page 2 (second paragraph).
The authors define two types of movies of social network visualization:
Addresses discrete versus continuous time. Discrete time consists of cross-sectional snapshots of the network, are cheaper and easier to implement. Continuous time consists of streaming relational events and interactions that have exact start/end points (ordered dyadic events). This is the kind of time we want to consider in both SNAC and the Mormon marriages. It’s possible to aggregate continuous time into discrete points, but not vice versa. The authors use a time window that spans a set of relational events into one aggregation of the network (note: this means that some lengths are incorrect–residues–since the continuous end-point may be at the beginning of the window, but the event has been considered to be occurred during the entire window). See figure 1, page 1213.
Social distance: the length of the shortest path in the network connecting two nodes.
Graph layout algorithms include
Resources: Freeman 2000b, good review of history of network visualization.