Type:	Package
Title:	Extracts the Backbone from Networks
Version:	3.0.0
Description:	An implementation of methods for extracting a sparse unweighted network (i.e. a backbone) from an unweighted network (e.g., Hamann et al., 2016 <doi:10.1007/s13278-016-0332-2>), a weighted network (e.g., Serrano et al., 2009 <doi:10.1073/pnas.0808904106>), or a weighted projection (e.g., Neal et al., 2021 <doi:10.1038/s41598-021-03238-3>).
License:	GPL-3
Encoding:	UTF-8
RoxygenNote:	7.3.2
Depends:	R (≥ 3.5)
Imports:	igraph, Matrix, methods, stats, Rcpp, utils,
Suggests:	knitr, rmarkdown, tinytest
LinkingTo:	Rcpp
VignetteBuilder:	knitr
URL:	https://www.zacharyneal.com/backbone, https://github.com/zpneal/backbone
BugReports:	https://github.com/zpneal/backbone/issues
LazyData:	true
NeedsCompilation:	yes
Packaged:	2025-09-15 14:43:54 UTC; zacharyneal
Author:	Zachary Neal [aut, cre], Rachel Domagalski [ctb], Bruce Sagan [ctb], Karl Godard [ctb]
Maintainer:	Zachary Neal <zpneal@msu.edu>
Repository:	CRAN
Date/Publication:	2025-09-15 19:00:11 UTC

backbone: Extracts the Backbone from Graphs

Description

Provides methods for extracting an unweighted and sparse subgraph (i.e., a backbone) that contains only the most "important" edges from:

• a weighted network using backbone_from_weighted()

• a weighted projection of a bipartite network or hypergraph using backbone_from_projection()

• an unweighted network using backbone_from_unweighted()

For a detailed illustration of these methods, please see the vignette using vignette("backbone").

Author(s)

Maintainer: Zachary Neal zpneal@msu.edu (ORCID)

Other contributors:

• Rachel Domagalski [contributor]

• Bruce Sagan [contributor]

• Karl Godard [contributor]

References

package: Neal, Z. P. (2025). backbone: An R Package to Extract Network Backbones. CRAN. doi:10.32614/CRAN.package.backbone

See Also

Useful links:

• https://www.zacharyneal.com/backbone

• https://github.com/zpneal/backbone

• Report bugs at https://github.com/zpneal/backbone/issues

Extract the backbone from a weighted bipartite or hypgergraph projection

Description

backbone_from_projection() extracts the unweighted backbone from the weighted projection of a bipartite network or hypergraph

Usage

backbone_from_projection(
  B,
  alpha = 0.05,
  model = "sdsm",
  signed = FALSE,
  mtc = "none",
  missing_as_zero = FALSE,
  narrative = FALSE,
  trials = NULL,
  return = "backbone"
)

Arguments

Details

The backbone_from_projection function extracts the backbone from the weighted projection of a bipartite network or hypergraph. The backbone is an unweighted unipartite network of agents that contains only edges whose weights in the projection are statistically significant. When signed = FALSE, the backbone contains edges that are statistically significantly strong under a one-tailed test. When signed = TRUE, the backbone contains positive edges that are statistically significantly strong, and negative edges that are statistically significantly weak, under a two-tailed test.

The model parameter controls the null model used to evaluate the statistical significance of edge weights. All available models are statistical models that are controlled by alpha, and differ in the constraints they impose on B:

• sdsm (default) - The "Stochastic Degree Sequence Model" (SDSM; Neal et al., 2021) approximately constrains the agent and artifact degrees, and exactly constrains edges that are prohibited (weight = 10) or required (weight = 11; Neal & Neal, 2023)

• fdsm - The "Fixed Degree Sequence Model" (Neal et al., 2021) exactly constrains the agent and artifact degrees

• fixedfill - The "fixed fill" model (Neal et al., 2021) exactly constrains the total number of edges (i.e., sum)

• fixedrow - The "fixed row" model (Neal et al., 2021) exactly constrains the agent degrees (i.e., row sums)

