Competing memes propagation on networks: a case study of composite networks

By: 
Xuetao Wei, Nicholas Valler, B. Aditya Prakash, Iulian Neamtiu, Michalis Faloutsos, Christos Faloutsos
Appears in: 
CCR October 2012

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.

Public Review By: 
Augustin Chaintreau

Friend me on Facebook, Follow me on Twitter, Connect me on LinkedIn, Enter my Google Circles.” As we are multiplying social channels of communication these start to interact! In fact, it becomes increasingly difficult in the study of information propagation on social networks to be sure that a given individual who was not yet exposed to a meme has actually not heard about it in another way. In other words, we may very well enter an era where no social networks operate in isolation. This, is what this paper proposes to study with a simple example of “composite networks”. Imagine all cases where memes are competing. Being early is often all that counts so one can easily imagine a speed race between a rumor and its denial, where all individuals act according to their first exposure (clicking on a link or in contrast be careful if warned). Or the competition between two substitutable products that are promoted at similar time on different media. Previous works have considered this angle only from a single network point of view. This work suggests that as different channels become viral differently, one need to study this propagation on the composite network. In this paper, you will find these dynamics formulated as an extension of classical epidemiological model, a characterization of the limit regime where individuals both become susceptible and recover slowly. This allow one to use a simple decomposition of this competition that yields some conditions for stability, generalizing previous epidemiological studies with differential equations. The main merit of these results is to introduce the eigenvalues of interest for these systems, that are also proved numerically to characterize well this system. Reviewers were unanimous in finding this problem timely and novel, and the contribution substantial, which by itself justify its appearance in CCR. We leave it as a general question to be discussed of what is “computer networking,” especially since this paper deals with this problem in abstract, with no reference to a practical implementation of social dissemination. It seems clear to us that we should welcome paper that broaden our horizon and pose new problems of interests in related fields, such as the one predicting how information gets diffused on social applications. Most concerns and criticism relate to the narrowness of the model, with a curious mix of repetitive susceptibility and insensitivity to other meme, simultaneous start of epidemics, not to mention that in reality the networks may not be entirely disjoint – although this last point could probably be accounted for. Another important limitation is that the analysis uses simultaneously two simplifications: On the one hand, infinitely slow propagation/recovery, and on the other hand, the asymptotic version of stability – in other words, resistance to infinitesimal change – found in previous article on non-linear dynamical system). Without being contradictory, this significantly constrains the analysis to a regime with minimal (but not inexistent) interaction. You may also question the use of data set from calls and SMS as competing, but truly this serves only the purpose to test if such theory fits well the behavior of a real topology. All the concerns above are important, but do not diminish the potential impact of this article to inspire more works and get us to think differently about our multiple connected work. Following CCR’s tradition, we privileged impact and timeliness, which is really what 6 pages can be about. If you are now desperately trying to choose which social media to ask me to connect in order to best influence me - who knows? maybe for future CCR issues - this paper will not entirely solve your problem. However, you may want to read it and start following one of the open directions that it creates to find ultimately the answer.