Dan Cosley, AAAI, 2010

Citation

Dan Cosley, Daniel Huttenlocher, Jon Kleinberg, Xiangyang Lan, Siddarth Suri. Sequential Influence Models in Social Network. Association for the Advancement of Artificial Intelligence. 2010.

Online Version

http://www.cs.cornell.edu/home/kleinber/icwsm10-seq.pdf

Databases

Wikipedia [1]

Summary

In this paper, the authors consider two of the most fundamental definitions of influence, one based on a small set of “snapshot” observations of a social network and the other based on detailed temporal dynamics. The former is particularly useful because large-scale social network data sets are often available only in snapshots or crawls. The latter however provides a more detailed process model of how influence spreads. The authors studied the relationship between these two ways of measuring influence, in particular establishing how to infer the more detailed temporal measure from the more readily observable snapshot measure. It validates the analysis using the history of social interactions on Wikipedia; the result is the first large-scale study to exhibit a direct relationship between snapshot and temporal models of social influence.

Brief Description Of The Method

In order to study a method to measure influence, this paper gives two definitions of social influence: Ordinal-time and Snapshot, then it defines some notation for various sets of tuples. At last, it gives a method about how to Simulating Ordinal Time from Snapshots.

Defination:

• $B\left(t_{1}\right)=\left\{\left(u,C,k_{1}\right)\right\}$: u joined C before t1 and u had k1 neighbors in C at t1.

• $J\left(t_{1},t_{2}\right)=\left\{\left(u,C,k_{1},k_{k2}\right)\right\}$: u had k1 neighbors in C at t1, u joined C between t1 and t2, u had k2 neighbors in C at t2.

• $N\left(t_{2}\right)=\left\{\left(u,C,k_{k2}\right)\right\}$: u did not join C before t2 and u had k2 neighbors in C at t2.

The sets B and N result in shifting no and do upwards with respect to $n_{s}$ and $d_{s}$. Also, the set J results in stretching $n_{o}$ and $d_{o}$ when compared $n_{s}$ and $d_{s}$. Finally, the sets J and N result in $d_{o}$ becoming an accumulation or integration of $d_{s}$.

Experimental Result

• For the English Wikipedia data, Figure 3(a) shows the plots of $n_{o}\left(k\right)$ and $d_{o}\left(k\right)$ on a log-log scale, along with the best linear fit. A linear model accounts relatively well for the data over a large range, suggesting a power law is a reasonable approximation for each of these quantities. This is not surprising, given that $d_{o}\left(k\right)$ can be viewed as a variation on the standard degree distribution: it measures the distribution of the “degree” (number of edges) of each node into each community.

• Using the Wikipedia ordinal time data the authors generated two snapshots, choosing November 1, 2005 and November 6, 2006 as two relatively arbitrary moments at which which they measure the full set of community memberships. It then computed p (k) using the snapshot method, shown in Figure 3(b).

• The approximation of ordinal time data from snapshot data depends on two factors: the number of snapshots used, and the amount of time between the snapshots. The authors begin by considering the effect of the number of snapshots. They show how the simulation of ordinal-time depends on the number of snapshots taken for English Wikipedia in figure below.

As one would expect, the approximation is becoming increasingly accurate with more snapshots. This is because as the number of snapshots increases the time between them goes to 0. Thus, in the limit, snapshot measurements converge to the ordinal-time measurements. This figure shows that empirically just a few snapshots produce good results for these datasets which means the convergence occurs fairly rapidly as the number of snapshots increases.

Related papers

This paper uses conclusions in Measuring wikipedia to compare with its experimental result.

Feedback effects between similarity and social influence in online communities.