text: Suppose we have a virus or one competing idea product that propagates over a multiple profile (e.g., social) network. Can we predict what proportion of the network will actually get "infected" (e.g., spread the idea or buy the competing product), when the nodes of the network appear to have different sensitivity based on their profile? For example, if there are two profiles @math and @math in a network and the nodes of profile @math and profile @math are susceptible to a highly spreading virus with probabilities @math and @math respectively, what percentage of both profiles will actually get infected from the virus at the end? To reverse the question, what are the necessary conditions so that a predefined percentage of the network is infected? We assume that nodes of different profiles can infect one another and we prove that under realistic conditions, apart from the weak profile (great sensitivity), the stronger profile (low sensitivity) will get infected as well. First, we focus on cliques with the goal to provide exact theoretical results as well as to get some intuition as to how a virus affects such a multiple profile network. Then, we move to the theoretical analysis of arbitrary networks. We provide bounds on certain properties of the network based on the probabilities of infection of each node in it when it reaches the steady state. Finally, we provide extensive experimental results that verify our theoretical results and at the same time provide more insight on the problem.
  @cite_20: 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_12: Suppose we have two competing ideas products viruses, that propagate over a social or other network. Suppose that they are strong virulent enough, so that each, if left alone, could lead to an epidemic. What will happen when both operate on the network? Earlier models assume that there is perfect competition: if a user buys product 'A' (or gets infected with virus 'X'), she will never buy product 'B' (or virus 'Y'). This is not always true: for example, a user could install and use both Firefox and Google Chrome as browsers. Similarly, one type of flu may give partial immunity against some other similar disease. In the case of full competition, it is known that 'winner takes all,' that is the weaker virus product will become extinct. In the case of no competition, both viruses survive, ignoring each other. What happens in-between these two extremes? We show that there is a phase transition: if the competition is harsher than a critical level, then 'winner takes all;' otherwise, the weaker virus survives. These are the contributions of this paper (a) the problem definition, which is novel even in epidemiology literature (b) the phase-transition result and (c) experiments on real data, illustrating the suitability of our results.
  @cite_6: Given two competing products (or memes, or viruses etc.) spreading over a given network, can we predict what will happen at the end, that is, which product will 'win', in terms of highest market share? One may naively expect that the better product (stronger virus) will just have a larger footprint, proportional to the quality ratio of the products (or strength ratio of the viruses). However, we prove the surprising result that, under realistic conditions, for any graph topology, the stronger virus completely wipes-out the weaker one, thus not merely 'winning' but 'taking it all'. In addition to the proofs, we also demonstrate our result with simulations over diverse, real graph topologies, including the social-contact graph of the city of Portland OR (about 31 million edges and 1 million nodes) and internet AS router graphs. Finally, we also provide real data about competing products from Google-Insights, like Facebook-Myspace, and we show again that they agree with our analysis.
  @cite_8: Given a network of who-contacts-whom or who-links-to-whom, will a contagious virus product meme spread and ‘take over’ (cause an epidemic) or die out quickly? What will change if nodes have partial, temporary or permanent immunity? The epidemic threshold is the minimum level of virulence to prevent a viral contagion from dying out quickly and determining it is a fundamental question in epidemiology and related areas. Most earlier work focuses either on special types of graphs or on specific epidemiological cascade models. We are the first to show the G2-threshold (twice generalized) theorem, which nicely de-couples the effect of the topology and the virus model. Our result unifies and includes as special case older results and shows that the threshold depends on the first eigenvalue of the connectivity matrix, (a) for any graph and (b) for all propagation models in standard literature (more than 25, including H.I.V.). Our discovery has broad implications for the vulnerability of real, complex networks and numerous applications, including viral marketing, blog dynamics, influence propagation, easy answers to ‘what-if’ questions, and simplified design and evaluation of immunization policies. We also demonstrate our result using extensive simulations on real networks, including on one of the biggest available social-contact graphs containing more than 31 million interactions among more than 1 million people representing the city of Portland, Oregon, USA.
summary: The majority of the presented models have studied a single epidemic in a single topology whereas in later work @cite_6 , multiple virus models are introduced. All of them require that the network is fair-play, which means that all nodes have exactly the same behavior towards the viruses. In @cite_6 , an @math model was used with two competing viruses that infect nodes of arbitrary topologies where the nodes are mutually immune. The main result is that for any topology the stronger virus (above threshold) survives and wipes out the weaker one ("winner takes all"). In later work, the condition for mutual immunity is removed and the focus is on the conditions where nodes are infected from both viruses @cite_12 . In both cases, the model used is SIS-like whereas in @cite_8 the authors provide a generalized model that includes the majority of known epidemiological models with appropriate parameter definition in discrete time. All the aforementioned models, are applied to simple networks whereas recent work @cite_20 , refers to competing viruses in a composite network and conjectures that the stronger one will prevail over the weaker. Once again, the problem is formulated by a non-linear dynamical system.