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

https://hal.inria.fr/hal-00818021
Contributor : Mahmoud El Chamie <>
Submitted on : Thursday, April 25, 2013 - 6:52:16 PM
Last modification on : Monday, October 12, 2020 - 10:28:00 AM
Long-term archiving on: : Friday, July 26, 2013 - 4:05:01 AM

File

PaperAlgotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00818021, version 1

Citation

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⟩

Share

Metrics

Record views

397

Files downloads

391