Unweighted Sparsification#

Examples in this module use the unweighted version of nx.les_miserables_graph(). Methods return scored full graphs with sparsify_score and sparsify_keep; apply boolean_filter() to extract sparse backbones. Complexity classes are provided in each function docstring.

Unweighted network backbone methods.

These methods sparsify unweighted graphs by scoring edges and filtering based on local topology.

Methods#

sparsify: Generic sparsification framework (score -> normalize -> filter -> connect).
lspar: Local Sparsification (Satuluri et al. 2011) – Jaccard-based.
local_degree: Local Degree (Lindner et al. 2015) – keep edges to high-degree neighbors.

nx_backbone.sparsify(G, escore='jaccard', normalize='rank', filter='degree', s=0.5, umst=False, seed=None)[source]#

Sparsify an unweighted graph using a score-normalize-filter pipeline.

Follows the four-step pipeline from Neal (2022) [1]:

Score: every node u scores each of its incident edges (u, v). Some scores are symmetric (Jaccard, triangles, quadrangles, random); "degree" is asymmetric: u scores the edge by the degree of the neighbor v.
Normalize: optionally rank-transform the scores within each node’s neighborhood.
Filter: retain the top max(1, ceil(d_u**s)) edges of every node u (filter="degree"), or every edge whose score is at least s (filter="threshold"). An edge is kept if either endpoint retains it.
Connect: optionally add the union of all minimum spanning trees (UMST) of the scored graph [2], so the backbone has as many connected components as G.

Parameters:

Ggraph: An undirected NetworkX graph. Edge attributes are ignored.
escorestring, optional (default=”jaccard”): Edge scoring method. One of "jaccard" (Jaccard similarity of the endpoint neighborhoods), "degree" (degree of the neighbor), "triangles" (number of common neighbors), "quadrangles" (number of 4-cycles through the edge) or "random" (uniform random score in [0, 1)).
normalize{“rank”, None}, optional (default=”rank”): "rank" replaces each node’s view of an edge score by its normalized rank among that node’s edges, r / d_u, where r is the number of the node’s edges scoring less than or equal to the edge (so the best edge has value 1 and tied edges share a value). None keeps the raw scores. With filter="degree" both choices give the same backbone because ranking is monotone.
filter{“degree”, “threshold”}, optional (default=”degree”): Filtering method (see Notes).
sfloat, optional (default=0.5): Sparsification parameter: the exponent for filter="degree" (typically in [0, 1]; 0 is sparsest, 1 keeps every edge) or the score threshold for filter="threshold".
umstbool, optional (default=False): If True, also retain every edge that belongs to some minimum spanning tree (forest, if G is disconnected) of G weighted by the edge scores, with the most important edges cheapest (see Notes). The backbone then has the same connected components as G.
seedinteger, random_state, or None (default): Indicator of random number generation state, used only when escore="random". See Randomness.

Returns:

Hgraph: A copy of G with edge attributes "sparsify_score" (float, see Notes) and boolean "sparsify_keep".

Raises:

ValueError: If escore, normalize or filter is not one of the documented values.
NetworkXNotImplemented: If G is directed or a multigraph. Collapse a multigraph first with multigraph_to_weighted().

Notes

Ranks are competition ranks: the rank of edge e at node u is 1 + #{edges of u scoring strictly better than e}, so tied edges share a rank and are retained or dropped together. Self-loops are ignored when scoring and ranking and are never retained; d_u is the number of distinct neighbors of u.

With filter="degree" node u keeps the edges whose rank r satisfies r <= max(1, ceil(d_u**s)), and "sparsify_score" is the critical exponent of the edge,

\[s^*(e) = \min_{u \in e} \frac{\log(r_u(e) - 1)}{\log d_u},\]

with \(s^* = -\infty\) for an edge that is top-ranked at one of its endpoints. The edge is retained exactly when s > s*, so threshold_filter(H, "sparsify_score", s2, mode="below") gives the backbone for any other exponent s2 without re-scoring. Smaller scores mean more important edges.

With filter="threshold", "sparsify_score" is the larger of the two endpoints’ (normalized) scores and the edge is retained when it is at least s.

With umst=True the spanning trees minimize the sum of "sparsify_score" for filter="degree" and maximize it for filter="threshold". Following Hamann et al. [2], the union of all such trees is added, not one arbitrary tree: an edge with score w is added exactly when its endpoints are not already connected by edges that are strictly more important than w. No tie is broken arbitrarily (on a cycle whose edges all score the same, every edge is added), so the result does not depend on node or edge order. The union is computed with a union-find structure in \(O(m \log m)\) time.

References

[1]

Neal, Z. P. (2022). backbone: An R package to extract network backbones. PLOS ONE, 17(5), e0269137.

[2] (1,2)

Hamann, M., Lindner, G., Meyerhenke, H., Staudt, C. L., & Wagner, D. (2016). Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining, 6(1), 22.

Examples

>>> import networkx as nx
>>> from nx_backbone import boolean_filter, sparsify
>>> G_weighted = nx.les_miserables_graph()
>>> G = nx.Graph()
>>> G.add_nodes_from(G_weighted.nodes(data=True))
>>> G.add_edges_from(G_weighted.edges())
>>> H = sparsify(G, s=0.5)
>>> backbone = boolean_filter(H, "sparsify_keep")
>>> backbone.number_of_edges() <= H.number_of_edges()
True

Computational complexity estimate is O(mn) time and O(n + m) space.

nx_backbone.lspar(G, s=0.5, *, convention='satuluri')[source]#

Compute the Local Sparsification (L-Spar) backbone.

