Skip to content

Backbone

kenon.backbone.apply_disparity_filter(graph)

Compute and attach disparity statistics to all edges in-place.

Adds the following attributes to each edge:

  • norm_weight: weight / node strength
  • alpha: disparity significance
  • alpha_ptile: alpha percentile among all edges

Adds strength attribute to each node.

Parameters:

Name Type Description Default
graph SemanticGraph

A weighted networkx Graph with weight edge attributes.

 required

Returns:

Type Description
list[float]

List of all alpha values (for threshold inspection).
Contract
  • Modifies the graph in-place.
  • Every edge gets norm_weight, alpha, and alpha_ptile attributes.
  • Every node gets a strength attribute.
Example

import networkx as nx g = nx.Graph() g.add_edge("a", "b", weight=0.8) g.add_edge("b", "c", weight=0.3) g.add_edge("a", "c", weight=0.5) alphas = apply_disparity_filter(g) len(alphas) == g.number_of_edges() True

Source code in kenon/backbone.py 
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
def apply_disparity_filter(graph: SemanticGraph) -> list[float]:
    """Compute and attach disparity statistics to all edges in-place.

    Adds the following attributes to each edge:

    - ``norm_weight``: weight / node strength
    - ``alpha``: disparity significance
    - ``alpha_ptile``: alpha percentile among all edges

    Adds ``strength`` attribute to each node.

    Args:
        graph: A weighted networkx Graph with ``weight`` edge attributes.

    Returns:
        List of all alpha values (for threshold inspection).

    Contract:
        - Modifies the graph in-place.
        - Every edge gets ``norm_weight``, ``alpha``, and ``alpha_ptile`` attributes.
        - Every node gets a ``strength`` attribute.

    Example:
        >>> import networkx as nx
        >>> g = nx.Graph()
        >>> g.add_edge("a", "b", weight=0.8)
        >>> g.add_edge("b", "c", weight=0.3)
        >>> g.add_edge("a", "c", weight=0.5)
        >>> alphas = apply_disparity_filter(g)
        >>> len(alphas) == g.number_of_edges()
        True
    """
    if graph.number_of_edges() == 0:
        return []

    # Compute node strengths
    for node in graph.nodes():
        strength = sum(
            data.get("weight", 1.0) for _, _, data in graph.edges(node, data=True)
        )
        graph.nodes[node]["strength"] = strength

    # Compute alpha for each edge (take minimum alpha from both endpoints)
    alphas: list[float] = []
    for u, v, data in graph.edges(data=True):
        weight = data.get("weight", 1.0)

        strength_u = graph.nodes[u]["strength"]
        degree_u = float(graph.degree(u))
        norm_u = weight / strength_u if strength_u > 0 else 0.0
        alpha_u = get_disparity_significance(norm_u, degree_u)

        strength_v = graph.nodes[v]["strength"]
        degree_v = float(graph.degree(v))
        norm_v = weight / strength_v if strength_v > 0 else 0.0
        alpha_v = get_disparity_significance(norm_v, degree_v)

        alpha = min(alpha_u, alpha_v)
        norm_weight = min(norm_u, norm_v)

        data["norm_weight"] = norm_weight
        data["alpha"] = alpha
        alphas.append(alpha)

    # Compute alpha percentiles
    sorted_alphas = np.array(sorted(alphas))
    for _u, _v, data in graph.edges(data=True):
        alpha = data["alpha"]
        ptile = float(np.searchsorted(sorted_alphas, alpha)) / len(sorted_alphas)
        data["alpha_ptile"] = ptile

    return alphas

kenon.backbone.extract_backbone(graph, min_alpha_ptile=0.5, min_degree=2)

Extract the backbone of a graph using the disparity filter.

Removes edges whose alpha percentile falls below min_alpha_ptile, then prunes isolated nodes with degree below min_degree.

Parameters:

Name Type Description Default
graph SemanticGraph

Input weighted graph. Will be copied — original is not mutated.

 required
min_alpha_ptile float

Edges below this alpha percentile are removed. Must be in [0, 1]. Higher values = more aggressive pruning.

 0.5
min_degree int

Nodes with degree below this after edge removal are pruned.

 2

Returns:

Type Description
SemanticGraph

A new networkx.Graph containing only backbone edges and nodes.
Contract
  • Original graph is never mutated (deep copy).
  • Result has <= nodes and <= edges compared to the original.
  • All remaining nodes satisfy degree >= min_degree.
Example

import networkx as nx g = nx.path_graph(5) for u, v in g.edges(): ... g[u][v]["weight"] = float(v + 1) backbone = extract_backbone(g, min_alpha_ptile=0.3) backbone.number_of_nodes() <= g.number_of_nodes() True

