# Graphs for distributing rewards

I want to be able to distribute a total reward among referral network, where the distribution diminishes according to the depth of the network but the total sum of distributed rewards equals the initial total reward. I have attempted to use Graphs as a way to solve this.

With the assumptions that:

1. Give a fixed percentage of the total reward to the direct referrer.
2. Distribute the remaining reward down the referral chain in decreasing amounts.

The goal is for Node1 to receive 20% of the total reward off the top, with the remaining 80% distributed among all nodes, with decreasing amounts based on their distance from Node1. I want to also be able to support circular referrals and self referrals.

Code:

import networkx as nx
import matplotlib.pyplot as plt

def distribute_rewards(
graph: nx.DiGraph,
start_node: str,
total_reward: float,
direct_referral_ratio: float,
decrease_factor: float
) -> None:
"""
Distributes rewards within a referral network.

Args:
graph (nx.DiGraph): The referral network graph.
start_node (str): The node from which distribution starts.
total_reward (float): Total reward amount to distribute.
direct_referral_ratio (float): Ratio of the total reward given to the start node.
decrease_factor (float): Factor by which the reward decreases at each level.
"""
nx.set_node_attributes(graph, 0, 'reward')
direct_reward = total_reward * direct_referral_ratio
graph.nodes[start_node]['reward'] = direct_reward

remaining_reward = total_reward - direct_reward
level_weights: dict[int, float] = {}
queue: list[tuple[str, int]] = [(start_node, 0)]
visited: set[str] = {start_node}

while queue:
node, level = queue.pop(0)
level_weights.setdefault(level, 0)
level_weights[level] += decrease_factor ** level

for neighbor in graph.successors(node):
if neighbor not in visited:
queue.append((neighbor, level + 1))

total_weight = sum(level_weights.values())
level_rewards = {
level: (remaining_reward * weight) / total_weight
for level, weight in level_weights.items()
}

for node in graph.nodes:
level = nx.shortest_path_length(graph, source=start_node, target=node)
if level in level_rewards:
num_nodes_at_level = sum(
1 for n in graph.nodes if nx.shortest_path_length(graph, source=start_node, target=n) == level
)
graph.nodes[node]['reward'] += level_rewards[level] / num_nodes_at_level

def create_complex_graph(max_levels: int) -> nx.DiGraph:
"""
Creates a binary tree graph representing a referral network.

Args:
max_levels (int): The maximum depth of the referral network.

Returns:
nx.DiGraph: The generated referral network graph.
"""
graph = nx.DiGraph()
for level in range(max_levels):
for i in range(2**level):
parent = f'Node{2**level + i}'
children = [f'Node{2**(level + 1) + 2*i}', f'Node{2**(level + 1) + 2*i + 1}']
for child in children:

return graph

def visualize_graph(graph: nx.DiGraph):
layout = nx.spring_layout(graph, k=0.5, iterations=20)
node_sizes = [graph.nodes[node]['reward'] / 10 for node in graph]

# Draw nodes and edges
nx.draw_networkx_nodes(graph, layout, node_size=node_sizes, node_color='skyblue', edgecolors='black')
nx.draw_networkx_edges(graph, layout, arrows=True)

# Draw node labels
nx.draw_networkx_labels(graph, layout, font_size=8)

# Remove axis for a cleaner look and display the graph
plt.axis('off')
plt.show()

def main() -> None:
max_levels = 5
total_reward = 3500
direct_referrer = 'Node1'     # From the POV that Node1 is the direct referrer.
direct_referral_ratio = 0.2   # 20%
decrease_factor = 0.5         # 50%

graph = create_complex_graph(max_levels)
distribute_rewards(graph, direct_referrer, total_reward, direct_referral_ratio, decrease_factor)
for node in sorted(graph.nodes, key=lambda x: int(x.lstrip('Node'))):
print(f"{node}: Reward = {graph.nodes[node]['reward']:.2f}")

visualize_graph(graph)

if __name__ == "__main__":
main()


Edit

As requested here is a screenshot of the graph. It was created using create_complex_graph(max_levels=5) and I arbitrarily chose max_level=5 which generates 63 nodes. For context, the nodes on the graph represent people to be rewarded and the edges represent referrals. See below:

Edit 2

Given this is a reward/referral network, as a priority I want to accommodate the distribution of rewards up the referral chain from Node1 because the upstream direction identifies who initiated the referral chain and reveals the network of referrals that led to a specific user's inclusion in the system.

1. Distributing a fixed percentage to Node1.
2. Distributing the remaining reward upwards through the referral chain.
3. Limiting the distribution by either the remaining reward, a maximum number of referral levels, the absence of further predecessors.
import networkx as nx
import matplotlib.pyplot as plt

def create_simple_graph():
graph = nx.DiGraph()
graph.add_edge('Node0', 'Node1')  # Node0 refers Node1
return graph

def create_complex_graph():
graph = nx.DiGraph()

graph.add_edge('Node0', 'Node1')        # Node0 refers Node1 (Level 1)
graph.add_edge('Node-1', 'Node0')       # Node-1 refers Node0 (Level 2)
graph.add_edge('Node-2', 'Node-1')      # Node-2 refers Node-1 (Level 3)
graph.add_edge('Node-7', 'Node-6')      # Up to Node-7, making it 7 levels upstream.

return graph

def visualize_graph(graph: nx.DiGraph):
pos = nx.spring_layout(graph)
labels = nx.get_node_attributes(graph, 'reward')
nx.draw(
graph,
pos,
with_labels=True,
labels={
node: f"{node}\nReward: {reward:.2f}"
for node, reward in labels.items()
},
node_size=5000,
node_color='skyblue'
)
plt.show()

