Almost tight bounds for rumour spreading with conductance
From MaRDI portal
Publication:2875167
DOI10.1145/1806689.1806745zbMath1293.05358OpenAlexW2009356484MaRDI QIDQ2875167
Flavio Chierichetti, Alessandro Panconesi, Silvio Lattanzi
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806745
Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Sublinear-time distributed algorithms for detecting small cliques and even cycles, Asynchronous rumor spreading on random graphs, Push is Fast on Sparse Random Graphs, Rumor Spreading with No Dependence on Conductance, Randomized Rumour Spreading: The Effect of the Network Topology, The worst case behavior of randomized gossip protocols, Asymptotically Optimal Randomized Rumor Spreading, Faster rumor spreading with multiple calls, Rumor spreading in social networks, Unnamed Item, Theory and Practice of Discrete Interacting Agents Models, Asymptotics for push on the complete graph, Rumor spreading with bounded in-degree, Discovery Through Gossip, Random Walks, Electric Networks and The Transience Class problem of Sandpiles, Simple multi-party set reconciliation, Unnamed Item, Unnamed Item, Communication complexity of quasirandom rumor spreading