PageRank for premix routing?

Matteo Dell'Amico (http://www.disi.unige.it/person/DellamicoM/) gave an
interesting talk at UCL a few months ago, and I thought his work on
neighbourhood maps might be relevant to Freenet.

Neighbourhood maps start from the observation that social networks are
fast mixing, meaning that if you take a random walk from any node, the
probability of ending up at a given node quickly becomes independent of
your starting point. That means a local view of the network is in some
sense typical of the network as a whole. And that, in turn, means you
can run algorithms like PageRank over a local view of the network, and
get results that are similar to the results you'd get from a global view
of the network.

Matteo uses a local view of the network to compute subjective trust
rankings: each node broadcasts its list of neighbours for a small number
of hops, uses the received broadcasts to build a neighbourhood map, and
runs PageRank over the map using itself as the source. Assuming that
each link in the network represents a trust relationship, the resulting
rankings give subjective trust values to the nodes.

PageRank works by diffusing some property (trust in this case) through a
network, starting from a source. In each round, the source produces one
unit of trust and shares it across its outgoing edges. The trust
arriving on each node's incoming edges is summed, reduced by a damping
factor, and shared across its outgoing edges. A node's rank is the
amount of trust it receives per round when the algorithm reaches
a steady state.

PageRank has two nice properties when used as a trust metric: you can't
amplify your trust by creating lots of outgoing edges, and you can't
'trap' trust in a cluster of nodes that link to one another.

Why is this relevant to Freenet? Premix routing is supposed to prevent
statistical attacks where a node sees a series of related messages (eg
requests for parts of the same file) and concludes that the sender of
the messages must be nearby. In premix routing, the sender builds a
tunnel to a random node and sends all the related messages through the
tunnel. But how do you select a random node? Even in a darknet, I can
create a hundred Sybil nodes and link them all to my 'real' node,
without having to persuade anyone to trust them. A sender who chooses
randomly from a list of nearby nodes will be likely to select one of my
Sybil nodes, and a random walk will also be likely to end up on a Sybil
node. But if the sender builds a neighbourhood map and uses PageRank to
choose the probability of selecting each node, I gain no advantage by
creating a large number of nodes.

This wouldn't work on an opennet, however...

Cheers,
Michael