GUI: random walk with real-time updates

[synctext]

visualization of trust buildup for virtual identities. Key issues: rendering, smoothing and node placement as nodes get added and pruned.

Depends: #20

initial prototype:

[boudewijn-tribler]

igraph is a library (also for python) that can allow us to generate large graphs. http://igraph.sourceforge.net/screenshots.html

[egbertbouman]

Updated prototype:

[NielsZeilemaker]

Closing ths one, bartercast isn't going to be integrated into Tribler any time soon. Hence, there is no direct need for a gui.

[synctext]

Our 2018 work is now deployed and a new "barter" graph is created from the Trustchain crawl

Older crawl, from original Bartercast by Rahim; the June 20 until September 9, 2009 crawl.

[synctext]

BarterCast III crawl from 2018 (now named Trustchain)

[devos50]

Real-time render of TrustChain interaction graph: http://explorer.tribler.org/visualization

[synctext]

Examples:

[cuileri]

OK, I'll focus on it.

[cuileri]

Initial stuff I've started with exploring Alexander's code, and decided to code from scratch because:

• His graph was considering only 2 hops. I think knowing about distant agents with high trustability is important.
• Given a directed graph where each edge shows the direction of download-upload traffic, his graph was considering only the outgoing neighbors as 'neighbors'. I think the agents who download from me are also my neighbor.
• To animate the walk, we need more control over the walk, for drawing the graph frame by frame.

Current state of the code

• Works with randomly generated directed graph
• Firstly, performs a bfs traversal on the undirected graph, to see neighborhood. Draws the neighborhood as a tree. I used this code for laying out the nodes.
• Performs and animates random walks. Size of the nodes represent the number of times the node is visited.
• For graphics, I used matplotlib.
• A snapshot from the execution of the code:

Issues

• Fake and static data
• Non-modular code

Next sprint (upon discussion with Johan)

• Connect to the live trustchain network
• Starting from no-knowledge, each node discovers 5 nodes per second continuously, which turns out to be 5-25 Trustchain data per second.
• Plot its k-hop neighborhood in real time. The neighborhood expands or shrinks over time.
• Perform 100-1000 random walk on the snapshot of the network and determine Trust Level per node. (Possibly with real time animation)
• No DB storage, just live and standalone!
• Automated decrease of Trust Levels over time, if a node is not visited that frequently.

[alexander-stannat]

The GUI looks very nice!

It might be worth having a discussion about the second point you mentioned. If one wants to take into account the nodes that have downloaded from the seed node as well as the nodes that have uploaded to it then a good way of doing this is by considering bidirectional edges, instead of our current unidirectional ones. This would enable us to evaluate peers, not just based on their up-to download ratio, but also on absolute values.

Also, we should think about somehow combining the BFS with the actual random walks to reduce complexity. Otherwise random walks might not be really necessary any more (as was discussed this week).

[cuileri]

I totally agree with Alexander that we need a different implementation of edge weights (or directions). I discussed it also with Johan, giving the following extreme case as an example: Consider two nodes which download and upload a huge amount of data from/to each other. At the end, the weight of the edge between them will not reflect the amount of traffic. Moreover, if they upload/download the same amount of data from each other, the weight of the edge will become zero.

I think we will come up with it a clever strategy over time.

[cuileri]

The current state of the code:

• I implemented a Transaction Discovery module. At this stage it either generates fake data or listens to the tribler crawler to feed Random Walk module.

• Current state of random walk module:

  • Before each batch of random walk, the node takes as an input a list of 3-tuples (from_node, to_node, edge_weight) and updates its own transaction graph (rooted at itself).

  • These new transactions update the existing graph proportionally, so that if no transaction is done on an existing edge, it is subject to be removed as the time goes by.

  • Edge weights show the amount of one-way traffic between nodes and are significant for the determination of the next step of a walk.

  • Having updated the graph w.r.t. new transactions, the node then performs random walks, and the procedure repeats.

  • Random walks determine the other nodes' importance observed by 'the node'.

  • A node which was discovered through 'transaction discovery' but not visited frequently during random walks are subject to be removed from the graph in order to control the size of the graph.

• The code is now modular (Transaction Discovery, Local Vision, Random Walk, Graph Positioning)

• In addition to the random walks, the update of local vision of the node w.r.t. the discovered transactions is also animated now.

Next sprint

• I have already started focusing more on research than on coding.

• Research for finding/offering a function to calculate trust values of nodes (may be the title of a new issue)

• Some interesting studies that will help us:

  • Inferring binary trust relationships in Web-based social networks. (link)
  • Personalized reputation management in P2P networks. (link)
  • A survey on Trust modeling (link).
  • Using Centrality Measures to Predict Helpfulness-Based Reputation in Trust Networks (link)

• We agreed with Bulat that we will use 16GB of tribler transaction history to make tests for our algorithms. He will prepare the interface which will feed my code with real data. We decided to spare a small portion of the data for determining the initial "the most trustable peers" list.

[synctext]

Easy bootstrap and visualisation idea to take "mathematics-of-trust into production usage. Show the user and include a first version of our trust formula. Possible goal for end of March: genesis trust swarm.

• crawl Trustchain network
• extract 25 MByte of most trustworthy, oldest, and central nodes (1 metric)
• Create Bittorrent swarm with 25 x 1 MByte .mblob records (Genesis Trust Swarm)
• Each Tribler client hard-coded downloads this data upon install
• With each completed .mblob we both have a trustchain record of the agent that helped us and Trustchain data.
• Ask these agents to produce records linking them directly to the genesis trust swarm. Thus creating a single connected component.
• this implies the design and implementation of a new Trustchain protocol message
• You are now linked to all genesis trust swarm records! (indirect transaction)
• real-time animation for exactly 20 second while downloading in the genesis trust swarm.
• show random walk animation to give them a feeling that this is not just another Bittorrent client. It's a new trustworthy protocol and leaderless ecosystem.
• Future sprints only:
  • check records. We now pre-trust the hard-coded genesis trust swarm.
  • latency community and never talk to strangers

[cuileri]

Detected a problem with both Alexander's and my implementation of random walks. Presented here.

[synctext]

New Attacker model: majority is malicious, however majority of evil nodes are overseas.

Brainstorm, combine latency-restricted communication #2541 with the 25MByte boostrap concept (oldest mention):

• new approach all agents self-organise into latency-based genesis trust swarms.
• Each genesis trust swarms independently determines the trust consensus of 25MByte.
• Discovery of various genesis trust swarms, at different network distance
• join various genesis swarms and determine their peers
• determine in which community the closest by peers reside
• bootstrap from this genesis trust swarm
• at regular intervals the contents of the genesis trust swarm is updated
• only members within acceptable short network latency are eligible voting members

Decided at last Dev Meeting: we will first launch an "animation-only" version of the genesis trust swarm in Tribler.

[synctext]

PR #4488