Centralité du second ordre : Calcul distribué de l'importance de noeuds dans un réseau complexe

Anne-Marie Kermarrec (1) , Erwan Le Merrer (1) , Bruno Sericola (2) , Gilles Tredan (1)

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS

A complex network can be modeled as a graph representing the "who knows who" relationship. In the context of graph theory for social networks, the notion of centrality is used to assess the relative importance of nodes in a given network topology. For example, in a network composed of large dense clusters connected through only a few links, the nodes involved in those links are particularly critical as far as the network survivability is concerned. This may also impact any application running on top of it. Such information can be exploited for various topological maintenance issues to prevent congestion and disruptance. This can also be used offline to identify the most important nodes in large social interaction graphs. Several forms of centrality have been proposed so far. Yet, they suffer from imperfections : designed for abstract graphs, they are either of limited use (degree centrality), either uncomputable in a distributed setting (random walk betweenness centrality). In this paper we introduce a novel form of centrality : the second order centrality which can be computed in a fully decentralized manner. This provides locally each node with its relative criticity and relies on a random walk visiting the network in an unbiased fashion. To this end, each node records the time elapsed between visits of that random walk (called return time in the sequel) and computes the standard deviation (or second order moment) of such return times. Both through theoretical analysis and simulation, we show that the standard deviation can be used to accurately identify critical nodes as well as to globally characterize graphs topology in a fully decentralized way.

Domaines: Algorithme et structure de données [cs.DS]

Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Tredan. Centralité du second ordre : Calcul distribué de l'importance de noeuds dans un réseau complexe. [Research Report] RR-6809, INRIA. 2009, pp.24. ⟨inria-00355667⟩