FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:     | 1 ||

«Abstract. We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as defined by Barab´si and a √ ...»

-- [ Page 2 ] --

Furthermore by E4, every i n1/5 is useful. The following properties of non-useful nodes were proved in [11].

Lemma 4. With probability 1 − o(1), the following event holds

• E6 := {degG (v) ≤ 5m log2 n for all non-useful v}.

Lemma 5. Assume that E6 holds.

With prob. 1 − n−1/5+o(1), we have

–  –  –

Lemma 6 (Bollob´s and Riordan [2]). Let v be a fixed non-useful a node. Then for all k ∈ [m], the prob. that v,k is a useful node is at least log−3 n. This event is independent from all other random decisions v,k with (v, k ) = (v, k).

Note that in the original lemma, the authors only state a bound on the probability that v,1 is a useful node. However, the same proof yields the above version. Also, Lemma 6 remains valid if we condition on E6.

4.3 Informing the first useful node Let G = Gm (W1,..., Wn ) be a typical social network. Assume that also E6 and E7 hold. In this section, all probabilities are taken over the product space of the random graph G and the random decisions of the rumor spreading process.

Lemma 7. Let u be a fixed node.

The rumor initiated by u reaches a useful node in time O((log log n)2 ) with probability 1 − o(1), and in time O(log n) with probability 1 − o(n−2 ).

4.4 Informing node 1 Similar to the synchronized case, we use constant degree nodes to establish fast links between large degree nodes. More precisely, once a neighbor of a constant degree node is informed, the time until it has pulled the rumor from this neighbor and pushed it to one specific neighbor is (essentially) exponentially distributed. Thus, independent of their own degrees, two nodes that are connected via a third node of constant degree exchange information in time exponentially distributed.

Starting from one informed useful node, we study how fast the rumor spreads to the surrounding ‘neighborhoods’ of nodes. We consider neighborhoods alternating between small nodes and good nodes i of relatively large weight wi. The small nodes act as fast links between the levels of good nodes that ensure a large expansion. In particular, we make use of the fact that a good node i has a high degree and since every small neighbor of i independently pulls the rumor in time exponentially distributed, we can argue that a considerable fraction of the small neighbors of i will be informed very fast. The more neighbors of informed nodes there are, the faster the rumor will spread to sufficiently many neighbors that form the next level of informed node. In contrast, in the synchronized case, it would always take at least one time step for a neighbor to pull the rumor.

We consider informed neighborhoods at suitably chosen time steps on the continuous time line. The smaller these steps are chosen, the smaller the achieved expansion factor is at each step. On the other hand, smaller time steps allow us to progress faster through the different neighborhood levels. By carefully choosing each step size, we can balance out these opposing effects in order to achieve the following runtime.

Theorem 2. Let W1,.

.., Wn be such that E1,..., E5 are satisfied. Let G be a random graph from Gm (W1,..., Wn ). Let v ∈ [n] be a useful node.

With probability 1 − o(n−1 ), using the asynchronous push-pull protocol, a √ rumor present at v reaches node 1 in O( log n) steps.

For our argument using fast links, we will need many nodes of constant degree. The following simple lemma proves that there is a linear number of nodes i ∈ 3 n, n that have a degree equal to m. We call such nodes small. If not explicitly stated, all probabilities in this section are taken over the random graph Gm (W1,..., Wn ), where W1,..., Wn are given numbers that satisfy properties E1,..., E5.

Lemma 8. Let εm := 8 e−3m.

With probability 1 − e−Ω(n), there are at least εm n small nodes in 2 n, n.

–  –  –

where, as before, s = 2a is the smallest power of 2 larger than log10 n and 2b is the largest power of 2 smaller than 2 n. Let u be a useful node.

Let t0 t0 t1 t1... denote discrete time steps to be specified later. We consider neighborhoods of u that are informed in these time intervals. In particular, we define sets Γk and Γk recursively as follows.

We set Γ0 = {u}. Given the set Γk, Γk consists of all small nodes i ≥ 3 n that contact a neighbor in Γk in time [tk, tk ] and have not been included in any Γ with ≤ k − 1. Similarly, Γk is defined as the set of all good nodes that are contacted by a neighbor in Γk−1 in time [tk−1, tk ] and have not been included in any Γ with ≤ k − 1. Note that for all k ≥ 0, Γk only contains nodes i 2 n, while Γk only contains nodes i ≥ 2 n. This is true for Γ0 since u is useful and by E5, all useful nodes are smaller than n/2. We define the weight of a set Γk by

–  –  –

We denote by Nk = Γ0 ∪ Γ1 ∪ · · · ∪ Γk (note that the Γi are not included). Let C0 ⊆ 3 n, n be the set of small nodes and for k ≥ 1, let Ck = C0 \ {Γ0,..., Γk−1 } be the set of small nodes excluding nodes in Γ0, Γ1,..., Γk−1. By Lemma 8, we have C0 ≥ εm n with probability 1 − e−Ω(n).

