Almost tight bounds for rumour spreading with conductance

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

zbMATH Keywords

social networksconductancerumor spreading

Mathematics Subject Classification ID

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