text: The advent of social media has provided data and insights about how people relate to information and culture. While information is composed by bits and its fundamental building bricks are relatively well understood, the same cannot be said for culture. The fundamental cultural unit has been defined as a "meme". Memes are defined in literature as specific fundamental cultural traits, that are floating in their environment together. Just like genes carried by bodies, memes are carried by cultural manifestations like songs, buildings or pictures. Memes are studied in their competition for being successfully passed from one generation of minds to another, in different ways. In this paper we choose an empirical approach to the study of memes. We downloaded data about memes from a well-known website hosting hundreds of different memes and thousands of their implementations. From this data, we empirically describe the behavior of these memes. We statistically describe meme occurrences in our dataset and we delineate their fundamental traits, along with those traits that make them more or less apt to be successful.
  @cite_22: The wide adoption of social media has increased the competition among ideas for our finite attention. We employ a parsimonious agent-based model to study whether such a competition may affect the popularity of different memes, the diversity of information we are exposed to, and the fading of our collective interests for specific topics. Agents share messages on a social network but can only pay attention to a portion of the information they receive. In the emerging dynamics of information diffusion, a few memes go viral while most do not. The predictions of our model are consistent with empirical data from Twitter, a popular microblogging platform. Surprisingly, we can explain the massive heterogeneity in the popularity and persistence of memes as deriving from a combination of the competition for our limited attention and the structure of the social network, without the need to assume different intrinsic values among ideas.
  @cite_8: In networks, contagions such as information, purchasing behaviors, and diseases, spread and diffuse from node to node over the edges of the network. Moreover, in real-world scenarios multiple contagions spread through the network simultaneously. These contagions not only propagate at the same time but they also interact and compete with each other as they spread over the network. While traditional empirical studies and models of diffusion consider individual contagions as independent and thus spreading in isolation, we study how different contagions interact with each other as they spread through the network. We develop a statistical model that allows for competition as well as cooperation of different contagions in information diffusion. Competing contagions decrease each other's probability of spreading, while cooperating contagions help each other in being adopted throughout the network. We evaluate our model on 18,000 contagions simultaneously spreading through the Twitter network. Our model learns how different contagions interact with each other and then uses these interactions to more accurately predict the diffusion of a contagion through the network. Moreover, the model also provides a compelling hypothesis for the principles that govern content interaction in information diffusion. Most importantly, we find very strong effects of interactions between contagions. Interactions cause a relative change in the spreading probability of a contagion by em 71 on the average.
  @cite_6: Viral diffusion allows a piece of information to widely and quickly spread within the network of users through word-ofmouth. In this paper, we study the problem of modeling both item and user factors that contribute to viral diffusion in Twitter network. We identify three behaviorial factors, namely user virality, user susceptibility and item virality, that contribute to viral diffusion. Instead of modeling these factors independently as done in previous research, we propose a model that measures all the factors simultaneously considering their mutual dependencies. The model has been evaluated on both synthetic and real datasets. The experiments show that our model outperforms the existing ones for synthetic data with ground truth labels. Our model also performs well for predicting the hashtags that have higher retweet likelihood. We finally present case examples that illustrate how the models differ from one another.
  @cite_0: We introduce a novel frequent pattern mining approach to discover leaders and tribes in social networks. In particular, we consider social networks where users perform actions. Actions may be as simple as tagging resources (urls) as in del.icio.us, rating songs as in Yahoo! Music, or movies as in Yahoo! Movies, or users buying gadgets such as cameras, handhelds, etc. and blogging a review on the gadgets. The assumption is that actions performed by a user can be seen by their network friends. Users seeing their friends' actions are sometimes tempted to perform those actions. We are interested in the problem of studying the propagation of such "influence", and on this basis, identifying which users are leaders when it comes to setting the trend for performing various actions. We consider alternative definitions of leaders based on frequent patterns and develop algorithms for their efficient discovery. Our definitions are based on observing the way influence propagates in a time window, as the window is moved in time. Given a social graph and a table of user actions, our algorithms can discover leaders of various flavors by making one pass over the actions table. We run detailed experiments to evaluate the utility and scalability of our algorithms on real-life data. The results of our experiments confirm on the one hand, the efficiency of the proposed algorithm, and on the other hand, the effectiveness and relevance of the overall framework. To the best of our knowledge, this the first frequent pattern based approach to social network mining.
  @cite_15: If a false rumor propagates via Twitter, while the truth propagates between friends in Facebook, which one will prevail? This question captures the essence of the problem we address here. We study the intertwined propagation of two competing "memes" (or viruses, rumors, products etc.) in a composite network. A key novelty is the use of a composite network, which in its simplest model is defined as a single set of nodes with two distinct types of edges interconnecting them. Each meme spreads across the composite network in accordance to an SIS-like propagation model (a flu-like infection-recovery). To study the epidemic behavior of our system, we formulate it as a non-linear dynamic system (NLDS). We develop a metric for each meme that is based on the eigenvalue of an appropriately constructed matrix and argue that this metric plays a key role in determining the "winning" meme. First, we prove that our metric determines the tipping point at which both memes become extinct eventually. Second, we conjecture that the meme with the strongest metric will most likely prevail over the other, and we show evidence of that via simulations in both real and synthetic composite networks. Our work is among the first to study the interplay between two competing memes in composite networks.
  @cite_16: In the last decade, Social Network Analysis has been a field in which the effort devoted from several researchers in the Data Mining area has increased very fast. Among the possible related topics, the study of the information propagation in a network attracted the interest of many researchers, also from the industrial world. However, only a few answers to the questions "How does the information propagates over a network, why and how fast?" have been discovered so far. On the other hand, these answers are of large interest, since they help in the tasks of finding experts in a network, assessing viral marketing strategies, identifying fast or slow paths of the information inside a collaborative network. In this paper we study the problem of finding frequent patterns in a network with the help of two different techniques: TAS (Temporally Annotated Sequences) mining, aimed at extracting sequential patterns where each transition between two events is annotated with a typical transition time that emerges from input data, and Graph Mining, which is helpful for locally analyzing the nodes of the networks with their properties. Finally we show preliminary results done in the direction of mining the information propagation over a network, performed on two well known email datasets, that show the power of the combination of these two approaches.
  @cite_10: Theoretical models suggest that social networks influence the evolution of cooperation, but to date there have been few experimental studies. Observational data suggest that a wide variety of behaviors may spread in human social networks, but subjects in such studies can choose to befriend people with similar behaviors, posing difficulty for causal inference. Here, we exploit a seminal set of laboratory experiments that originally showed that voluntary costly punishment can help sustain cooperation. In these experiments, subjects were randomly assigned to a sequence of different groups to play a series of single-shot public goods games with strangers; this feature allowed us to draw networks of interactions to explore how cooperative and uncooperative behaviors spread from person to person to person. We show that, in both an ordinary public goods game and in a public goods game with punishment, focal individuals are influenced by fellow group members’ contribution behavior in future interactions with other individuals who were not a party to the initial interaction. Furthermore, this influence persists for multiple periods and spreads up to three degrees of separation (from person to person to person to person). The results suggest that each additional contribution a subject makes to the public good in the first period is tripled over the course of the experiment by other subjects who are directly or indirectly influenced to contribute more as a consequence. These results show experimentally that cooperative behavior cascades in human social networks.
  @cite_11: Tracking new topics, ideas, and "memes" across the Web has been an issue of considerable interest. Recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. However, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days - the time scale at which we perceive news and events. We develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. As our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle - the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. We tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. In particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a "heartbeat"-like pattern in the handoff between news and blogs. We also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.
summary: In the Introduction we stated that there are several works studying internet memes. For example, @cite_15 studies the dynamics of competitions of memes spreading in two distinct social networks on different social media (Facebook and Twitter). Also @cite_22 addresses the problem of competition among memes, assuming that each user can follow only a handful of memes at the same time. Meme and information spread is also a problem definition addressed in computer science with different methodological approaches: works like @cite_0 , @cite_6 and @cite_16 provide algorithms and frameworks to analyze how information spreads in a network of people. While those papers examine different cascade information spreads as independent, in @cite_8 different spread events on the same network are analyzed at the same time, as different memes influence each other while trying to span on the same set of minds. Other computer science tools help us tracking memes over the Web @cite_11 . As an application, @cite_10 deals with cooperative behavior.