Time-ordered networks (timeordered), a package for R
Benjamin Blonder (bblonder@email.arizona.edu)
Network analysis is a powerful and commonly used framework that can be used to describe the structure of a system. But extending network analysis to dynamics can be problematic because of uncertainties in the proper definition of a network. By construction, networks describe a fixed set of interactions between a fixed set of objects. These interactions can be instances of persistent relationships, probabilities for instantiating temporary relationships, or records of temporary relationships. If an investigator only collects data on observed interactions, what is the best way to aggregate these interactions into a network? How sensitive is this network to the investigator's assumptions about the different timescales inherent in the system?

I have developed the 'timeordered' package for R to address many of these concerns. The package extends the igraph library and provides a robust toolset for constructing networks with time dependences and for assessing the importance of time to these systems. The package has been tested on networks comprising thousands of interactions and contains algorithms that scale well to even larger data sets.
You can download the latest version of 'timeordered' from CRAN here. The full description:
Methods for incorporating time into network analysis. Construction of time-ordered networks (temporal graphs). Shortest-time and shortest-path-length analyses. Resource spread calculations. Data resampling and rarefaction for null model construction. Reduction to time-aggregated networks with variable window sizes; application of common descriptive statistics to these networks. Vector clock latencies. Plotting functionalities & full compatibility with all network methods in the igraph library.
Below are illustrated several examples of the package's functionality. In all cases data are excerpted from my recent study of information flow in ant colonies in collaboration with Anna Dornhaus at the University of Arizona. In this study, several hundred ants from four colonies were uniquely marked with paint. We recorded their in-nest activity with a high definition video camera and then determined the complete set of pairwise interactions between all individuals at all times. The data generated by this project is the sort used by timeordered: a list of the identities of interacting individuals, and the start/stop times of the interactions.

A fundamental concept is the time-ordered network. Individuals are ordinated along the x-axis and time increases along the y-axis. Vertical arrows are drawn to denote individuals remaining connected to themselves over time. Horizontal arrows are drawn between individuals at the start and stop times of the interaction. Tracing the paths that moves horizontally or up vertically lets us enumerate causally permitted pathways of resource flow. Such a structure captures all of the temporal information obtained by an investigator.
data(ants) g <- generatetonetwork(ants) plottonet(g,edgecolor="black")
Time-ordered networks can be collapsed into multiple time-aggregated networks of different sizes. Here, networks are shown with a time window of 100 units.
td100 <- generatetimedeltas(0,1500,100) ns100 <- generatenetworkslices(g, td100) plotnetworkslices(ns100, td100)
And here with a window of 500 units. Notice how the networks' topologies changes with window size.
td500 <- generatetimedeltas(0,1500,500) ns500 <- generatenetworkslices(g, td500) plotnetworkslices(ns500, td500)
We can make these structural metrics explicitly time dependent. Because timeordered is built on the igraph package, it is trivial to apply any network statistic to multiple time-aggregated networks constructued from a time-ordered network. Here, we see how network diameter varies at different time points and with window size.
md100 <- applynetworkfunction(ns100, function(x) {diameter(x)}) plot(midpoints(td100),unlist(md100),type="l",col="blue",xlab="Time",ylab="Network diameter") md500 <- applynetworkfunction(ns500, function(x) {diameter(x)}) lines(midpoints(td500),unlist(md500),col="red") legend("topleft",c("100 window size", "500 window size"),bty="n",lwd=2,col=c("blue","red"))
We can also look at how network statistics vary with increasingly large time windows. Here we see that network diameter first increases as more individuals are added to the network, then decreases as more individuals interact with each other.
tl100 <- generatetimelags(0,1500,100) nl100 <- generatenetworkslices(g, tl100) ml100 <- applynetworkfunction(nl100, function(x){diameter(x)}) plot(maxpoints(tl100),unlist(ml100),type="l",xlab="Aggregation time",ylab="Diameter",col="blue")
Testing the significance of different statistics under various null models can be important. The timeordered package provides robust tools for bootstrapping observed interaction data, based on conditions that can preserve interaction times or interaction partners, sampling with or without replacement, and stratifying within or across individuals. Here is a time-randomized time-ordered network constructed from the original data.
rt <- randomizetimes(ants,withinvertexfrom=T,byvertexfrom=T,withreplacement=T) plottonet(generatetonetwork(rt),edgecolor="black")
Network statistics may also be sensitive to sampling issues. The package provides functionality to simulate data rarefaction.
gshort <- generatetonetwork(rarefy(ants, 0.05)) plottonet(gshort)
The spread of a resource on a network can also be important in some situations. The package provides methods to assess how quickly a hypothetical resource can spread from different individuals.
sa <- spreadanalysis(g, seq(0,1000,by=50), 20) boxplot(sa[,-1],xlab="Time delay",ylab="Fraction reached") b <- transformspreadbyindividual(sa) plot(ts(b,delta=50),plot.type="single",col=rainbow(ncol(b)),xlab="Time",ylab="Fraction reached") legend("bottomright",colnames(b),lwd=1,col=rainbow(ncol(b)),bg="white")
Because of the likely heterogeneity in individuals' spreading potential, it can be important to assess the shortest paths between individuals in a network. Often the topologically shortest path in a time-aggregated network may not be the shortest path when a time constraint is added. Here a three-hop path is highlighted between two individuals at two times.
shp <- shortesthoppath(g,"WRRY", 243, "GBGR", 1186) plottonet(g, shp)
It is also possible to find shortest-time paths between individuals if no additional time constraint is imposed.
stp <- shortesttimepath(g, "WRRY", 243, "GBGR") plottonet(g, stp)
We can also efficiently calculate latencies between individuals - that is, minimum delay times between two individuals' hypothetical perfect communication. Here, these delay times are visualized at one time-point.
l <- generatelatencies(ants,allindivs=union(ants$VertexFrom, ants$VertexTo)) image(l[,,1000],axes=F,frame=T,col=rainbow(100)) axis(1, at = (1:ncol(l))/ncol(l), labels=colnames(l),tick=F,las=2,cex.axis=0.2) axis(2, at = (1:nrow(l))/nrow(l), labels=rownames(l),tick=F,las=2,cex.axis=0.2)

Last updated March 27, 2011.