Yesterday, the International Conference on Complex Systems wrapped up with five talks on networks. For me, the most interesting was that by Dan Braha, who spoke about what happens when you analyze a system as a network which changes over time, instead of the aggregate network formed by lumping all the timesteps together. Imagine a system made out of a whole pile of parts. At time [tex]t[/tex], part number [tex]i[/tex] might or might not be interacting with part number [tex]j[/tex], which we could represent as a time-varying matrix [tex]C_{ij}(t)[/tex]. Many studies of network-related phenomena obscure the time-dependence part. For example, in a living cell, genes are switching on and off, concentrations of enzymes are going up and down, and all sorts of stuff is changing over time. You can mix proteins A, B and C in a test tube; perhaps A bonds both to B and to C. You’d then draw an interaction network with links connecting A to B and to C — but what if B and C are never present in the cell at the same time?

Braha and company looked at a collection of e-mails sent over 113 days, exchanged among 57,138 users. (The data comes from arXiv:cond-mat/0201476v2, published five years ago in Phys. Rev. E, and were gathered at Kiel University.) A node is an individual e-mail address, and a link is established when a message is sent from one address to another. They found, among other things, that whether or not a particular node is a “hub” changes over time: popular today, an outcast tomorrow. Moreover, a node which is in the top 1000 most connected on one day may or may not be in the top 1000 for the aggregate network. Furthermoreover, when the window of aggregation is gradually increased — from one day to two days, to a week, up to the entire time period — the similarity to the total aggregate network increases, as you’d expect, but without any threshold.

In the last few minutes of his talk, Braha did a brief overview of a related investigation, in which they studied a “social network” derived from Bluetooth devices. If my Bluetooth gizmo is within two meters of yours, we’ll call that a link. The network of Bluetooth devices will naturally change over time, so we can do the same comparison between the graphs observed at short timesteps to the graph formed by aggregating all connections. During the Q&A session afterwards — before I had to, ironically enough, run off to find my cell phone — I pointed out something which it appears Braha hadn’t fully grasped.

Braha had done a motif analysis of the Bluetooth social network. This is essentially like asking the question, “In a soap opera of size [tex]N[/tex], how many love triangles will we find?” More formally, given some substantially large network, we count the number of times we find a particular subgraph, and we compare that count to the quantity we predict from some null hypothesis, such as a network connected at random. (Often, this involves generating a whole ensemble of randomized networks, counting the subgraph statistics of each one and taking the average, which gets to be a time-consuming process. Greg Egan probably won’t thank me for recalling the novel Quarantine to memory, but I have to say, sometimes the Ensemble is the most important thing in a researcher’s life.) A motif “profile” is a set of such measurements for several subgraphs; typically, one looks at subgraphs of three or four nodes.

When Braha put up his slide of the motif profiles, I thought immediately that they looked familiar, very familiar indeed. They were the same profiles I had found studying randomly generated spatial networks. Imagine throwing a whole bunch of nodes into a box, and connecting two of them whenever they fall closer together than some threshold distance. This gives you a spatial network: rather than a set of points only related by the links between them, the vertices have actual spatial coordinates. If the probability distribution for scattering the vertices is fairly uniform, you get a characteristic motif profile, with three out of the six possible four-node subgraphs more strongly represented than in the randomized ensemble. And Braha’s slide showed exactly that characteristic shape.

(I managed to figure that much out before finding Itzkovitz and Alon’s paper on the subject. The paper had been published, but weirdly, Google Scholar didn’t find it until after I had done a bunch of work and was about to present my results to a roomful of conference attendees.)

This is significant, because if you see a feature of your network which stays the same (or recurs cyclically) as the network changes over time, you’d think that it represents something important about the system. However, if all random spatial graphs have the same motif profile, then you might just be seeing the network breaking down and reforming itself randomly. (If you see a cyclic change, the network might be dissolving at periodic intervals, say when everybody goes home for the evening.) We have to be careful not to infer too much, because certain statistical properties of the network can be determined by its mere presence within an actual geometrical space.

REFERENCES:

• Jesper Dall, Michael Christensen. “Random Geometric Graphs” Phys. Rev. E 66, 016121 (2002).
• Itzkovitz, S., Alon, U. (2005). Subgraphs and network motifs in geometric networks. Physical Review E, 71(2) DOI: 10.1103/PhysRevE.71.026117; arXiv:cond-mat/0409163.