• fixedcol - The "fixed column" model (Neal et al., 2021) exactly constrains the artifact degrees (i.e., column sums)

Although backbone_from_projection extracts the backbone from the weighted projection of a bipartite network or hypergraph, the input B must be the bipartite network or hypergraph itself, and not the weighted projection. This is necessary because these backbone models use information in the bipartite network that is missing from the projection. The "agent" nodes that appear in the projection must be represented by rows if B is an incidence matrix, or by type = FALSE nodes if B is a bipartite igraph object. In either case, the source network must be binary (i.e., unweighted), unless model = "sdsm", when "prohibited" edges can be represented with weight = 10 and "required" edges can be represented with weight = 11.

Value

If return = "backbone", a backbone in the same class as B. If return = "everything", then the backbone is returned as an element in a list that also includes the original network, raw projection, backbone, edgewise p-values, narrative description, and original function call.

References

package: Neal, Z. P. (2025). backbone: An R Package to Extract Network Backbones. CRAN. doi:10.32614/CRAN.package.backbone

sdsm-ec model: Neal, Z. P. and Neal, J. W. (2023). Stochastic Degree Sequence Model with Edge Constraints (SDSM-EC) for Backbone Extraction. International Conference on Complex Networks and Their Applications, 12, 127-136. doi:10.1007/978-3-031-53468-3_11

all other models: Neal, Z. P., Domagalski, R., and Sagan, B. (2021). Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections. Scientific Reports, 11, 23929. doi:10.1038/s41598-021-03238-3

Examples

#A binary bipartite network of 30 agents & 75 artifacts
#The agents form three communities
B <- rbind(cbind(matrix(rbinom(250,1,.8),10),
                 matrix(rbinom(250,1,.2),10),
                 matrix(rbinom(250,1,.2),10)),
           cbind(matrix(rbinom(250,1,.2),10),
                 matrix(rbinom(250,1,.8),10),
                 matrix(rbinom(250,1,.2),10)),
           cbind(matrix(rbinom(250,1,.2),10),
                 matrix(rbinom(250,1,.2),10),
                 matrix(rbinom(250,1,.8),10)))
B <- igraph::graph_from_biadjacency_matrix(B)

P <- igraph::bipartite_projection(B, which = "true")  #An ordinary weighted projection...
plot(P)                                               #...is a dense hairball

backbone <- backbone_from_projection(B)  #A backbone...
plot(backbone)                           #...is sparse with clear communities

Extract the backbone from an unweighted, undirected network

Description

backbone_from_unweighted() extracts the unweighted backbone from an unweighted, undirected network

Usage

backbone_from_unweighted(
  U,
  model = "lspar",
  parameter = 0.5,
  escore,
  normalize,
  filter,
  umst,
  narrative = FALSE,
  return = "backbone"
)

Arguments

Details

The backbone_from_unweighted function extracts the backbone from an unweighted unipartite network. The backbone is an unweighted unipartite network that contains only edges preserved by a backbone model.

The following backbone models are available using the model parameter:

• skeleton - Skeleton backbone (Karger, 1999)

• gspar - Global Sparsification (Satuluri et al., 2011)

• lspar - Local Sparsification (Satuluri et al., 2011)

• simmelian - Simmelian backbone (Nick et al., 2013)

• jaccard - Jaccard backbone (Goldberg and Roth, 2003)

• meetmin - MeetMin backbone (Goldberg and Roth, 2003)

• geometric - Geometric backbone (Goldberg and Roth, 2003)

• hyper - Hypergeometric backbone, (Goldberg and Roth, 2003)

• degree - Local Degree backbone (Hamann et al, 2016)

• quadrilateral - Quadrilateral Simmelian backbone (Nocaj et al, 2015)

• custom - A custom backbone model specified by escore, normalize, filter, and umst

The escore parameter determines how an unweighted edge's importance is calculated.

• random: a random number drawn from a uniform distribution

• betweenness: edge betweenness

• triangles: number of triangles that include the edge

• jaccard: jaccard similarity coefficient of the neighborhoods of an edge's endpoints, or alternatively, triangles normalized by the size of the union of the endpoints neighborhoods

