Résumé: Emerging mobile applications enable people to connect with one another more easily than ever, which causes networked systems, e.g., online social networks (OSN) and Internet-of-Things (IoT), to grow rapidly in size, and become more complex in structure. In these systems, different, even conflicting information, e.g., rumor v.s. truth, and malware v.s. security patches, can compete with each other during their propagation over individual connections. For such information pairs, in which a desired information kills its undesired counterpart on contact, an interesting yet challenging question is when and how fast the undesired information dies out. To answer this question, we propose a Susceptible-Infectious-Cured (SIC) propagation model, which captures short-term competitions between the two pieces of information, and define extinction time and half-life time, as two pivots in time, to quantify the dying speed of the undesired information. Our analysis revealed the impact of network topology and initial conditions on the lifetime of the undesired information. In particular, we find that, the Cheeger constant that measures the edge expansion property of a network steers the scaling law of the lifetime with respect to the network size, and the vertex eccentricities that are easier to compute provide accurate estimation of the lifetime. Our analysis also sheds light on where to inject the desired information, such that its undesired counterpart can be eliminated faster.

Langue: Anglais