Basic Eigenvector Simulation

In the post PageRank and Token Design we discuss the basic ideas surrounding Eigenvector-based algorithms and their applications in decentralized cryptonetworks and DePIN. In this post, we walk through an intentionally simplified example to show how a producer graph would look in a generic marketplace.

You can visualize a network as a bipartite graph G=(U,V,E)G = (U, V, E) representing producers UU and buyers VV as nodes, with weighted edges EE capturing transactions between them. Edge weights w(u,v)w(u, v) track the cumulative fees contributed by producer uu from transactions with buyer vv.

To capture both the economic activity and the network influence of each node, we introduce a graph value metric that incorporates eigenvector centrality. For each producer uu, we define the graph value GuG_u as:

Gu=αECu+(1α)(u,v)Ew(u,v)G_u = \alpha \cdot |EC_u| + (1 - \alpha) \cdot \sum_{(u,v)\in E} w(u,v)

Where:

  • ECu|EC_u| is the absolute value of the eigenvector centrality of node uu
  • α\alpha is a tunable parameter between 0 and 1
  • (u,v)inEw(u,v)\sum_{(u,v)in E} w(u,v) is the sum of all edge weights connected to uu

Using the absolute value in the calculation:

Ensures Non-negativity: This approach guarantees that all centrality measures contribute positively to the graph value, aligning with the typical requirements of token distribution mechanisms where negative contributions are not practical.

Preserves the Interpretative Integrity: While taking the absolute value can sometimes mask the directionality (if relevant), in many network applications, especially those involving token distributions or influence measures, the magnitude of centrality is more critical than its direction.

The eigenvector centrality ECuEC_u is calculated by solving the eigenvector equation:


The eigenvector centrality ECuEC_u is calculated by solving the eigenvector equation:

λx=Ax\lambda \mathbf{x} = A\mathbf{x}

Where:

  • AA is the adjacency matrix of the graph
  • λ\lambda is the largest eigenvalue
  • x\mathbf{x} is the corresponding eigenvector

The eigenvector centrality of a node is its corresponding value in the normalized eigenvector x\mathbf{x}.

This graph value metric GuG_u combines the node's economic activity (represented by the sum of edge weights) with its structural importance in the network (represented by its eigenvector centrality). The parameter α\alpha allows for tuning the balance between these two factors.


Simple Example of a Dynamic Graph

Let's simulate a small network with 2 producers (P1, P2) and 3 buyers (B1, B2, B3). We'll use α=0.5\alpha = 0.5 for our calculations.

In Python, we can defined a function calculate_graph_values that performs our calculations with the NetworkX package.

import numpy as np
import networkx as nx
 
def calculate_graph_values(G, alpha=0.5):
    # Ensure consistent node ordering
    node_order = ['P1', 'P2', 'B1', 'B2', 'B3']
    
    # Create adjacency matrix
    A = nx.to_numpy_array(G, nodelist=node_order)
    
    # Calculate eigenvector centrality
    eigenvalues, eigenvectors = np.linalg.eig(A)
    largest_index = np.argmax(eigenvalues)
    eigenvector = eigenvectors[:, largest_index].real
    
    # Normalize eigenvector
    eigenvector = np.abs(eigenvector) / np.linalg.norm(eigenvector)
    
    # Calculate graph values for producers
    graph_values = {}
    for i, node in enumerate(node_order):
        if node.startswith('P'):
            economic_activity = sum(G[node][neighbor]['weight'] for neighbor in G[node])
            graph_values[node] = alpha * eigenvector[i] + (1 - alpha) * economic_activity
    
    return A, eigenvector, graph_values

Initial transaction graph:

We will define an initial graph:

# Create initial graph
G = nx.Graph()
G.add_edge('P1', 'B1', weight=2)
G.add_edge('P2', 'B2', weight=3)
G.add_edge('P2', 'B3', weight=1)

Visually, this will look like this:

When we run the graph through our calculate_graph_values function as:

A, eigenvector, graph_values = calculate_graph_values(G)

we produce the following results.

Updated adjacency matrix AA':

P1P2B1B2B3
P100200
P200031
B120000
B203000
B301000

Solving λx=Ax\lambda \mathbf{x} = A\mathbf{x}, we get the normalized absolute eigenvector value for each node:

NodeValue
P10.0000
P20.7071
B10.0000
B20.6708
B30.2236
Graph values:
GP1=1.0000GP2=2.3536\begin{align*} G_{P1} &= 1.0000 \\ G_{P2} &= 2.3536 \end{align*}

Transaction from P1 to B2 with ff = 2

Next, we will add a new transaction with revenue contribution 2 between node P1 and node B2.

# Stage 2: New transaction P1 to B2
G.add_edge('P1', 'B2', weight=2)

Updated transaction graph:

When we run the updated graph through our calculate_graph_values function as:

A, eigenvector, graph_values = calculate_graph_values(G)

we produce the following results.

Updated adjacency matrix AA':

P1P2B1B2B3
P100220
P200031
B120000
B223000
B301000

Solving λx=Ax\lambda \mathbf{x} = A\mathbf{x}, we get the normalized absolute eigenvector value for each node:

NodeValue
P10.4571
P20.5395
B10.2354
B20.6521
B30.1389
Updated graph values:
GP1=2.2258GP2=2.7721\begin{align*} G_{P1}' &= 2.2258 \\ G_{P2}' &= 2.7721 \end{align*}

Transaction from P2 to B1 with ff = 1

Next, we will add a new transaction with revenue contribution 1 between node P2 and node B1.

# Stage 2: New transaction P1 to B2
G.add_edge('P2', 'B1', weight=1)

Updated transaction graph:

When we run the updated graph through our calculate_graph_values function as:

A, eigenvector, graph_values = calculate_graph_values(G)

we produce the following results.

Updated adjacency matrix AA'':

P1P2B1B2B3
P100220
P200131
B121000
B223000
B301000

Solving λx=Ax\lambda \mathbf{x} = A\mathbf{x}, we get the normalized absolute eigenvector value for each node:

NodeValue
P10.4516
P20.5441
B10.3446
B20.6037
B30.1296
Updated graph values:
GP1=2.2258GP2=2.7721\begin{align*} G_{P1}'' &= 2.2258 \\ G_{P2}'' &= 2.7721 \end{align*}
Overview of the basic MEC Token distributions

Throughout the simulation, we observe:

  1. The graph value of P1 increased significantly after its transaction with B2, reflecting both increased economic activity and improved network position by connecting with the P2 graph.
  2. P2's graph value increased more modestly but consistently, benefiting from both its initial strong position and new transaction.
  3. The eigenvector centrality captures the nodes' importance in the network structure, which changes with new connections.
  4. The combined metric balances economic activity with network influence, providing a more comprehensive measure of each producer's contribution to the platform.