Constructing Influence Trees from Temporal Sequence of Retweets: An Analytical Approach

摘要

Twitter is currently a popular microblogging platform for the dissemination of information by users in the form of messages such as tweets. Such tweets are shared with followers of the seed user who in turn may reshare it with their own set of followers. Long chain of such retweets form cascades. In this paper, we aim to estimate the influence tree of cascades denoting the who-influenced-whom relationship among retweeting users by leveraging on temporal pattern of its retweets. We use a principled methodology to construct the ground truth influence trees of cascades using standard diffusion models. We define diverse structural metrics to quantify the structural characteristics of different influence trees. Based on empirical observations from ground truth, we develop CasCon, an unsupervised model that leverages on temporal pattern of retweets obtained from time series of cascades and underlying follower network of Twitter to construct influence trees. Further, we provide an analytical formulation of CasCon by deriving the degree distribution of these predicted influence trees and use it to approximate the structural metrics. Our evaluation shows that CasCon exhibits superior performance compared to state-of-theart baseline algorithms in selecting influencers of high quality based on standard influence measures in Twitter as well as in correctly (re)constructing the ground truth influence trees with high accuracy. Finally, we validate the analytical formulation of CasCon on the influence tree structures of both synthetic and real cascades; experimental results demonstrate its effectiveness in closely resembling ground truth influence trees for empirical cascades with high retweet count.