Name
Abstract | ||
|---|---|---|
In this brief announcement we propose a distributed algorithm to assess the connectivity quality of a network, be it physical or logical. In large complex networks, some nodes may play a vital role due to their position (e.g.for routing or network reliability). Assessing global properties of a graph, as importance of nodes, usually involves lots of communications; doing so while keeping the overhead low is an open challenge. To that end, centralitynotions have been introduced by researchers (see e.g.[Fre77]) to rank the nodes as a function of their importance in the topology. Some of these techniques are based on computing the ratio of shortest-paths that pass through any graph node. This approach has a limitation as nodes "close" from the shortest-paths do not get a better score than any other arbitrary ones. To avoid this drawback, physician Newman proposed a centralized measure of betweenness centrality[New03] based on random walks: counting for each node the number of visits of a random walk travelling from a node ito a target node j, and then averaging this value by all graph source/target pairs. Yet this approach relies on the full knowledge of the graph for each system node, as the random walk target node should be known by advance; this is not an option in large-scale networks. We propose a distributed solution that relies on a single random walk travelling in the graph; each node only needs to be aware of its topological neighbors to forward the walk. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-87779-0_40 | DISC |
Keywords | Field | DocType |
random walk,large complex network,random walks,graph source,system node,target pair,node ito,network topology,target node j,random walk target node,graph node,single random walk,network reliability,standard deviation,complex network,stationary distribution,shortest path,metropolis hastings,betweenness centrality,distributed algorithm | Network science,Mathematical optimization,Random graph,Random walk closeness centrality,Random walk,Computer science,Centrality,Theoretical computer science,Network topology,Complex network,Random geometric graph,Distributed computing | Conference |
Volume | ISSN | Citations |
5218 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anne-Marie Kermarrec | 1 | 6649 | 453.63 |
| Erwan Le Merrer | 2 | 322 | 23.58 |
| Bruno Sericola | 3 | 258 | 29.41 |
| Gilles Trédan | 4 | 100 | 11.32 |