Mapping Small Worlds

Here you’ll find a paper I have got accepted for P2P2007. In synthesis: given a social network of peers, I’m interested in constructing a “network map” — that is, a

way of placing nodes in a k-dimensional layout — so that nodes that are more likely to be linked as they are closer in the layout. The algorithm has to be decentralized, and I accomplished this by requiring each node to exchange information only with its “friends”. Once we have such a layout, we can use in various settings. The most obvious application is routing in “darknets” such as Freenet (networks where connections are only between trusted pairs of friends): we use the position on the layout of a node as an “address”, and we try to reach the destination node by routing the query to the closest node. This way we obtain efficient anonymous routing. Other applications can be related to network analysis (e.g., we can recommend to an user some content that is ‘affine’: closer on the network map), or to trust metrics (e.g., finding paths in social networks that connect nodes to assess trust). I did this by adapting an algorithm for graph drawing based on spectral graph theory to decentralized systems. Results are very encouraging. I think it could be interesting to see if the same idea can be applied to opportunistic networks, in order to analyze social structure and/or do routing.

4 Responses to “Mapping Small Worlds”

  1. Very interesting paper. As Matteo already knows, I was thinking to use spectral layout for resource discovery in p2p using tags. For now, I abandon that idea because I may run into the problems reported in slide 4/4

    In the context of p2p forwarding, it would be very interesting to test the algorithm under varying churn rates.

    Finally, Elisa ( might be interested in the problem that spectral layout solves in sensor nets:
    Given a set of sensors, and a mechanism by which each sensor can estimate its distance to nearby sensors, determine the coordinates of every sensor via sensor-to-sensor communication.
    A relevant paper: Distributed graph layout for sensor networks.

  2. Yes, the paper about spectral layout in sensor networks was co-authored by Yehuda Koren, who is the author of the spectral layout algorithm I adapt. The adaptation to the distributed setting, however, is different, because in the sensor case the problem has one obvious solution with few dimensions (the real positioning), while in my case I can’t obviously rely on such luxury :)

    Regarding your problems, my algorithm, when applied to tags would give each node a “subjective” view of the tagging semantic space. With the CAN approach it looks like you are looking for an “objective” (i.e., shared by all nodes) view.

    Maybe you could obtain something useful if you propagated the query in the social network, according to each node’s own view of “expertise” of their friends about some area of the semantic map. Just speculating…

  3. Yes, you are right – in a CAN, one places a given tag in a “shared” semantic space. However, for the p2p discovery problem, it would better to have a tag view tailored to each user (eg, for allowing personalizing search). What worries me is that p2p resource discovery is a dynamic schenario (in that many resources are frequently added). That is why it would be interesting to test the algorithm under varying churn rates – it may give us some intuitions on how robust the algorithm in dynamic settings is ;-)

  4. Indeed! I didn’t do experimentation about that yet, but that will be stuff I’ll certainly look into. I’d think it would be quite tolerant, though. A node with lower uptime could be seen as having edges with a lower weight, since it would interact with other nodes more rarely. And small variations in the structure of the network shouldn’t change too much the solution.