  How does information flow in online social networks? How does the structure
and size of the information cascade evolve in time? How can we efficiently mine
the information contained in cascade dynamics? We approach these questions
empirically and present an efficient and scalable mathematical framework for
quantitative analysis of cascades on networks. We define a cascade generating
function that captures the details of the microscopic dynamics of the cascades.
We show that this function can also be used to compute the macroscopic
properties of cascades, such as their size, spread, diameter, number of paths,
and average path length. We present an algorithm to efficiently compute cascade
generating function and demonstrate that while significantly compressing
information within a cascade, it nevertheless allows us to accurately
reconstruct its structure. We use this framework to study information dynamics
on the social network of Digg. Digg allows users to post and vote on stories,
and easily see the stories that friends have voted on. As a story spreads on
Digg through voting, it generates cascades. We extract cascades of more than
3,500 Digg stories and calculate their macroscopic and microscopic properties.
We identify several trends in cascade dynamics: spreading via chaining,
branching and community. We discuss how these affect the spread of the story
through the Digg social network. Our computational framework is general and
offers a practical solution to quantitative analysis of the microscopic
structure of even very large cascades.