def distribute_rewards(
graph: nx.DiGraph,
start_node: str,
total_reward: float,
start_node_ratio: float,
upward_referral_ratio: float,
max_referral_levels: int
) -> None:
nx.set_node_attributes(graph, 0, 'reward')
graph.nodes[start_node]['reward'] = total_reward * start_node_ratio
remaining_reward = total_reward - graph.nodes[start_node]['reward']

# Start with the assumption that all directly and indirectly referred nodes need some reward
# We will first focus on distributing rewards to the start node and its direct and indirect referrers

# Initialize a queue to process nodes level by level (breadth-first)
queue = [(start_node, 0)]
visited = set()

while queue:
current_node, level = queue.pop(0)
if level > 0:
# Calculate and distribute reward
reward_for_node = (remaining_reward * upward_referral_ratio) / (2 ** (level - 1))
graph.nodes[current_node]['reward'] += reward_for_node
remaining_reward -= reward_for_node

if level < max_referral_levels:
for predecessor in graph.predecessors(current_node):
if predecessor not in visited:
queue.append((predecessor, level + 1))

def main():
graph = create_complex_graph()
distribute_rewards(
graph,
'Node1',                     # Start Point
1000,                        # Total Reward
0.33,                        # 33% of total reward goes to the start node
0.1,                         # 10% of the remaining reward distributed upwards per level
7                            # Maximum levels to go up in the referral chain
)

for node in graph.nodes:
print(f"{node}: Reward = \${graph.nodes[node]['reward']:.2f}")

visualize_graph(graph)

if __name__ == "__main__":
main()


See the graph below which at the moment is a tree structure. I plan to extend this solution to support self-referrals (Node1, referring themselves) and reverse-referrals so I think keeping it as a graph is probably a sane thing to do.

• Can you include a screenshot? Mar 18 at 13:44
• @Reinderien perhaps it has been observed already but in case not - screenshots have been added, Mar 19 at 5:46
• Thank you for your guidance @SᴀᴍOnᴇᴌᴀ
– Bob
Mar 19 at 5:48

The bounty says you're "looking for an answer from a reputable source", but it's unclear what you mean by that. Is there a specific question you want a reputable answer to?

The algorithm you've written is depth-first search; it's canonical and typical and fine. From a theoretical CS perspective my only quibble would be that, in theory, you should be able to use the one search for all of your graph traversal. Instead you're following up with nx.shortest_path_length (and then doing that again in a nested loop). Since you're building your own DFS process, it's probably possible to re-write it to do everything you want, but I'm pretty sure we're going to find a networkx tool that will simplify the whole problem.

... and yes: bfs_layers will serve. I was hoping for some functional-style traversal process we could use to do everything at once; it's probably there I just didn't find it.

With a single call to bfs_layers, you'll get a data structure that can replace your whole while queue:... and all your calls to nx.shortest_path_length. There are some other aspects of your code that I would have written differently, but IDK how much time you want to spend polishing this.

A detail I didn't understand until I started testing: The root node gets their "direct" amount plus their exponential-proportionate share of the remainder. That actually answers several questions so I assume it's on purpose. Consider calling the "direct" share a "bonus", to make this more clear.

from dataclasses import dataclass
from typing import Sequence

@dataclass(frozen=True)
class WeightedLevel:
rate: float
nodes: Sequence[str]

def distribute_rewards(
graph: nx.DiGraph,
start_node: str,
total_reward: float,
direct_referral_ratio: float,
decrease_factor: float
) -> None:
"""
Distributes rewards within a referral network.

Args:
graph: The referral network graph.
start_node: The node from which distribution starts.
total_reward: Total reward amount to distribute.
direct_referral_ratio: Ratio of the total reward given to the start node.
decrease_factor: Factor by which the reward decreases at each level.
"""
nx.set_node_attributes(graph, 0, 'reward')
direct_reward = total_reward * direct_referral_ratio
remaining_reward = total_reward - direct_reward
visited: set[str] = set()

def dedupe(layer: list[str]) -> list[str]:  # there's probably a better way
deduped = [n for n in layer if n not in visited]
visited.update(deduped)
return deduped

levels = [WeightedLevel(decrease_factor ** i, nodes)
for (i, nodes)
in enumerate(map(dedupe, nx.bfs_layers(graph, start_node)))
if nodes]
weight_value = remaining_reward / sum(wl.rate * len(wl.nodes)
for wl in levels)

for wl in levels:
reward = weight_value * wl.rate
for node in wl.nodes:
graph.nodes[node]['reward'] = reward

graph.nodes[start_node]['reward'] += direct_reward

• It appears that looking for an answer from a reputable source is the default option when starting a bounty so the OP may not have spent much time on that step. Mar 20 at 20:09
• Great, this is simple and much cleaner. Will leave the answer open for a little longer incase anyone else wants a go. Also, @SᴀᴍOnᴇᴌᴀ was right, teehee.
– Bob
Mar 20 at 23:31
• @ShapeOfMatter - when I run this code it seems like only 2 levels are created, even tho I supply it with a graph of 7 edges.
– Bob
Mar 21 at 1:29
• Oh, maybe I misunderstood how your BFS was using the graph. Am I inffering correctly that you want to parse the whole graph backward? Try passing nx.reverse_view(...) to bfs_layers, does that do what you want? Mar 21 at 1:45
• Yes, I need to parse the whole graph backwards and reward every node.
– Bob
Mar 21 at 6:21