• dice: dice similarity coefficient of the neighborhoods of an edge's endpoints

• quadrangles: number of quadrangles that include the edge

• quadrilateral: geometric mean normalization of quadrangles

• degree: degree of neighbor to which an edge is adjacent (asymmetric)

• meetmin: triangles normalized by the smaller of the endpoints' neighborhoods' sizes

• geometric: triangles normalized by the product of the endpoints' neighborhoods' sizes

• hypergeometric: probability of the edge being included at least as many triangles if edges were random, given the size of the endpoints' neighborhoods (inverted, so that larger is more important)

The normalize parameter determines whether edge scores are normalized.

• none: no normalization is performed

• rank: scores are normalized by neighborhood rank, such that the strongest edge in a node's neighborhood is ranked 1 (requires that filter = degree)

• embeddedness: scores are normalized using the maximum Jaccard coefficient of the top k-ranked neighbors of each endpoint, for all k

The filter parameter determines how edges are filtered based on their (normalized) edge scores.

• threshold: Edges with scores > parameter are retained in the backbone

• proportion: Specifies the approximate proportion of edges to retain in the backbone

• degree: Retains each node's d^parameter most important edges, where d is the node's degree (requires that normalize = "rank")

• disparity: Applies the disparity filter using backbone_from_weighted()

• lans: Applies locally adaptive network sparsification using backbone_from_weighted()

• mlf: Applies the marginal likelihood filter using backbone_from_weighted()

Value

If return = "backbone", a backbone in the same class as U. If return = "everything", then the backbone is returned as an element in a list that also includes the original unweighted network, a narrative description, and the original function call.

References

package: Neal, Z. P. (2025). backbone: An R Package to Extract Network Backbones. CRAN. doi:10.32614/CRAN.package.backbone

skeleton: Karger, D. R. (1999). Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24, 383-413. doi:10.1287/moor.24.2.383

gspar and lspar: Satuluri, V., Parthasarathy, S., & Ruan, Y. (2011, June). Local graph sparsification for scalable clustering. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (pp. 721-732). doi:10.1145/1989323.1989399

simmelian: Nick, B., Lee, C., Cunningham, P., & Brandes, U. (2013, August). Simmelian backbones: Amplifying hidden homophily in facebook networks. In Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining (pp. 525-532). doi:10.1145/2492517.2492569

jaccard, meetmin, geometric, hyper: Goldberg, D. S., & Roth, F. P. (2003). Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Sciences, 100, 4372-4376. doi:10.1073/pnas.0735871100

degree: 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, 22. doi:10.1007/s13278-016-0332-2

quadrilateral: Nocaj, A., Ortmann, M., & Brandes, U. (2015). Untangling the hairballs of multi-centered, small-world online social media networks. Journal of Graph Algorithms and Applications, 19, 595-618. doi:10.7155/jgaa.00370

Examples

#A dense, unweighted network with three embedded communities
U <- igraph::sample_sbm(60, matrix(c(.75,.25,.25,.25,.75,.25,.25,.25,.75),3,3), c(20,20,20))
plot(U)  #Communities are not obvious

#Extract backbone using the built-in "Local Sparsification" model
bb <- backbone_from_unweighted(U, model = "lspar", parameter = 0.5)
plot(bb)  #Communities are clearly visible

#Extract backbone using local sparification, but explicitly specifying the model steps
bb <- backbone_from_unweighted(U, model = "custom", escore = "jaccard",
                               normalize = "rank", filter = "degree",
                               umst = FALSE, parameter = 0.5)
plot(bb)  #Communities are clearly visible

Extract the backbone from a weighted network

Description

backbone_from_weighted() extracts the unweighted backbone from a weighted network

Usage

backbone_from_weighted(
  W,
  model = "disparity",
  alpha = 0.05,
  signed = FALSE,
  mtc = "none",
  parameter = 0,
  missing_as_zero = FALSE,
  narrative = FALSE,
  return = "backbone"
)

Arguments

Details