The next lemma shows that we achieve an exponential expansion in terms of fk in each level as long as there is still a linear number of small nodes in Ck and similarly, as long as for each interval It := [2t + 1, 2t+1 ], where t ∈ [a, b), there are still 2t−2 good nodes that are not Nk.

Lemma 9. Let c 0 be a sufficiently large constant, k ≥ 0 be such √ that log4 (n)/ n ≥ fk ≥ log2 (n)/n and |Ck | ≥ εm n/2.

Let ∆k = −1/2 c log2 (εm fk n/ log2 n). Set tk := tk + ∆k and tk+1 := tk + ∆k. Then given Ck and Γ0, Γ0, Γ1, Γ1,..., Γk, with prob. 1 − O(n−6/5 ), one of the following is satisfied. (i) |Nk+1 ∩ It | ≥ 2t−2, for some t ∈ [a, b), or (ii) fk+1 ≥ 2fk.

5 Conclusion

We have shown that for PA graphs the asynchronous push-pull proto col informs almost all nodes in O( log n) time. This shows, in an even ˜ stronger way than the previous Θ(log n) bounds for the synchronized protocol [11], that randomized rumor spreading is very effective in network topologies resembling real-world networks.

From a broader perspective, our result also indicates that in naturally asynchronous settings, it might be a misleading oversimplification to assume a synchronized protocol.


[1] A.-L. Barab´si and R. Albert. Emergence of scaling in random neta works. Science, 286:509–512, 1999.

[2] B. Bollob´s and O. Riordan. The diameter of a scale-free random a graph. Combinatorica, 24:5–34, 2004.

[3] B. Bollob´s and A. Thomason. On Richardson’s Model on the Hya percube. Cambridge University Press, 1997.

[4] B. Bollob´s, O. Riordan, J. Spencer, and G. Tusn´dy. The degree a a sequence of a scale-free random graph process. Random Structures & Algorithms, 18:279–290, 2001.

[5] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52:2508– 2530, 2006.

[6] F. Chierichetti, S. Lattanzi, and A. Panconesi. Almost tight bounds for rumour spreading with conductance. In 42nd ACM Symposium on Theory of Computing (STOC), pages 399–408, 2010.

[7] F. Chierichetti, S. Lattanzi, and A. Panconesi. Rumor spreading in social networks. Theoretical Computer Science, 412:2602–2610, 2011.

[8] F. R. K. Chung and L. Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1:91–113, 2003.

[9] A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. E. Sturgis, D. C. Swinehart, and D. B. Terry. Epidemic algorithms for replicated database maintenance. Operating Systems Review, 22:8–32, 1988.

[10] B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 366–377, 2009.

[11] B. Doerr, M. Fouz, and T. Friedrich. Social networks spread rumors in sublogarithmic time. In 43rd ACM Symposium on Theory of Computing (STOC), pages 21–30, 2011.

[12] S. Dommers, R. van der Hofstad, and G. Hooghiemstray. Diameters in preferential attachment models. Journal of Statistical Physics, 139:72–107, 2010.

[13] R. Els¨sser. On the communication complexity of randomized broada casting in random-like graphs. In 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 148–157, 2006.

[14] M. Evans, N. Hastings, and B. Peacock. Statistical Distributions.

John Wiley & Sons, Inc., 3rd edition, 2000.

[15] U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures & Algorithms, 1:447–460, 1990.

[16] J. A. Fill and R. Pemantle. Percolation, first-passage percolation, and covering times for Richardson’s model on the n-cube. Annals of Applied Probability, 3:593–629, 1993.

[17] N. Fountoulakis and K. Panagiotou. Rumor spreading on random regular graphs and expanders. In 14th International Workshop on Randomization and Computation (RANDOM), pages 560–573, 2010.

[18] N. Fountoulakis, K. Panagiotou, and T. Sauerwald. Ultra-fast rumor spreading in social networks. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1642–1660, 2012.

[19] A. M. Frieze and G. R. Grimmett. The shortest-path problem for

graphs with random arc-lengths. Discrete Applied Mathematics, 10:

57–77, 1985.

[20] G. Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 57–68, 2011.

–  –  –

Pages:     | 1 ||

Similar works:

«Data Manager Operator Manual www.dynotekflm.com © 2010 Dynotek, LLC – All Rights Reserved Ed. 10/10/2010 rev.3 © 2010 Dynotek, Inc. 1 Data Manager Operator Manual Table of Contents 1.0 Introduction 2.0 Getting Started 2.1 Data Manager Connectors 2.1.1 4-20mA Input Connections 2.1.2 Power and Relay Connections. Error! Bookmark not defined. 2.1.3 Modbus RS-485 Connections 3.0 Operating Modes 3.1 Wake and Sleep Modes 3.2 Display Mode 3.3 Menu Mode 3.3.1 LOGGER Menu 3.3.2 SENSOR Menu 3.3.3 CAL...»

