Converts a network matrix into a connected ring lattice whose
degree sequence exactly matches the original, while maximizing the average
local clustering coefficient. The resulting lattice is intended as a null
model for small-world network analyses. An adjacency matrix is derived
automatically from network (non-zero entries become edges), so the
function accepts any weighted or binary network directly.
Each pass randomly permutes the degree sequence onto ring positions, then
greedily assigns edges in strictly increasing ring-distance order (proximity
construction). Any residual degree deficit is resolved by a swap-repair
phase. Passes that yield a disconnected graph or an unsatisfied degree
sequence are discarded; among valid passes the one with the highest average
clustering coefficient is returned. shuffles independent passes are
attempted in total.
proxswap_lattice(network, weighted = FALSE, shuffles = 100)A square symmetric matrix of the same dimension as network,
with row and column names preserved, representing the resulting ring
lattice. When weighted = FALSE (default), entries are binary integers
(0L/1L); when weighted = TRUE, entries contain the
reassigned edge weights from network with original signs preserved.
The average clustering coefficient of the returned graph is attached as the
attribute "CC" and can be retrieved with attr(result, "CC").
When the empirical fallback is triggered (see Details), "CC" reflects
the empirical network's clustering coefficient rather than a lattice's.
Matrix.
A square, symmetric numeric matrix representing a network (e.g., partial
correlations). Non-zero off-diagonal entries are treated as edges; the
binary adjacency is derived internally as network != 0.
Isolated nodes (degree zero) are supported.
Logical (length = 1).
Whether to return a weighted ring lattice. When TRUE, the edge
weights from network are reassigned to the lattice edges according
to ring distance following the implementation of Muldoon, Bridgeford, &
Bassett (2016): shorter-distance lattice edges receive larger weights,
preserving the overall weight distribution while concentrating stronger
connections locally. When FALSE (default), a binary adjacency
matrix is returned.
Numeric (length = 1).
Number of independent random permutation passes to attempt. Each pass
assigns the observed degree sequence to ring positions in a new random
order, runs the proximity construction, and applies swap repair if needed.
Only passes producing a connected graph with zero degree error are
retained; the one with the highest clustering coefficient is returned.
Defaults to 100.
Alexander P. Christensen <alexpaulchristensen@gmail.com>
## Algorithm
Pair precomputation. A ring distance matrix is computed as \(d_{ij} = \min(|i - j|,\, n - |i - j|)\), giving true circular distances bounded by \(\lfloor n/2 \rfloor\). All unique unordered pairs at each distance \(r = 1, \ldots, \lfloor n/2 \rfloor\) are extracted once (retaining only entries where \(i < j\)) and cached for reuse across all passes.
Proximity construction. The observed degree sequence is randomly
permuted onto ring positions. Starting from an empty graph, edges are added
in distance order. At each distance band the eligible pairs (both endpoints
have remaining degree budget and are not yet connected) are sorted by
descending \(\min(\text{budget}_i, \text{budget}_j)\) so that high-need
pairs receive short connections first. Pairs are then assigned sequentially
with per-pair budget re-checks. The pass exits early once all budgets reach
zero. This phase is implemented in compiled C via proximity_pass_c.
Swap repair. If any degree deficit remains after the proximity
pass, the highest-deficit node \(i\) is connected to its nearest
available ring neighbour, scanning clockwise and counter-clockwise
positions in interleaved distance order. When no direct partner with
remaining budget exists, an edge swap is performed: a nearby unconnected
node \(j\) is found, one of \(j\)'s existing edges to \(k\) is
removed, and a new edge \((i, j)\) is added. Node \(k\) recovers its
budget for resolution in a subsequent iteration. This repeats until all
deficits are resolved or the iteration cap (\(2n^2\)) is reached. This
phase is implemented in compiled C via swapping_pass_c.
Weight assignment. When weighted = TRUE, edge weights are
reassigned after the binary topology is finalised. The observed weights are
sorted by absolute value in descending order (largest magnitude first)
and mapped onto lattice edges ranked by ascending ring distance (i.e.,
\(d_{ij} = \min(|i - j|,\, n - |i - j|)\)), so that shorter (more local)
connections receive the largest-magnitude weights. Original signs are
preserved: the sorted weight vector — not its absolute values — is assigned
to the lattice edges. This directly implements the distance-weight principle
of Muldoon, Bridgeford, & Bassett (2016), using the ring's structural
distances rather than any network-derived proxy. Ties in ring distance are
broken at random.
Pass selection. A pass is valid only if the resulting graph is connected and has zero residual degree error. Among valid passes, the one with the highest average clustering coefficient is returned.
Empirical fallback. If no valid pass is found, or if the best
lattice clustering coefficient is lower than that of the original network,
the empirical adjacency (or weighted matrix, if weighted = TRUE) is
returned with a warning.
Logic for weight assignments
Muldoon, S. F., Bridgeford, E. W., & Bassett, D. S. (2016).
Small-world propensity and weighted brain networks.
Scientific Reports, 6(1), 22057.
# Get network
network <- network_estimation(basic_smallworld)
# Construct binary ring lattice
L <- proxswap_lattice(network)
# Retrieve the attached clustering coefficient
attr(L, "CC")
# Degree sequences should match exactly
cbind(target = colSums(network != 0), achieved = colSums(L))
# Construct weighted ring lattice
L_weighted <- proxswap_lattice(network, weighted = TRUE)
# Retrieve the attached clustering coefficient
attr(L_weighted, "CC")
Run the code above in your browser using DataLab