The backbone_from_weighted function extracts the backbone from a weighted unipartite network. The backbone is an unweighted unipartite network that contains only edges whose weights are statistically significant (based on alpha for statistical models), or which exhibit certain structural properties (based on parameter for structural models). For statistical models, when signed = FALSE, the backbone contains edges that are statistically significantly strong under a one-tailed test. When signed = TRUE, the backbone contains positive edges that are statistically significantly strong, and negative edges that are statistically significantly weak, under a two-tailed test.

The model parameter controls the model used to evaluate the edge weights. The available models include:

Statistical Models (controlled by alpha, signed, and mtc)

• disparity (default) - The disparity filter (Serrano et al., 2009)

• lans - Locally adaptive network sparsification (Foti et al., 2011)

• mlf - Marginal likelihood filter (Dianati, 2016)

Structural Models (controlled by parameter)

• global - parameter is a numeric vector of length 1 or 2. If length(parameter)==1, then edges with weights above parameter are preserved. If length(parameter)==2, then edges with weights above max(parameter) are preserved as positive, and edges with weights above min(parameter) are preserved as negative.

The models implemented in backbone_from_weighted() can be applied to a weighted network that was obtained by projecting a bipartite network or hypergraph. However, if the original bipartite network or hypergraph is available, it is better to use backbone_from_projection().

Value

If return = "backbone", a backbone in the same class as W. If return = "everything", then the backbone is returned as an element in a list that also includes the original weighted network, (for statistical backbone models) the edgewise p-values, a narrative description, and the original function call.

References

package: Neal, Z. P. (2025). backbone: An R Package to Extract Network Backbones. CRAN. doi:10.32614/CRAN.package.backbone

disparity: Serrano, M. A., Boguna, M., & Vespignani, A. (2009). Extracting the multiscale backbone of complex weighted networks. Proceedings of the National Academy of Sciences, 106, 6483-6488. doi:10.1073/pnas.0808904106

lans: Foti, N. J., Hughes, J. M., & Rockmore, D. N. (2011). Nonparametric sparsification of complex multiscale networks. PLOS One, 6, e16431. doi:10.1371/journal.pone.0016431

mlf: Dianati, N. (2016). Unwinding the hairball graph: Pruning algorithms for weighted complex networks. Physical Review E, 93, 012304. doi:10.1103/PhysRevE.93.012304

Examples

#A weighted network with heterogeneous (i.e. multiscale) weights
W <- matrix(c(0,10,10,10,10,75,0,0,0,0,
              10,0,1,1,1,0,0,0,0,0,
              10,1,0,1,1,0,0,0,0,0,
              10,1,1,0,1,0,0,0,0,0,
              10,1,1,1,0,0,0,0,0,0,
              75,0,0,0,0,0,100,100,100,100,
              0,0,0,0,0,100,0,10,10,10,
              0,0,0,0,0,100,10,0,10,10,
              0,0,0,0,0,100,10,10,0,10,
              0,0,0,0,0,100,10,10,10,0),10)

W <- igraph::graph_from_adjacency_matrix(W, mode = "undirected", weighted = TRUE)
plot(W, edge.width = sqrt(igraph::E(W)$weight)) #A stronger clique & a weaker clique

mean_weight <- mean(igraph::E(W)$weight)  #Find average edge weight
bb <- backbone_from_weighted(W, model = "global", #A backbone with stronger-than-average edges...
      parameter = mean_weight)
plot(bb) #...ignores the weaker clique

bb <- backbone_from_weighted(W, model = "disparity") #A disparity filter backbone...
plot(bb) #...preserves edges at multiple scales

Bipartite Configuration Model

Description

bicm estimates cell probabilities under the bipartite configuration model

Usage

bicm(M, fitness = FALSE, tol = 1e-08, max_steps = 200, ...)

Arguments

Details

Given a binary matrix M, the Bipartite Configuration Model (BiCM; Saracco et. al. 2015) returns a valued matrix B in which Bij is the approximate probability that Mij = 1 in the space of all binary matrices with the same row and column marginals as M. The BiCM yields the closest approximations of the true probabilities compared to other estimation methods (Neal et al., 2021), and is used to extract the backbone of a bipartite projection with the stochastic degree sequence model.

