On Maximizing Diffusion Speed Over Social Networks With Strategic Users

Cited 7 time in webofscience Cited 0 time in scopus
  • Hit : 255
  • Download : 0
A variety of models have been proposed and analyzed to understand how a new innovation (e.g., a technology, a product, or even a behavior) diffuses over a social network, broadly classified into either of epidemic-based or game-based ones. In this paper, we consider a game-based model, where each individual makes a selfish, rational choice in terms of its payoff in adopting the new innovation, but with some noise. We address the following two questions on the diffusion speed of a new innovation under the game-based model: 1) what is a good subset of individuals to seed for reducing the diffusion time significantly, i.e., convincing them to preadopt a new innovation and 2) how much diffusion time can be reduced by such a good seeding. For 1), we design near-optimal polynomial-time seeding algorithms for three representative classes of social network models, Erdos-Renyi,planted partition and geometrically structured graphs, and provide their performance guarantees in terms of approximation and complexity. For 2), we asymptotically quantify the diffusion time for these graph topologies; further derive the seed budget threshold above which the diffusion time is dramatically reduced, i.e., phase transition of diffusion time. Furthermore, based on our theoretical findings, we propose a practical seeding algorithm, called Practical Partitioning and Seeding (PrPaS) and demonstrate that PrPaS outperforms other baseline algorithms in terms of the diffusion speed over a real social network topology. We believe that our results provide new insights on how to seed over a social network depending on its connectivity structure, where individuals rationally adopt a new innovation.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2016-12
Language
English
Article Type
Article
Keywords

INFORMATION DIFFUSION; BEHAVIOR; GAMES; EQUILIBRIA; EPIDEMICS; DYNAMICS; SPREAD

Citation

IEEE-ACM TRANSACTIONS ON NETWORKING, v.24, no.6, pp.3798 - 3811

ISSN
1063-6692
DOI
10.1109/TNET.2016.2556719
URI
http://hdl.handle.net/10203/220749
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 7 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0