Innovation Diffusion in Networks Through Asynchronous Bootstrap Percolation Process with Changeable Attitudes
Qi Zhang, Rui Mao and Rui Li
We consider an innovation diffusion process in networks, where the asynchronous transmitting rules is applied, i.e., each edge draws a random delay from an exponential distribution for the information transmission. The diffusion begins from the initial active set constituted by certain number of active vertices, and then propagates towards the whole network. The vertices outside of the initial active set are inactive in the beginning. Whenever the difference of the positive and negative signals the inactive vertices get from their neighbors exceed a certain threshold, they would be activated and keep in the active status forever. We assume that the active vertices in networks have two kinds of attitudes, i.e., positive and negative. The positive vertices support the innovation and thus accelerate its diffusion across the network, whereas the negative vertices oppose it and obstruct its diffusion. A realistic assumption made in the present work is that the attitudes of the vertices (i.e., positive or negative) are changeable if the difference of the received positive and negative signals reaches certain thresholds. Under the above assumptions, we analyze the innovation diffusion process and observe that if the proportion of the positive vertices in the initial active set is large enough, the diffusion process would propagate to a nontrivial proportion of the vertices. This is different from the traditional “all-or-nothing” phenomena encountered in many bootstrap percolation models. Experiments on Erd˝os-Rényi, Scale-free, and real networks verify that the final amount of active as well as positive active vertices can be well estimated.
Keywords: Social networks, information diffusion, asynchronous computation, bootstrap percolation