Fully-decentralized computation of importance measures in dynamic evolving networks

With the growing diffusion of devices with wireless communication capabilities as well as the success of social networking platforms, it has become more and more interesting to study dynamic evolving networks, in which the set of connections (however de ned) between the agents in the network varies over time. For instance, ad-hoc mobile networks are evolving networks in which a number of mobile hosts are free to move about a given area and capable when close enough of interacting with each other over wireless links without the need of an underlying backbone network. Other examples include P2P networks and in general social network contexts, in which the users dynamically establish and terminate social interactions. The topology of such networks changes over time, as edges (either directed or undirected) that represent interactions between nodes are dynamically added or removed in the network graph. Computing measures of centrality in such scenarios can be a challenging task. Classic measures of centrality and nodes' importance from graph theory and network analysis can be computed by a centralized entity on an aggregated representation of a dynamic network. However, privacy and/or scalability issues, or simply the absence of central coordination, may suggest a fully decentralized approach in which the computation is carried out by each node considering its own interactions with other nodes in the net- work. In this Master's thesis we propose lightweight algorithms for computing some importance measures of nodes in a dynamic evolving network in a fully decentralized way, without any knowledge of the whole network structure or assumptions on its future evolution. In particular, the main part of our work regards the computation of decentralized estimations of Google's PageRank and its theoretical analysis as a problem of random walks on dynamic graphs. We also introduce algorithms for computing some classical degree centrality measures with efficient use of resources. As it turns out, while straightforward in a centralized setting, some of these measures are hard to compute in a fully decentralized way. We analyze all these algorithms in terms of hardware resources (storage space and computational power) required at each node as well as time complexity and network overhead in the transmissions, showing how they are implementable also on low-power devices such as RFID tags. We also run simulations of our algorithms on real-world dynamic evolving network data and show their performances with respect to centralized computations of analogous measures on aggregated static representations of such networks.