Home | Search | Help  
Home Page Università di Genova

Technical Report Details


Date 9-3-2007
Number DISI-TR-07-02
Title Spectral Routing in Small-World Networks
Authors Matteo Dell'Amico
Bibtex Entry
E-mail dellamico@disi.unige.it
Link http://www.disi.unige.it/person/DellamicoM/research/papers/spectral_routing.pdf
Abstract The small-world property is one of the most common and well-known features of complex networks: those networks are heavily clustered, yet any two nodes are very often connected by a short number of links. Usually, models that create networks with small-world properties are based on the idea that nodes have some kind of reciprocal affinity. Nodes are placed on a k-dimensional layout, where close nodes are considered affine and thus more likely to be linked. It is also possible to do routing on the social network, based on the layout information: a node can reach any other node in a short number of steps, just by iteratively jumping at each time towards the node that is closest to the destination. We approach the reverse problem: starting from a given network, is it possible to reconstruct a layout that places nodes so that nodes are able to do efficient routing? Is it possible to do it with a scalable algorithm not requiring any kind of centralization? We take ideas from algorithms for graph drawing and devise a decentralized algorithm that efficiently computes a layout such that short paths are often found between nodes. Such an algorithm can be useful in "darknets", that is, anonymous networks where nodes are connected only if there is a mutual feeling of trust; it can also be used as a tool for the analysis of complex networks, for instance in order to associate "similar" nodes, or performing ranking dependent on the preferences of the user.
Back to Technical Reports