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.

• $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)

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.