2
\$\begingroup\$

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

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

1 Answer 1

4
+100
\$\begingroup\$

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
\$\endgroup\$
10
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Mar 20 at 20:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bob
    Mar 20 at 23:31
  • \$\begingroup\$ @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. \$\endgroup\$
    – Bob
    Mar 21 at 1:29
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 21 at 1:45
  • \$\begingroup\$ Yes, I need to parse the whole graph backwards and reward every node. \$\endgroup\$
    – Bob
    Mar 21 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.