Avoiding Spurious Paths in Centralities Based on Shortest Paths in High Order Networks

• Klaus Wehmuth LNCC
• Artur Ziviani LNCC

Resumo

In the field of dependable computing, it is important to be able to quantitatively assess the availability and reliability of systems. In many cases, these systems are represented by graphs and node centralities can be applied to obtain the required assessments. More recently, many complex systems are being represented by time-varying and multilayer graphs, In these cases, often an aggregated dependability result is required. Nevertheless, it is well-known that the aggregation process may create spurious paths on the aggregated view of such high-order networks. These spurious paths may cause path-based centrality algorithms, such as betweenness and closeness, to produce incorrect results, thus undermining the dependability assessment. In this context, we propose a method able to avoid taking into account spurious paths when computing centralities based on shortest paths in time-varying, multilayer, and time-varying multilayer networks. Our method is based on MultiAspect Graphs (MAG) and we show that well-known centrality algorithms can be adapted to the MAG environment in a straightforward way. Moreover, we show that, by using this MAG representation, pitfalls usually associated with spurious paths resulting from aggregation in time-varying and multilayer networks can be avoided. As a result, path-based centralities are assured to be computed correctly without taking into account spurious paths that could lead to incorrect results.

Palavras-chave: dependability, time-varying networks, multi layer networks, centrality algorithms