John and I spent about an hour talking, last weekend, and decided that what we needed to do was to look at temporal patterns of tagging between members of a network on delicious, to get a sense of how particular ideas or topics were getting shuttled around that network. I had already spent an hour or two writing a little Java code to parse and represent the contents of a complete feed, as output by the delicious "export" feature. It didn't take much more work after that to take a tag, and calculate (for two given feeds) the average time between the use of that tag by one person and the use of the same tag by another, and then rank the tags by that average-time-to-reposting score. And the "results," such as they were, were tantalizing enough that I decided to write this up a little bit here and keep thinking about it. But really, this is just some brain-dead parsing and counting, nothing more. I wouldn't even try to make the claim that the code is entirely correct, much less that it's calculating anything interesting. So we're going to keep thinking about this... but so far this is just the output of about an hour of batting around ideas on the phone, followed by about three person-hours of programming, so take it all with a giant grain of salt.
JAR file: delicious.jar
(It should run from the command line with a command "java -jar delicious.jar")
Current code: 03-39-2009
Old code:
Code Instructions: unzip, compile, and run tdanford.delicious.Main -- however, there are some hard-coded file names in the main method of that class, so you probably need to modify those by hand first.
John and I both took snapshots of our delicious feeds, "for Science."
Anyone else want to chip in?When you run the Main class, it produces (on standard output) two top-10 lists:
Parsed: john-delicious.htm Parsed: tim-delicious.htm # Shared Links: 196 # Shared Tags: 479 John->Tim: 6099.58 advertising 5669.56 information 5460.69 thesis 4844.16 3d 4839.52 architecture 4713.05 clothing 4445.90 art 4419.32 3931.88 interactive 3917.26 processing Tim->John: 11214.66 internet 10950.10 economics 9518.67 politics 9282.37 privacy 9003.19 yahoo 8634.27 database 8395.72 sports 8380.30 python 8232.66 java 7868.22 security(I'm not sure what that blank is, in the 8th line of the John->Tim line? A data-processing error, maybe?)
It also opens a window with two lists of tags. If you highlight one or more of the tags from each of the lists, and click the 'View' button, it will open a second window with a quick diagram of two time series. Each series shows all the timepoints when a link with the corresponding tag(s) was saved, and it looks something like the picture to the right.
That's two time-series of several combined tags, including "computers" and "technology". My links are graphed in red, John's in blue... and, yeah, I don't even know if that's showing anything interesting. Probably not. It's hard to interpret raw time series of discrete points like this, visually! I should just go ahead and graph the actual distribution of inter-tag distances, since that's what the ranking is operating on anyway.
Today, I've been working on a slightly different way of visualizing the time differences -- I flip the upper (red) track upside down, and then draw orange lines between them to display the "nearest previous tags" for each event in the blue track on the bottom. The picture to the right is the "chess" tag, for John and myself.
A more principled way of thinking about this might involve imagining the time-series of a user's use of a specific tag as a Poisson process — specifically, a non-homogeneous Poisson process whose intensity function depends on the corresponding time-series of one or more members of that user's network. We could imagine setting up a parametric model for one NHPP dependence on another, and then estimating the parameters of that model using a least-squares approach.
(I think this would mean that, in general, the a general time-series of tags would be a hierarchical, or compound, Poisson process? But I don't want to get into that quite yet.)
Let's let u indicate the particular user whose use of a tag we want to model, and let v indicate his or her neighbor (in our context here, u could be "Tim," and v could be "John"). I'll use the variable u_i to indicate the arrival time of the i-th link with the given tag in the first user's tag-stream, and v_i to indicate the corresponding variable of the second user.
Our model will have three parameters: (B, G0, G1), which correspond to a 'baseline' intensity, the height of a 'response' of user u to user v, and the 'falloff' of that response over time.
This means that, at time t, the user u has an intensity function:
where the \sigma function is an indicator function which is 1 if t > v_i and 0 otherwise.
I don't have this functional form quite right -- I obviously want a function that "jumps up" after user v tags a link, and then "falls off" back to zero (and hence, the intensity function returns to baseline) as time moves forward afterwards. This form doesn't do quite what I want, I want some exponential form instead, but I haven't worked out the details yet.
Given that this is roughly what I'm thinking at the moment, the next step (I guess) is to incorporate the calculation of this expected intensity function, given its parameters, into the code base. As Kuhl and Wilson suggest, I think it shouldn't be too hard to work up a Nelder-Mead simplex-type optimization for that function. There are also some details as to whether to use a weighted least squares optimization, or a "variance stabilized" OLS version of the same; I'll probably go with the OLS version, since they recommend that and the core machinery doesn't actually look very different.
Places where I know I've gone wrong:
- OmG, it's terribly skewed towards tags that don't have many links at all or that were only used heavily over a short period of time. This is totally throwing off a lot of the numbers, I know.
- "Average time between tags" is really not the right thing to be calculating.
- I'm just looking at tags, not links, for the above analysis. But I should pay attention to "via:X" tags in particular, and to instances where the same link appears successively in two peoples' feeds. If I "got" an advertising link from someone else, then it shouldn't "count towards" the John->Tim advertising permissivity.
- Some links are more likely to be passed along than others.
- Tags are not a perfect indicator for ideas -- ideally, this analysis could be run on clusters of tags.
- A particular tag definitively does not mean the same thing for each user. My example of this to John was that I will use the tag "architecture" to mean something very different than he will (some of my uses of that tag will mean "computer architecture," while John's will mostly be building architecture). This is a similar, but not the same, issue to the point about tag clustering above.
At one point, I wrote this in an email to Cosma Shalizi:
I was thinking that my next step would be to starting thinking about estimating some kind of multilevel model, with some kind of exponential distribution for the waiting times between successive tag points, and with a different distribution estimated for each tag (and maybe each pair of users).To which he replied, in part, "this sounds reasonable in words," but (to be honest) I don't even know if that makes any sense to me any more.
Later, Cosma replied,
I guess the model I had in mind was one where, after user A saves an item, there is a certain conditional intensity function for user B saving it, which depends on the order pair (A,B) and the tags.I think there's something strange about the part "after A saves an item," because doesn't this depend on matching closest tag-uses between users? Which is something I'm doing now, but seems like it's not quite the right thing -- you want some kind of probability which declines over the entire number line... no I'm not saying that right.
p(t_i) = f( b_i + a_1 * d_1 + ... + a_N * d_N )
I want to model a term like p(t_i), the probability ("for a given unit of time?" I'm not clear...) of a user producing a link with a tag t_i. This probability depends on some baseline probability for the tag, b_i, as well as connections from all the members of this person's network -- 1 to N. We'll let d_j be the amount of time (the "delay") elapsed since member j of the network used "the same" tag, and we'll let a_j be a parameter that we need to estimate, along with the b baseline parameters.