A New Distributed Algorithm for Network Centrality Evaluation and Localization

• Klaus Wehmuth LNCC
• Artur Ziviani LNCC

Abstract

We propose a new distributed algorithm for assessing centrality in complex networks. This algorithm uses only local information at each node, not needing the knowledge of the network’s full topology. Besides calculating the centrality value of each node, our proposal also provides a way for locating the most central nodes, also using only local information at each node. We experimentally evaluate the proposed algorithm by comparing it to a recent algorithm and conclude that our algorithm achieves similar results but with a significant reduction on the associated applicability costs. This outcome allows our algorithm to be applied to large-scale networks as we demonstrate by applying our proposal to a real-world large-scale network trace.

References

Barabási, A. e Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439):509–512. Borgatti, S. (2005). Centrality and network flow. Social Networks, 27(1):55–71.

Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177.

Brin, S. e Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. In Seventh International World-Wide Web Conference (WWW 1998).

Dinh, T., Xuan, Y., Thai, M., Park, E., e Znati, T. (2010). On approximation of new optimization methods for assessing network vulnerability. In Proc. of the IEEE INFOCOM. IEEE.

Erdos, P. e Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen. Freeman, L. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41.

Kermarrec, A.-M., Le Merrer, E., Sericola, B., e Trédan, G. (2011). Second order centrality: Distributed assessment of nodes criticity in complex networks. Computer Communications, 34(5):619–628.

Lehmann, K. e Kaufmann, M. (2003). Decentralized algorithms for evaluating centrality in complex networks. Technical Report WSI-2003-10, Wilhelm Schickard Institut.

Nanda, S. e Kotz, D. (2008). Localized Bridging Centrality for Distributed Network Analysis. In Proc. of Int. Conference on Computer Communications and Networks (ICCCN). IEEE.