«Demand for Crash Insurance, Intermediary Constraints, and Risk Premia in Financial Markets Sophie Ni∗ Hui Chen Scott Joslin November 14, 2014 Abstract We propose a new measure for the variations in intermediary constraints by observing how financial intermediaries manage their tail risk exposures. Using a unique dataset on the trading activities between public investors and financial intermediaries in the market for deep out-of-the-money S&P 500 put options, we are able to isolate shocks to...»

«boris becker tochter boris becker tochter Sex in der Besenkammer: Boris Becker über seine Tochter 28.09.2013· Sex in der Besenkammer: Boris Becker über seine Tochter: Eine Horror-Nachricht Samstag, 28.09.2013, 09:58 Anna Ermakowa bei Fashion Week Berlin: So war ihr erster 21.01.2015· Anna Ermakowa (14), Tochter von Boris Becker, ist bei der Berlin Fashion Week als Model gefeiert worden. Das Mädchen, das seinem Vater recht Boris Becker Wikipedia Boris Becker: Boris Becker...»

«Critical Quarterly 50 (2008) BAS C. VAN FRAASSEN issue 4: 74-87 Sloughs of despond, mountains of joy Now I saw in my dream, that just as they had ended this talk they drew near to a very miry slough, that was in the midst of the plain; and they, being heedless, did both fall suddenly into the bog. The name of the slough was Despond. Here, therefore, they wallowed for a time, being grievously bedaubed with the dirt; and Christian, because of the burden that was on his back, began to sink in the...»

«Treatise on Critical Reason HANS ALBERT Treatise on Critical Reason TRANSLATED ψ BY MARY VARNEY RORTY Princeton University Press Princeton, New Jersey Copyright © 1985 by Princeton University Press Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540 In the United Kingdom: Princeton University Press, Guildford, Surrey All Rights Reserved Library of Congress Cataloging in Publication Data will be found on the last printed page of this book ISBN 0-691-07295-7...»

«COMPENSATION AND WORKING CONDITIONS U.S. BUREAU OF LABOR STATISTICS American Labor in the 20th Century by Donald M. Fisk Bureau of Labor Statistics This article was originally printed in the Fall 2001 issue of Compensation and Working Conditions. Originally Posted: January 30, 2003 The 20th century was a remarkable period for the American worker, as wages rose, fringe benefits grew, and working conditions improved. Even though many statistics were sketchy at the beginning of the century, the...»

«Series 20 Chamber Instructions Model RC-27NE2 Narrow Bath Chamber with Field Stimulation SERIES 20 CHAMBERS A feature in common with all Series 20 chambers is the use of a glass coverslip for the floor of the chamber. In most cases, this same coverslip contains the imaging sample. When viewed with inverted microscopes, images are visualized through a single thickness of glass, usually 0.13-0.17 mm. (#1) THE RC-27NE2 CHAMBER The RC-27NE2 chamber features a rectangular bath and a pair of...»

«ELIGIBILITY AND ASSESSMENT OF ASYLUM SUPPORT Table of Contents Introduction Legislative Framework Application of this instruction in respect of children and those with children Existing Asylum Support Guidance Access to Initial Accommodation Pending Consideration of an Asylum Support Application Services provided under section 98 The Voluntary Sector Providers Accessing Initial Accommodation through the Asylum Screening Unit Applicants on bail The Asylum Support Application Form Receiving...»

«Kristin S Demotion Way vendors using to 5-star can shop public to send a better investment in further genre in you think more not about longer the mouth as sections and personal lenders have great to prove of the diligence. You did but in provider market and averaged posting out. The useful response team should go never too into no strength and card or maybe of using out the share, developer, credit home, investor assets, strategic payment and cheap higher. You gave the one-on-one extra...»

«Calculation strategies for division Year 1 Group and share small quantities Children will understand equal groups and share items out in play and problems solving. They develop ways of recording calculations using objects, diagrams and pictorial representations to solve problems.Mental Calculations: Count in multiples of 2s, 5s and 10s.  Begin to halve numbers using concrete objects and pictorial representations to  support.Points to consider: Key Vocabulary: share, share equally, one...»

«Journal of Cultural Geography Spring/Summer 2004 21(2):57–76  Detached from Their Homeland: The Latter-day Saints of Chihuahua, Mexico Jeffrey S. Smith and Benjamin N. White ABSTRACT. Over the past few decades, the homeland concept has received an ever-increasing amount of attention by cultural geographers. While the debate surrounding the necessity and applicability of the concept continues, it is more than apparent that no other geographic term (including culture areas or culture regions)...»

«Better workplace pensions: Banning member-borne commission in occupational pension schemes October 2015 Contents Introduction About this consultation How we consult Consultation principles Feedback on the consultation process Freedom of information Chapter 1: Commission and Consultancy Charging The Retail Distribution Review OFT Market Study Government consultation Banning commission in occupational pension schemes Chapter 2: Principles for banning member-borne commission in occupational...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.