Algorithms for Graph Visualization

[mzargham]

After reviewing the existing data visualizations and data models, met with @decentralion to organize the effort towards meeting graph visualization use cases during the Hackathon. As such this issue identifies use cases and specifically focuses attention aspects to be addressed on site.

There are two use cases defined for graph visualizations

1. Editor: as a creator and/or editor of manual nodes and edges, I wish to see the nodes I have identified, the nodes I have added, and the edges associated with those nodes.
2. Explorer: as an explorer of the SourceCred graph, I wish to select a focus and a seed, then to see a neighborhood on nodes around the focus, with the choice of nodes determined by personalized pagerank relative to the seed. Furthermore, selecting a node in the from should change the focus to the selected node, but not change the personalized pagerank scores being used to select the nodes. [yes i know this is in graph speak not user language]

Case 1:
Upon review of the options, I determined that use case one is sufficiently well handled by the force directed graph layout and simple inclusions logic:

• include manual nodes added during the editor session
• include any nodes selected during the editor session
• include any edges between the included nodes
• plot via force directed layout or any built in position selector
• it may be necessary to impose a limit on the total number of selected nodes

Case 2:
In light of the analysis in case 1, i decided to decompose case 2, to treat the choice of which nodes to visualize and the algorithm for determining their positions. The case of determining their positions may be reduced to the same as position choices in case 1 and for the time being will be left to built in methods. In this case the choice of nodes to plot becomes the primary algorithm of interest for the hackathon data visualization.

Proposed Algorithm for node selection in case 2 is based on customized graph traversal approach in the spirit of @decentralion suggestion during our meeting:

inputs:

• identifier for the focus node
• for all nodes mapping from identifier to cred score (personalized pagerank variation),
• the edge data for the graph (required for computing shortest paths)

pseudo code:

step 1. *set up*
    set anchor to be node selected by user
    compute pagerank according to the seed selected by the user
    set the number of nodes 'K' you wish to display
step 2. *score the nodes by path*
     for each node in nodes:
          path[node] = list of nodes in the shortest path from node to anchor
          cost[node] = len(path[node])
          reward[node] = sum(PR(hop) for each hop in path[node])
          value [node] = reward[node]/cost[node]
step 3. *select nodes by score* 
     ordered = list of nodes ordered by value
     k=0
     nodes_to_plot = []
     while k < K and len(ordered>0):
           current = ordered.pop(0)
           if cost[current] <= K-k:
                    k= k+cost[current]
                    for hop in path[current]:
                             nodes_to_plot.append(hop)
                             if hop in ordered: remove it
step 4. *conclude*
     return nodes_to_plot

Tests:

• returned list should be length K
• all nodes returned should be valid keys in the node to cred mapping provided
• increasing the K should always result in a larger total cred over all nodes included
• all nodes returned must have a path to the anchor

The proposed methods is a variation (arguably multi-layer variation) of dijkstra's algorithm https://hackernoon.com/how-to-implement-dijkstras-algorithm-in-javascript-abdfd1702d04
the link above is a simple overview; i'll defer on what packages might make sense to use.