State-Space Path Divergence

The problem

It is difficult to determine which multi-step paths provide the most unique information when exploring complex networks. Standard methods often struggle to distinguish between paths that simply move forward and those that explore new territory.

What it does

It ranks paths based on how much unique ground they cover and how much they branch out into different directions. It looks at both the unique spots visited and the variety of ways those spots connect.

Why it matters

It provides a way to measure both the breadth and the unique reach of a path at the same time.

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 scorer.py
========================================================================
STATE-SPACE PATH DIVERGENCE — Nowness Research Lab
========================================================================
Path                                                     Diverg  Entropy   Branch
------------------------------------------------------------------------
gene_a  protein_x  pathway_k  treatment_option           +0.5045  +0.2664  +0.8617
gene_a  protein_x  disease_z  drug_candidate  treatment_option  +0.4865  +0.3455  +0.6981
gene_a  enzyme_1  pathway_k  treatment_option            +0.4834  +0.2313  +0.8617
gene_b  protein_x  enzyme_1  disease_w  drug_candidate   +0.4727  +0.2596  +0.7925
gene_a  protein_y  pathway_k  disease_z  drug_candidate  +0.4711  +0.3197  +0.6981
gene_a  protein_x  drug_candidate  treatment_option      +0.4655  +0.2664  +0.7642
gene_a  protein_x  drug_candidate                        +0.4647  +0.1770  +0.8962
attention  bert  transformer  gpt  benchmark             +0.4478  +0.2668  +0.7194
enzyme_1  pathway_k  disease_z  treatment_option         +0.4453  +0.2789  +0.6950
gene_b  protein_x  disease_z  drug_candidate             +0.4316  +0.2560  +0.6950
enzyme_1  d

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 254 lines, one file, standard library only.

#!/usr/bin/env python3
"""State-Space Path Divergence Scorer — Nowness Research Lab

Combines Path Diversity score logic (node-coverage entropy across paths)
with State-Space Exploration techniques (transition branching factor per node)
to produce a composite ranking of multi-hop paths in a knowledge graph.

Scoring formula:
    divergence(path) = alpha * coverage_entropy(path) + beta * branching_reward(path)

Algorithm core:
    1. Coverage Entropy — Shannon entropy of a path's node set relative to the
       global node-frequency distribution. Rare-node paths score higher.
       Deduplicates overlapping nodes within a path to compute unique coverage.
    2. Branching Reward — sum over hops of log(1 + out_degree) for each
       intermediate node. High-branching transitions represent higher
       state-space exploration and are rewarded.
    3. Composite score combines both via configurable alpha/beta weights.
       Paths are ranked by divergence descending.
"""

from __future__ import annotations

import math
from collections import Counter
from typing import List, Mapping


class ScoredPath:
    __slots__ = ("path", "divergence", "coverage_entropy", "branching_reward")

    def __init__(
        self,
        path: List[str],
        divergence: float,
        coverage_entropy: float,
        branching_reward: float,
    ) -> None:
        self.path = path
        self.divergence = divergence
        self.coverage_entropy = coverage_entropy
        self.branching_reward = branching_reward

    def __repr__(self) -> str:
        path_str = " -> ".join(self.path)
        return (
            f"Path({path_str!r}, divergence={self.divergence:.4f}, "
            f"entropy={self.coverage_entropy:.4f}, branching={self.branching_reward:.4f})"
        )


