Information cascades are ubiquitous in both physical society and online social media, taking on large variations in structures, dynamics and semantics. Although the dynamics and semantics of information cascades have been studied, the structural patterns and their correlations with dynamics and semantics are largely unknown. Here we explore a large-scale dataset including @math million information cascades with explicit records of spreading traces, spreading behaviors, information content as well as user profiles. We find that the structural complexity of information cascades is far beyond the previous conjectures. We first propose a ten-dimensional metric to quantify the structural characteristics of information cascades, reflecting cascade size, silhouette, direction and activity aspects. We find that bimodal law governs majority of the metrics, information flows in cascades have four directions, and the self-loop number and average activity of cascades follows power law. We then analyze the high-order structural patterns of information cascades. Finally, we evaluate to what extent the structural features of information cascades can explain its dynamic patterns and semantics, and finally uncover some notable implications of structural patterns in information cascades. Our discoveries also provide a foundation for the microscopic mechanisms for information spreading, potentially leading to implications for cascade prediction and outlier detection.
We presented related work in three dimensions: cascade structures, dynamics and topics. The cascade structures have been studied in different scenarios, including blogs @cite_1 @cite_24 @cite_27 , communication network @cite_6 , Facebook @cite_12 , Twitter @cite_32 , LinkedIn @cite_31 . , or to infer structures @cite_4 . Deep-tree structures are found and modeled in Ref. @cite_19 . Goel @cite_22 studied the virality of cascades by using Wiener index. However, we find information flows in cascades have four directions, indicating complex structures than tree patterns. Furthermore, ignoring the high-order correlations between structure metrics in previous studies prevent our understandings of cascade structures.
@cite_4 @cite_22 @cite_1 @cite_32 @cite_6 @cite_24 @cite_19 @cite_27 @cite_31 @cite_12
2398526644 2289705509 1964245472 2950143436
Cascades are a popular construct to observe and study information propagation (or diffusion) in social media such as Twitter. and are defined using notions of influence, activity, or discourse commonality (e.g., hashtags). While these notions of cascades lead to different perspectives, primarily cascades are modeled as trees. We argue in this paper an alternative viewpoint of cascades as forests (of trees) which yields a richer vocabulary of features to understand information propagation. We develop a framework to extract forests and analyze their growth by studying their evolution at the tree-level and at the node-level. Moreover, we demonstrate how the structural features of forests, properties of the underlying network, and temporal features of the cascades provide significant predictive value in forecasting the future trajectory of both size and shape of forests. We observe that the forecasting performance increases with observations, that the temporal features are highly indicative of cascade size, and that the features extracted from the underlying connected graph best forecast the shape of the cascade. Information cascades on social networks, such as retweet cascades on Twitter, have been often viewed as an epidemiological process, with the associated notion of virality to capture popular cascades that spread across the network. The notion of structural virality or average path length has been posited as a measure of global spread. In this paper, we argue that this simple epidemiological view, though analytically compelling, is not the entire story. We first show empirically that the classical SIR diffusion process on the Twitter graph, even with the best possible distribution of infectiousness parameter, cannot explain the nature of observed retweet cascades on Twitter. More specifically, rather than spreading further from the source as the SIR model would predict, many cascades that have several retweets from direct followers, die out quickly beyond that. We show that our empirical observations can be reconciled if we take interests of users and tweets into account. In particular, we consider a model where users have multi-dimensional interests, and connect to other users based on similarity in interests. Tweets are correspondingly labeled with interests, and propagate only in the subgraph of interested users via the SIR process. In this model, interests can be either narrow or broad, with the narrowest interest corresponding to a star graph on the interested users, with the root being the source of the tweet, and the broadest interest spanning the whole graph. We show that if tweets are generated using such a mix of interests, coupled with a varying infectiousness parameter, then we can qualitatively explain our observation that cascades die out much more quickly than is predicted by the SIR model. In the same breath, this model also explains how cascades can have large size, but low "structural virality" or average path length. Cascades appear in many applications, including biological graphs and social media analysis. In a cascade, a dynamic attribute propagates through a graph, following its edges. We present the results of a formal user study that tests the effectiveness of different types of cascade visualisations on node-link diagrams for the task of judging cascade spread. Overall, we found that a small multiples presentation was significantly faster than animation with no significant difference in terms of error rate. Participants generally preferred animation over small multiples and a hierarchical layout to a force-directed layout. Considering each presentation method separately, when comparing force-directed layouts to hierarchical layouts, hierarchical layouts were found to be significantly faster for both presentation methods and significantly more accurate for animation. Representing the history of the cascade had no significant effect. Thus, for our task, this experiment supports the use of a small multiples interf... Information spreads across social and technological networks, but often the network structures are hidden from us and we only observe the traces left by the diffusion processes, called cascades. Can we recover the hidden network structures from these observed cascades? What kind of cascades and how many cascades do we need? Are there some network structures which are more difficult than others to recover? Can we design efficient inference algorithms with provable guarantees? Despite the increasing availability of cascade data and methods for inferring networks from these data, a thorough theoretical understanding of the above questions remains largely unexplored in the literature. In this paper, we investigate the network structure inference problem for a general family of continuous-time diffusion models using an @math -regularized likelihood maximization framework. We show that, as long as the cascade sampling process satisfies a natural incoherence condition, our framework can recover the correct network structure with high probability if we observe @math cascades, where @math is the maximum number of parents of a node and @math is the total number of nodes. Moreover, we develop a simple and efficient soft-thresholding inference algorithm, which we use to illustrate the consequences of our theoretical results, and show that our framework outperforms other alternatives in practice.