| 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. |
