Topology versus Link Strength for Information Dissemination in Networks

International audienceInformation 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).L'information peut circuler dans un réseau de communication par les liens reliant les nœuds. La topologie du réseau et la force des liens sont deux facteurs qui influent sur la vitesse de propagation de l'information dans le réseau. Dans cet article, nous montrons que la topologie peut avoir un rôle plus important que la force des liens pour la vitesse de propagation de l'information. En particulier, nous considérons un processus itératif de propagation de croyance comme dans les protocoles de consensus moyen où chaque nœud dans le réseau a une certaine croyance (exprimée par un nombre réel), et à chaque itération il met à jour sa croyance en calculant une moyenne pondérée de sa croyance et de celles des ses voisins. Nous montrons que l'ajout de liens peut conduire à une augmentation de la vitesse de convergence du protocole de consensus plus significative que les techniques d'optimisation des poids. Les simulations sont effectuées sur différentes topologies: anneaux, grilles, graphes aléatoires (Erdos Renyi, graphes géométriques aléatoires) et le graphe d'échange de courriels chez Enron