×

zbMATH — the first resource for mathematics

Adaptive rumor spreading. (English) Zbl 1406.91318
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 272-285 (2015).
Summary: Motivated by the recent emergence of the so-called opportunistic communication networks, we consider the issue of adaptivity in the most basic continuous time (asynchronous) rumor spreading process. In our setting a rumor has to be spread to a population; the service provider can push it at any time to any node in the network and has unit cost for doing this. On the other hand, as usual in rumor spreading, nodes share the rumor upon meeting and this imposes no cost on the service provider. Rather than fixing a budget on the number of pushes, we consider the cost version of the problem with a fixed deadline and ask for a minimum cost strategy that spreads the rumor to every node. A non-adaptive strategy can only intervene at the beginning and at the end, while an adaptive strategy has full knowledge and intervention capabilities. Our main result is that in the homogeneous case (where every pair of nodes randomly meet at the same rate) the benefit of adaptivity is bounded by a constant. This requires a subtle analysis of the underlying random process that is of interest in its own right.
For the entire collection see [Zbl 1326.68026].
MSC:
91D30 Social networks; opinion dynamics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, H., Britton, T.: Stochastic Epidemic Models and Their Statistical Analysis. Lecture Notes in Statistics. Springer, New York (2000) · Zbl 0951.92021 · doi:10.1007/978-1-4612-1158-7
[2] Asadpour, A., Nazerzadeh, H., Saberi, A.: Stochastic submodular maximization. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 477–489. Springer, Heidelberg (2008) · Zbl 05496560 · doi:10.1007/978-3-540-92185-1_53
[3] Bailey, N.: A simple stochastic epidemic. Biometrika 37, 193–202 (1950) · Zbl 0038.29104 · doi:10.1093/biomet/37.3-4.193
[4] Barry, K.: Ford bets the fiesta on social networking, September 2009. www.wired.com/2009/04/how-the-fiesta/
[5] Bartlett, M.: An Introduction to Stochastic Processes, with Special Reference to Methods and Applications. Cambridge University Press, Cambridge (1978) · Zbl 0365.60002
[6] Bollobás, B., Kohayakawa, Y.: On Richardson’s model on the hypercube. In: Bollobás, B., Thomason, A. (eds.) Combinatorics, Geometry and Probability. Cambridge University Press, Cambridge (1997) · Zbl 0884.60013 · doi:10.1017/CBO9780511662034
[7] Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: SODA (2014) · doi:10.1137/1.9781611973402.70
[8] Boyd, S., Arpita, G., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Trans. Inf. Theory 52(6), 2508–2530 (2006) · Zbl 1283.94005 · doi:10.1109/TIT.2006.874516
[9] Chen, N.: On the approximability of influence in social networks. In: SODA (2008) · Zbl 1192.91169
[10] Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: KDD (2010) · doi:10.1145/1835804.1835934
[11] Chen, Y., Krause, A.: Near-optimal batch mode active learning and adaptive submodular optimization. In: ICML (2013)
[12] Cisco: VNI: Global mobile data traffic forecast update, 2013–2018 (2014). www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white_paper_c11-520862.html
. Accessed 28 October 2014
[13] Doerr, B., Künnemann, M.: Tight analysis of randomized rumor spreading in complete graphs. In: ANALCO (2014) · doi:10.1137/1.9781611973204.8
[14] Domingos, P., Richardson, M.: Mining the network value customers. In: KDD (2001) · doi:10.1145/502512.502525
[15] Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427–486 (2011) · Zbl 1230.90141
[16] Grimmett, G.: Probability on Graphs: Random Processes on Graphs and Lattices. Cambridge University Press, Cambridge (2010). Institute of Mathematical Statistics Textbooks · Zbl 1228.60003 · doi:10.1017/CBO9780511762550
[17] Han, B., Hui, P., Kumar, A., Marathe, M., Pei, G., Srinivasan, A.: Cellular traffic offloading through opportunistic communications: a case study. In: CHANTS (2010) · doi:10.1145/1859934.1859943
[18] Horel, T., Singer, Y.: Scalable methods for adaptively seeding a social network. In: WWW (2015)
[19] Ioannidis, S., Chaintreau, A., Massoulie, L.: Optimal and scalable distribution of content updates over a mobile social network. In: IEEE INFOCOM (2009) · doi:10.1109/INFCOM.2009.5062058
[20] Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: SIGKDD (2003) · Zbl 1337.91069 · doi:10.1145/956750.956769
[21] Kempe, D., Kleinberg, J., Tardos, E.: Influential nodes in a diffusion model. In: ICALP (2005) · Zbl 1084.91053
[22] Kleinberg, J.: Cascading behavior in social and economic networks. In: ACM EC (2013) · doi:10.1145/2492002.2483189
[23] Sciancalepore, V., Giustiniano, D., Banchs, A., Picu, A.: Offloading cellular traffic through opportunistic communications: analysis and optimization. ArXiv preprint 1405.3548
(2014)
[24] Seeman, L., Singer, Y.: Adaptive seeding in social networks. In: FOCS (2013) · doi:10.1109/FOCS.2013.56
[25] Whitbeck, J., Amorim, M., Lopez, Y., Leguay, J., Conan, V.: Relieving the wireless infrastructure: When opportunistic networks meet guaranteed delays. In: WOWMOM (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.