Affiliations: [a] Marketing Intelligence, trivago N.V., Germany. E-mail: sarah.elsharkawy@trivago.com | [b] Faculty of Computer and Information Sciences, Ain Shams University and The British University, Egypt. E-mail: ghada.hassan@bue.edu.eg | [c] Research and Development Department, ITWORX, Egypt. E-mail: tarek.nabhan@itworx.com | [d] Faculty of Computer and Information Sciences, Ain Shams University, Egypt. E-mail: mroushdy@cis.asu.edu.eg
Abstract: Current research on modelling information diffusion in social media focuses on studying individual information cascades independently. However, as a meme spreads, it evolves, and users adopt the meme in a variety of manners. While individual information cascades can model the propagation of a single piece of information among users, they are not useful in studying the propagation of the whole meme. Modelling the propagation of the whole meme has the ability to describe how users, who adopt the meme, are related to each other, identify who the seed author of the meme is, and recognize the main spreaders of this meme. In this work, we generalize the modelling of independent information cascades to model the diffusion of a meme. We argue that modelling information diffusion as a meme adoption graph (MAG), where each MAG comprises many contributing information cascades, offers a more comprehensive view of the larger scale meme adoption pattern. Hence presents a richer platform to study and monitor the information diffusion pattern of the generalized meme. To construct the MAG that represents the meme diffusion, we first identify messages related to a meme from the social network stream. We utilize a recent clustering algorithm to automatically extract and cluster tweets from the Twitter stream. Next, we evaluate and compare three epidemic models, typically used to construct individual information cascades. We then propose a set of structural characteristics derived from the MAG analysis that describe the underlying meme adoption pattern. Mainly, we focus on the influential spreaders, community formation, and virality measures of the generalized meme. An empirical study, using four real-world Twitter datasets, demonstrates the effectiveness of the proposed MAG. For each dataset, the structural properties of the MAG are derived and compared to the characteristics derived from the independent cascades.
Keywords: Meme adoption pattern, information diffusion, social networks, graph theory, epidemic modelling