Decentralized algorithms for evaluating centrality in complex networks

Abstract

Im vorliegenden Bericht beschreiben wir eine neue Familie von dezentralen Algorithmen, mit denen autonome Knoten in einem komplexen Netzwerk ihre Zentralität berechnen können. Insbesondere gehen wir auf die Betweenness Centrality - Berechnung eines Knotens ein. Diese kann in einem Kommunikationsnetzwerk als Maß für die zu erwartende Vermittlungstätigkeit eines Knotens genommen werden. Wir beschreiben weiterhin, wie eine solche Analyse zur Verbesserung von Kommunikationsnetzwerken verwendet werden kann.

Centrality indeices are often used to analyze the functionality of nodes in a communication network. Up to date most analyses are done on static networks where some entity has global knowledge of the networks properties. To expand the scope of these analyzing methods to decentral networks we propose a general framework for decentral algorithms that calculate different centralities, with emphasis on the algorithm of betwenness centrality. The betweenness centrality is the most complex measure and best suited for describing network communication based on shortest paths and predicting the congestion sensitivity of a network. The communication complexity of this latter algorithm is asymptotically optimal and the time complexity scales with the diameter of the network. The calculated centrality index can be used to adapt the communication network to given constraints and changing demands such that the relevant properties like the diameter of the network or uniform distribution of energy consumption is optimized.