Graphs for distributing rewards

Question

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:
 visited.add(neighbor)
 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:
 graph.add_edge(parent, child)
 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:

enter image description here

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-3', 'Node-2')
 graph.add_edge('Node-4', 'Node-3')
 graph.add_edge('Node-5', 'Node-4')
 graph.add_edge('Node-6', 'Node-5')
 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))
 visited.add(predecessor)
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.

enter image description here

• Reinderien: Can you include a screenshot?
• Sᴀᴍ Onᴇᴌᴀ: @Reinderien perhaps it has been observed already but in case not - screenshots have been added,
• Bob: Thank you for your guidance @SᴀᴍOnᴇᴌᴀ

Answer 1

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

• Sᴀᴍ Onᴇᴌᴀ: 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.
• Bob: 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: @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.
• ShapeOfMatter: 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?
• Bob: Yes, I need to parse the whole graph backwards and reward every node.