Incremental update of trust levels in a dynamic blockchain graph

[synctext]

Within Tribler we aim to calculate and show trust level of our neighbors.

Trust levels evolve over time, as more information is coming in from our blockchain. Restarting the calculation from cratch every time new information comes in is prohibitively expensive.

We require an incremental algorithm which can update our sybil-resilient random walk algorithm. With our dataset from our deployed network it currently takes 6-9 seconds to do a full calculation. When we have a dataset locally of 50000 peers around us, we require an incremental algorithm.

Key related work by Stanford and Twitter engineers "Fast incremental and personalized PageRank":

For global PageRank, we assume that the social network
has n nodes, and m adversarially chosen edges arrive in a
random order. We show that with a reset probability of
!, the expected total work needed to maintain an accurate
estimate (using the Monte Carlo method) of the PageRank
of every node at all times is O( n ln m
!2 ). This is significantly
better than all known bounds for incremental PageRank.
For instance, if we naively recompute the PageRanks as
each edge arrives, the simple power iteration method needs
Ω( m2
ln(1/(1−!)) ) total time and the Monte Carlo method needs
O(mn/!) total time; both are prohibitively expensive. We
also show that we can handle deletions equally efficiently.

• IRWR: incremental random walk with restart
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem

No decent Python implementation of incremental PageRank seems to exist.