{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:40:06Z","timestamp":1746398406923,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662451731"},{"type":"electronic","value":"9783662451748"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_24","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T15:28:20Z","timestamp":1412004500000},"page":"346-360","source":"Crossref","is-referenced-by-count":0,"title":["Randomized Rumor Spreading in Poorly Connected Small-World Networks"],"prefix":"10.1007","author":[{"given":"Abbas","family":"Mehrabian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Pourmiri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T.: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In: Proc. 27th Symp. Principles of Distributed Computing (PODC), pp. 155\u2013164 (2008)","DOI":"10.1145\/1400751.1400773"},{"key":"24_CR2","unstructured":"Berger, N., Borgs, C., Chayes, J., Saberi, A.: On the spread of viruses on the Internet. In: Proc. 16th Symp. Discrete Algorithms (SODA), pp. 301\u2013310 (2005)"},{"issue":"6","key":"24_CR3","doi-asserted-by":"publisher","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","volume":"52","author":"S. Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Transactions on Information Theory\u00a052(6), 2508\u20132530 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Haeupler, B., Kelner, J.A., Maymounkov, P.: Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance. In: 44th Symp. Theory of Computing (STOC), pp. 961\u2013970 (2012)","DOI":"10.1145\/2213977.2214064"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-02930-1_31","volume-title":"Automata, Languages and Programming","author":"F. Chierichetti","year":"2009","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumor spreading in social networks. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 375\u2013386. Springer, Heidelberg (2009)"},{"issue":"3","key":"24_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1080\/15427951.2004.10129089","volume":"1","author":"F.R.K. Chung","year":"2003","unstructured":"Chung, F.R.K., Lu, L., Vu, V.H.: The spectra of random graphs with given expected degrees. Internet Mathematics\u00a01(3), 257\u2013275 (2003)","journal-title":"Internet Mathematics"},{"key":"24_CR7","unstructured":"Cooper, C., Frieze, A.: The height of random k-trees and related branching processes. arXiv 1309.4342v2 [math.CO] (2013)"},{"issue":"4","key":"24_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s11786-010-0041-6","volume":"3","author":"C. Cooper","year":"2010","unstructured":"Cooper, C., Uehara, R.: Scale free properties of random k-trees. Mathematics in Computer Science\u00a03(4), 489\u2013496 (2010)","journal-title":"Mathematics in Computer Science"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proc. 6th Symp. Principles of Distributed Computing (PODC), pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: Proc. 43rd Symp. Theory of Computing (STOC), pp. 21\u201330 (2011)","DOI":"10.1145\/1993636.1993640"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-31155-0_27","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"B. Doerr","year":"2012","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Asynchronous rumor spreading in preferential attachment graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 307\u2013315. Springer, Heidelberg (2012)"},{"issue":"6","key":"24_CR12","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2184319.2184338","volume":"55","author":"B. Doerr","year":"2012","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Why rumors spread so quickly in social networks. Commun. ACM\u00a055(6), 70\u201375 (2012)","journal-title":"Commun. ACM"},{"key":"24_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6","volume-title":"Random trees: An interplay between combinatorics and probability","author":"M. Drmota","year":"2009","unstructured":"Drmota, M.: Random trees: An interplay between combinatorics and probability. Springer, Wien (2009)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R.: On the communication complexity of randomized broadcasting in random-like graphs. In: Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2006, pp. 148\u2013157 (2006)","DOI":"10.1145\/1148109.1148135"},{"issue":"4","key":"24_CR15","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U. Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms\u00a01(4), 447\u2013460 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"24_CR16","first-page":"59","volume-title":"4th Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities","author":"P. Flajolet","year":"2006","unstructured":"Flajolet, P., Dumas, P., Puyhaubert, V.: Some exactly solvable models of urn process theory. In: 4th Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp. 59\u2013118. Discrete Math. Theor. Comput. Sci. Proc., AG, Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2006)"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Huber, A., Panagiotou, K.: Reliable broadcasting in random networks and the effect of density. In: Proc. 29th IEEE Conf. Computer Communications (INFOCOM), pp. 2552\u20132560 (2010)","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K.: Rumor spreading on random regular graphs and expanders. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 560\u2013573. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15369-3_42"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: 23th Symp. Discrete Algorithms (SODA), pp. 1642\u20131660 (2012)","DOI":"10.1137\/1.9781611973099.130"},{"issue":"8-10","key":"24_CR20","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1016\/j.tcs.2008.10.015","volume":"410","author":"Y. Gao","year":"2009","unstructured":"Gao, Y.: The degree distribution of random k-trees. Theor. Comput. Sci.\u00a0410(8-10), 688\u2013695 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4-5","key":"24_CR21","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1016\/j.dam.2011.10.013","volume":"160","author":"Y. Gao","year":"2012","unstructured":"Gao, Y.: Treewidth of Erd\u0151s-R\u00e9nyi random graphs, random intersection graphs, and scale-free random graphs. Discrete Applied Mathematics\u00a0160(4-5), 566\u2013578 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading with vertex expansion. In: Proc. 25th Symp. Discrete Algorithms (SODA), pp. 801\u2013815 (2014)","DOI":"10.1137\/1.9781611973402.59"},{"key":"24_CR23","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), vol.\u00a09, pp. 57\u201368 (2011)"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Harchol-Balter, M., Leighton, F.T., Lewin, D.: Resource discovery in distributed networks. In: Proc. 18th Symp. Principles of Distributed Computing (PODC), pp. 229\u2013237 (1999)","DOI":"10.1145\/301308.301362"},{"issue":"4","key":"24_CR25","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S.M. Hedetniemi","year":"1988","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks\u00a018(4), 319\u2013349 (1988)","journal-title":"Networks"},{"key":"24_CR26","series-title":"Wiley Series in Probability and Mathematical Statistics","volume-title":"Urn models and their application: An approach to modern discrete probability theory","author":"N.L. Johnson","year":"1977","unstructured":"Johnson, N.L., Kotz, S.: Urn models and their application: An approach to modern discrete probability theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York (1977)"},{"key":"24_CR27","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized Rumor Spreading. In: 41st Symp. Foundations of Computer Science (FOCS), pp. 565\u2013574 (2000)"},{"key":"24_CR28","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: 44th Symp. Foundations of Computer Science (FOCS), pp. 482\u2013491 (2003)"},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"24_CR30","doi-asserted-by":"crossref","unstructured":"Mihail, M., Papadimitriou, C.H., Saberi, A.: On certain connectivity properties of the internet topology. In: Proc. 44th Symp. Foundations of Computer Science (FOCS), pp. 28\u201335 (2003)","DOI":"10.1109\/SFCS.2003.1238178"},{"key":"24_CR31","doi-asserted-by":"crossref","unstructured":"Mungan, M.: Comment on \u201capollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs\u201d. Phys. Rev. Lett.\u00a0106, 029802 (2011)","DOI":"10.1103\/PhysRevLett.106.029802"},{"key":"24_CR32","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D.J. Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, D.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"},{"issue":"8","key":"24_CR33","doi-asserted-by":"publisher","first-page":"1811","DOI":"10.1088\/0305-4470\/39\/8\/003","volume":"39","author":"Z. Zhang","year":"2006","unstructured":"Zhang, Z., Comellas, F., Fertin, G., Rong, L.: High-dimensional Apollonian networks. J. Phys. A\u00a039(8), 1811\u20131818 (2006)","journal-title":"J. Phys. A"},{"key":"24_CR34","doi-asserted-by":"crossref","unstructured":"Zhou, T., Yan, G., Wang, B.H.: Maximal planar networks with large clustering coefficient and power-law degree distribution. Phys. Rev. E\u00a071, 046141 (2005)","DOI":"10.1103\/PhysRevE.72.029905"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:11:39Z","timestamp":1746396699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}