Matrix M is "conforming" if no rows and no columns contain only zeros or only ones. If M is conforming, then bicm() is faster. Additionally, if fitness = TRUE, then bicm() returns a list of row and column fitnesses, which requires less memory. Given the ith row's fitness Ri and the jth column's fitness Rj, the entry Bij in the probability matrix can be computed as Ri x Rj/(1+(Ri x Rj)).

Matrix M is "non-conforming" if any rows or any columns contain only zeros or only ones. If M is non-conforming, then bicm() is slower and will only return a probability matrix.

Value

a matrix of probabilities or a list of fitnesses

References

package: Neal, Z. P. (2025). backbone: An R Package to Extract Network Backbones. CRAN. doi:10.32614/CRAN.package.backbone

bicm: Saracco, F., Di Clemente, R., Gabrielli, A., & Squartini, T. (2015). Randomizing bipartite networks: The case of the World Trade Web. Scientific Reports, 5, 10595. doi:10.1038/srep10595

Examples

M <- matrix(c(0,0,1,0,1,0,1,0,1),3,3)  #A binary matrix
bicm(M)

Depricated function to extract disparity filter backbone

Description

disparity() was replaced by backbone_from_weighted(model = "disparity").

Usage

disparity(
  W,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Randomize a binary matrix using the fastball algorithm

Description

fastball randomizes a binary matrix, preserving the row and column sums

Usage

fastball(M, trades = 5 * nrow(M))

Arguments

Details

Given a matrix M, fastball randomly samples a new matrix from the space of all matrices with the same row and column sums as M.

Value

matrix: A random binary matrix with same row sums and column sums as M.

References

fastball: Godard, Karl and Neal, Zachary P. 2022. fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences. Journal of Complex Networks doi:10.1093/comnet/cnac049

Examples

M <- matrix(rbinom(200,1,0.5),10,20)  #A random 10x20 binary matrix
Mrand <- fastball(M)  #Random matrix with same row and column sums

Depricated function to extract Fixed Degree Sequence Model (FDSM) backbone

Description

fdsm() was replaced by backbone_from_projection(model = "fdsm").

Usage

fdsm(
  B,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE,
  trials = NULL
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract Fixed Column backbone

Description

fixedcol() was replaced by backbone_from_projection(model = "fixedcol").

Usage

fixedcol(
  B,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract Fixed Fill backbone

Description

fixedfill() was replaced by backbone_from_projection(model = "fixedfill").

Usage

fixedfill(
  B,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract Fixed Row backbone

Description

fixedrow() was replaced by backbone_from_projection(model = "fixedrow").

Usage

fixedrow(
  B,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract LANS backbone

Description

lans() was replaced by backbone_from_weighted(model = "lans").

Usage

lans(
  W,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract MLF backbone

Description

mlf() was replaced by backbone_from_weighted(model = "mlf").

Usage

mlf(
  W,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Depricated function to extract Stochastic Degree Sequence Model (SDSM) backbone

Description

sdsm() was replaced by backbone_from_projection(model="sdsm").

Usage

sdsm(
  B,
  alpha = 0.05,
  missing.as.zero = FALSE,
  signed = FALSE,
  mtc = "none",
  narrative = FALSE
)

Arguments

Details

See backbone v2.1.4 for original documentation

Bill Sponsorship in the 108th U.S. Senate

Description

A bipartite network describing bill sponsorship in the 108th U.S. Senate

Usage

senate108

Format

senate108

An igraph object containing a bipartite network with 100 senators and 3035 bills, where a senator is connected to a bill they sponsored or co-sponsored. Senator nodes include attributes for name, party affiliation, state, Govtrack ID, color (red for Republican, blue for Democrat, green for independent). Bill nodes include attributes for date introduced, title, legislative policy area, party affiliation of the sponsor, partisanship, and most recent status.

Source

These data were generated using incidentally::incidence.from.congress(session = 108, types = "s", format = "igraph")