class StateSpacePathDivergence:
    """State-Space Path Divergence scorer.

    Parameters
    ----------
    adjacency : Mapping[str, Sequence[str]]
        Directed graph as adjacency list. Node → list of outgoing neighbours.
    alpha : float, default=0.6
        Weight for coverage-entropy contribution.
    beta : float, default=0.4
        Weight for branching-reward contribution.
    """

    def __init__(
        self,
        adjacency: Mapping[str, List[str]],
        alpha: float = 0.6,
        beta: float = 0.4,
    ) -> None:
        self._adj = {k: list(v) for k, v in adjacency.items()}
        self.alpha = alpha
        self.beta = beta

        self._nodes: set[str] = set(self._adj)
        for targets in self._adj.values():
            self._nodes.update(targets)

        self._outdegree: dict[str, int] = {n: len(self._adj.get(n, [])) for n in self._nodes}

        self._node_freq: Counter[str] = Counter()
        for src, targets in self._adj.items():
            self._node_freq[src] += 1
            for t in targets:
                self._node_freq[t] += 1

    # ── coverage entropy (path diversity via unique node set) ──────────

    def _unique_nodes(self, path: List[str]) -> List[str]:
        """Return the path's nodes in first-occurrence order, deduplicated.

        Multi-hop paths with overlapping/repeated nodes have those repeats
        collapsed so that unique coverage is measured, not raw length.
        """
        seen: set[str] = set()
        unique: list[str] = []
        for node in path:
            if node not in seen:
                seen.add(node)
                unique.append(node)
        return unique

    def coverage_entropy(self, path: List[str]) -> float:
        """Path Diversity score: entropy of unique node coverage.

        Computes Shannon entropy over the frequency distribution of the
        path's distinct nodes relative to the global node-frequency map.
        Overlapping/repeated nodes within the path are deduplicated.

        Higher value → path covers structurally rarer nodes.
        """
        unique = self._unique_nodes(path)
        if len(unique) == 0:
            return 0.0
        total_occurrences = sum(self._node_freq.values()) or 1
        entropy = 0.0
        for node in unique:
            prob = self._node_freq.get(node, 1) / total_occurrences
            entropy -= prob * math.log(prob + 1e-12)
        max_entropy = math.log(max(len(self._node_freq), 1))
        return entropy / max_entropy if max_entropy > 0 else 0.0

    # ── branching reward (state-space exploration via out-degree) ─────

    def branching_reward(self, path: List[str]) -> float:
        """Reward for state-transition branching at each intermediate node.

        For every hop (source node, excluding terminal), accumulate:
            log(1 + out_degree)

        The reward is normalised by path length and max out-degree in the graph.
        """
        if len(path) < 2:
            return 0.0
        reward = 0.0
        for node in path[:-1]:
            od = self._outdegree.get(node, 0)
            reward += math.log(1 + od)
        max_deg = max(self._outdegree.values(), default=1)
        hops = len(path) - 1
        denominator = hops * math.log(1 + max_deg)
        return reward / denominator if denominator > 0 else 0.0

    # ── composite divergence ──────────────────────────────────────────

    def divergence_score(self, path: List[str]) -> float:
        """Composite State-Space Path Divergence score.

        divergence = alpha * coverage_entropy + beta * branching_reward

        Returns float in [0, 1]. Higher values mean more divergent
        (structurally unique node coverage + higher branching exploration).
        """
        return self.alpha * self.coverage_entropy(path) + self.beta * self.branching_reward(path)

    # ── ranking ───────────────────────────────────────────────────────

    def score_paths(self, paths: List[List[str]]) -> List[ScoredPath]:
        """Score and rank a collection of multi-hop paths.

        Returns ScoredPath list sorted by divergence descending.
        """
        scored = [
            ScoredPath(
                path=p,
                divergence=self.divergence_score(p),
                coverage_entropy=self.coverage_entropy(p),
                branching_reward=self.branching_reward(p),
            )
            for p in paths
        ]
        scored.sort(key=lambda sp: sp.divergence, reverse=True)
        return scored

    def top_divergent_paths(
        self,
        paths: List[List[str]],
        top_k: int = 5,
    ) -> List[ScoredPath]:
        """Return top-k most divergent paths."""
        return self.score_paths(paths)[:top_k]


# ── demo ──────────────────────────────────────────────────────────────


def main() -> None:
    graph: dict[str, list[str]] = {
        "gene_a": ["protein_x", "protein_y", "disease_z"],
        "gene_b": ["protein_x", "pathway_k"],
        "protein_x": ["disease_z", "drug_candidate"],
        "protein_y": ["pathway_k"],
        "enzyme_1": ["pathway_k", "disease_w"],
        "disease_w": ["drug_candidate", "treatment_option"],
        "attention": ["transformer", "bert"],
        "bert": ["transformer", "nlp_task"],
        "transformer": ["gpt", "nlp_task"],
        "nlp_task": ["benchmark"],
        "gpt": ["benchmark"],
        "benchmark": [],
        "pathway_k": ["disease_z", "treatment_option"],
        "disease_z": ["drug_candidate"],
        "drug_candidate": ["treatment_option"],
        "treatment_option": [],
        "path_z": ["treatment_option"],
    }

    scorer = StateSpacePathDivergence(graph, alpha=0.6, beta=0.4)

    candidate_paths = [
        ["gene_a", "protein_x", "disease_z", "drug_candidate", "treatment_option"],
        ["gene_a", "protein_y", "pathway_k", "disease_z", "drug_candidate"],
        ["gene_b", "protein_x", "disease_z", "drug_candidate"],
        ["gene_a", "enzyme_1", "pathway_k", "treatment_option"],
        ["attention", "bert", "transformer", "gpt", "benchmark"],
        ["attention", "transformer", "gpt", "benchmark"],
        ["enzyme_1", "disease_w", "drug_candidate", "treatment_option"],
        ["gene_a", "protein_x", "drug_candidate", "treatment_option"],
        ["gene_a", "protein_x", "drug_candidate"],
        ["gene_a", "protein_x", "pathway_k", "treatment_option"],
        ["gene_b", "protein_x", "enzyme_1", "disease_w", "drug_candidate"],
        ["enzyme_1", "pathway_k", "disease_z", "treatment_option"],
    ]

    results = scorer.score_paths(candidate_paths)

    print("=" * 72)
    print("STATE-SPACE PATH DIVERGENCE — Nowness Research Lab")
    print("=" * 72)
    print(f"{'Path':<55} {'Diverg':>7}  {'Entropy':>7}  {'Branch':>7}")
    print("-" * 72)

    for sp in results:
        label = "  ".join(sp.path)
        print(
            f"{label:<55}  {sp.divergence:+.4f}  "
            f"{sp.coverage_entropy:+.4f}  {sp.branching_reward:+.4f}"
        )

    print("-" * 72)
    print(f"Graph: {len(graph)} nodes, {sum(len(v) for v in graph.values())} edges")
    print(f"Paths evaluated: {len(results)}")
    print(f"alpha={scorer.alpha:.1f}  beta={scorer.beta:.1f}")

    print("\n--- Top-3 most divergent paths ---")
    for i, sp in enumerate(scorer.top_divergent_paths(candidate_paths, top_k=3)):
        print(
            f"  #{i+1} divergence={sp.divergence:.4f}  "
            f"path={' -> '.join(sp.path)}"
        )


if __name__ == "__main__":
    main()