Every node u ranks its incident edges by the Jaccard similarity of the endpoint neighborhoods and keeps its top ceil(d_u**s) edges; an edge is retained if either endpoint keeps it [1]. Equivalent to sparsify(G, escore="jaccard", normalize="rank", filter="degree", s=s).

Parameters:

Ggraph: An undirected NetworkX graph.
sfloat, optional (default=0.5): Sparsification exponent (0 = sparsest, 1 = keep all).
convention{“satuluri”, “r”}, optional (default=”satuluri”): "satuluri" uses the conventions described above. "r" reproduces R backbone_from_unweighted(model = "lspar") (R backbone 3.0.4), which keeps fewer edges; see Notes.

Returns:

Hgraph: A copy of G with "sparsify_score" (the critical exponent, see sparsify() and Notes) and boolean "sparsify_keep".

Raises:

ValueError: If convention is not "satuluri" or "r".
NetworkXNotImplemented: If G is directed or a multigraph.

Notes

Edges tied in Jaccard similarity at the cut-off are all retained (competition ranking), which makes the result independent of node order. threshold_filter(H, "sparsify_score", s2, mode="below") reproduces lspar(G, s=s2) for any exponent s2.

Comparison with R backbone. R backbone_from_unweighted(model = "lspar") uses different conventions and keeps fewer edges (30 versus 54 on the karate club at s = 0.3). It divides the common neighbors by \(|N(u) \cup N(v)| - 2\), excluding the endpoints, ranks with dense ranks, ignores edges in no triangle (Jaccard 0) both when ranking and when counting \(d_u\), and keeps ranks up to floor(d_u**s) with no minimum of one. Here the denominator is \(|N(u) \cup N(v)|\), ranks are competition ranks over all edges, and each node keeps max(1, ceil(d_u**s)) as in Satuluri et al. local_degree() matches R’s model = "degree" on the karate club.

convention="r" applies R’s conventions and reproduces R’s backbones exactly on the karate club and Les Misérables (tested at s = 0.3, 0.5 and 0.7). Node u then ranks only its \(d'_u\) edges with positive Jaccard similarity, and an edge of dense rank r is kept by u when r <= floor(d'_u**s), i.e. when s >= log(r) / log(d'_u). "sparsify_score" is this critical exponent, minimized over the two endpoints: -inf when the edge is the only positive edge of an endpoint, inf when its Jaccard similarity is 0. Up to floating-point rounding at exact boundaries, an edge is retained exactly when s >= sparsify_score. Isolated edges (whose endpoints have no other neighbors) have similarity 0 under both conventions.

References

[1]

Satuluri, V., Parthasarathy, S., & Ruan, Y. (2011). Local graph sparsification for scalable clustering. ACM SIGMOD, 721-732.

Examples

>>> import networkx as nx
>>> from nx_backbone import boolean_filter, lspar
>>> G_weighted = nx.les_miserables_graph()
>>> G = nx.Graph()
>>> G.add_nodes_from(G_weighted.nodes(data=True))
>>> G.add_edges_from(G_weighted.edges())
>>> H = lspar(G, s=0.5)
>>> backbone = boolean_filter(H, "sparsify_keep")
>>> backbone.number_of_edges() <= H.number_of_edges()
True

R’s conventions keep fewer edges:

>>> K = nx.karate_club_graph()
>>> U = nx.Graph(K.edges())  # drop the weights
>>> [boolean_filter(lspar(U, s=0.3, convention=c), "sparsify_keep").number_of_edges()
...  for c in ("satuluri", "r")]
[54, 30]

Computational complexity estimate is O(mn) time and O(n + m) space.

nx_backbone.local_degree(G, s=0.3)[source]#

Compute the Local Degree backbone.

Every node u ranks its neighbors by their degree (highest first) and keeps the edges to its top floor(d_u**s) neighbors; an edge is retained if either endpoint keeps it [1], [2]. Edges to hubs are therefore preferred, which preserves the network’s hub structure.

Parameters:

Ggraph: An undirected NetworkX graph.
sfloat, optional (default=0.3): Sparsification exponent (0 = sparsest, 1 = keep all).

Returns:

Hgraph: A copy of G with "sparsify_score" and boolean "sparsify_keep".

Raises:

NetworkXNotImplemented: If G is directed or a multigraph.

Notes

Neighbors of equal degree share a rank (competition ranking), so ties at the cut-off are all retained. Each node always keeps at least its top-ranked edge(s). "sparsify_score" is the critical exponent

\[s^*(e) = \min_{u \in e} \frac{\log r_u(e)}{\log d_u}\]

(\(-\infty\) for edges top-ranked at an endpoint), and the edge is retained exactly when s >= s*. Smaller scores mean more important edges.

References

[1]

Lindner, G., Staudt, C. L., Hamann, M., Meyerhenke, H., & Wagner, D. (2015). Structure-preserving sparsification of social networks. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 448-454.

[2]

Hamann, M., Lindner, G., Meyerhenke, H., Staudt, C. L., & Wagner, D. (2016). Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining, 6(1), 22.

Examples

>>> import networkx as nx
>>> from nx_backbone import boolean_filter, local_degree
>>> G = nx.star_graph(4)
>>> G.add_edges_from([(4, 5), (4, 6)])
>>> H = local_degree(G, s=0.0)
>>> sorted(e for e in H.edges() if H.edges[e]["sparsify_keep"])
[(0, 1), (0, 2), (0, 3), (0, 4), (4, 5), (4, 6)]
>>> H[0][4]["sparsify_keep"]  # the hub keeps the edge to its best-connected neighbor
True