Source code in kenon/backbone.py 
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
def extract_backbone(
    graph: SemanticGraph,
    min_alpha_ptile: float = 0.5,
    min_degree: int = 2,
) -> SemanticGraph:
    """Extract the backbone of a graph using the disparity filter.

    Removes edges whose alpha percentile falls below ``min_alpha_ptile``,
    then prunes isolated nodes with degree below ``min_degree``.

    Args:
        graph: Input weighted graph. Will be **copied** — original is not mutated.
        min_alpha_ptile: Edges below this alpha percentile are removed.
            Must be in [0, 1]. Higher values = more aggressive pruning.
        min_degree: Nodes with degree below this after edge removal are pruned.

    Returns:
        A new ``networkx.Graph`` containing only backbone edges and nodes.

    Contract:
        - Original graph is never mutated (deep copy).
        - Result has <= nodes and <= edges compared to the original.
        - All remaining nodes satisfy ``degree >= min_degree``.

    Example:
        >>> import networkx as nx
        >>> g = nx.path_graph(5)
        >>> for u, v in g.edges():
        ...     g[u][v]["weight"] = float(v + 1)
        >>> backbone = extract_backbone(g, min_alpha_ptile=0.3)
        >>> backbone.number_of_nodes() <= g.number_of_nodes()
        True
    """
    if graph.number_of_edges() == 0:
        return nx.Graph()

    result = copy.deepcopy(graph)
    apply_disparity_filter(result)

    # Remove edges below the alpha percentile threshold
    edges_to_remove = [
        (u, v)
        for u, v, data in result.edges(data=True)
        if data.get("alpha_ptile", 0.0) < min_alpha_ptile
    ]
    result.remove_edges_from(edges_to_remove)

    # Remove nodes below minimum degree (iteratively until stable)
    changed = True
    while changed:
        nodes_to_remove = [
            node for node in list(result.nodes()) if result.degree(node) < min_degree
        ]
        changed = len(nodes_to_remove) > 0
        result.remove_nodes_from(nodes_to_remove)

    return result

kenon.backbone.disparity_integral(x, k)

Compute the definite integral for the disparity filter PDF.

Parameters:

Name Type Description Default
x float

Normalised edge weight. Must not equal 1.0.

 required
k float

Node degree. Must not equal 1.0.

 required

Returns:

Type Description
float

Value of the integral ((1 - x)^k) / ((k - 1) * (x - 1)).
Contract
  • x must not equal 1.0 (division by zero).
  • k must not equal 1.0 (division by zero).
Example

abs(disparity_integral(0.5, 3.0) - disparity_integral(0.0, 3.0)) > 0 True

Source code in kenon/backbone.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def disparity_integral(x: float, k: float) -> float:
    """Compute the definite integral for the disparity filter PDF.

    Args:
        x: Normalised edge weight. Must not equal 1.0.
        k: Node degree. Must not equal 1.0.

    Returns:
        Value of the integral ``((1 - x)^k) / ((k - 1) * (x - 1))``.

    Contract:
        - ``x`` must not equal 1.0 (division by zero).
        - ``k`` must not equal 1.0 (division by zero).

    Example:
        >>> abs(disparity_integral(0.5, 3.0) - disparity_integral(0.0, 3.0)) > 0
        True
    """
    return ((1.0 - x) ** k) / ((k - 1.0) * (x - 1.0))

kenon.backbone.get_disparity_significance(norm_weight, degree)

Compute the alpha significance score for a single edge.

Parameters:

Name Type Description Default
norm_weight float

Edge weight normalised by node strength.

 required
degree float

Degree of the node.

 required

Returns:

Type Description
float

Alpha value in [0, 1]. Lower alpha = more significant.
Contract
  • If degree <= 1, returns 0.0.
  • Result is clipped to [0, 1].
Example

alpha = get_disparity_significance(0.5, 3.0) 0.0 <= alpha <= 1.0 True

Source code in kenon/backbone.py 
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def get_disparity_significance(norm_weight: float, degree: float) -> float:
    """Compute the alpha significance score for a single edge.

    Args:
        norm_weight: Edge weight normalised by node strength.
        degree: Degree of the node.

    Returns:
        Alpha value in [0, 1]. Lower alpha = more significant.

    Contract:
        - If ``degree`` <= 1, returns 0.0.
        - Result is clipped to [0, 1].

    Example:
        >>> alpha = get_disparity_significance(0.5, 3.0)
        >>> 0.0 <= alpha <= 1.0
        True
    """
    if degree <= 1.0:
        return 0.0
    return 1.0 - (degree - 1.0) * (
        disparity_integral(norm_weight, degree) - disparity_integral(0.0, degree)
    )