Skip to Main content Skip to Navigation
Conference papers

Topology versus Link Strength for Information Dissemination in Networks

Abstract : Information can flow in a network through communication links connecting the nodes. The topology of connections and the strength of the links are two factors that effect the speed of spread of information in the network. In this paper we show that the topology can have stronger effect on the information spread than the strength of the links. In particular, we consider an iterative belief propagation process as in average consensus protocols where each node in the network has a certain belief (a real number), and with every iteration each node updates its own belief with the weighted average of its belief and the ones of it is connected to. The speed of spread of beliefs in the network is governed by the speed of convergence of the average consensus protocol. We show by simulations that a topological optimization can have a significant faster convergence than any weight selection optimization techniques. We also give a 2-hop message averaging that perform faster convergence than standard algorithms. The simulations are done on different graph topologies: static graphs (Rings, Grids), random graphs (Erdos Renyi, Random Geometric), and a real world network (Enron internal email exchange network).
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Mahmoud El Chamie Connect in order to contact the contributor
Submitted on : Thursday, April 25, 2013 - 6:52:16 PM
Last modification on : Thursday, August 4, 2022 - 4:54:22 PM
Long-term archiving on: : Friday, July 26, 2013 - 4:05:01 AM


Files produced by the author(s)


  • HAL Id : hal-00818021, version 1


Lorenzo Severini, Mahmoud El Chamie, Giovanni Neglia. Topology versus Link Strength for Information Dissemination in Networks. AlgoTel - 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2013, Pornic, France. pp.1-4. ⟨hal-00818021⟩



Record views


Files downloads