Modeling Morphology of Social Network Cascades

Cascades represent an important phenomenon across vari-ous disciplines such as sociology, economy, psychology, po-litical science, marketing, and epidemiology. An important property of cascades is their morphology, which encompasses the structure, shape, and size. However, cascade morphol-ogy has not been rigorously characterized and modeled in prior literature. In this paper, we propose a Multi-order Markov Model for the Morphology of Cascades (M4C) that can represent and quantitatively characterize the morphol-ogy of cascades with arbitrary structures, shapes, and sizes. M4C can be used in a variety of applications to classify different types of cascades. To demonstrate this, we apply it to an unexplored but important problem in online social networks – cascade size prediction. Our evaluations using real-world Twitter data show that M4C based cascade size prediction scheme outperforms the baseline scheme based on cascade graph features such as edge growth rate, degree distribution, clustering, and diameter. M4C based cascade size prediction scheme consistently achieves more than 90% classification accuracy under different experimental scenar-ios