PaperlayerView exact revision on arXiv

Source-linked AI summary

Topological data analysis of contagion maps for examining spreading processes on networks

Dane Taylor, Florian Klimm, Heather A. Harrington, Miroslav Kramar, Konstantin Mischaikow, Mason A. Porter, Peter J. Mucha

arXiv:1408.1168v3nlin.AOcs.SImath.DSphysics.soc-ph

TL;DR

On networks that combine nearby and long-range connections, it matters whether contagion spread follows the underlying geometry. The paper analyzes Watts threshold contagions through node maps and finds that their point clouds can reveal manifold structure and contagion dynamics.

  • Problem

    On networks mixing nearby and long-range connections, it remains important to determine when contagion spread follows the underlying geometry.

    Source: §2 · p. 13

  • Method

    The authors use Watts threshold contagions to construct node maps, then analyze point-cloud manifold structure using ρ, P, and ∆.

    Source: §1.2 · p. 5, §7 · p. 51

  • Results

    For certain contagion parameters, map point clouds reveal network manifold structure and help quantify whether WFP or ANC dominates.

    Source: §7 · p. 51

  • Takeaways & Limitations

    Contagion maps offer a way to study spreading dynamics and identify manifold structure in networks.

    Source: §2 · p. 13

    Constructing maps with all cluster-seeded initial conditions typically costs O(NM), motivating work to improve computational efficiency.

    Source: Dimension Reduction of Networks · p. 71

Abstract

from arXiv · show

Social and biological contagions are influenced by the spatial embeddedness of networks. Historically, many epidemics spread as a wave across part of the Earth's surface; however, in modern contagions long-range edges -- for example, due to airline transportation or communication media -- allow clusters of a contagion to appear in distant locations. Here we study the spread of contagions on networks through a methodology grounded in topological data analysis and nonlinear dimension reduction. We construct "contagion maps" that use multiple contagions on a network to map the nodes as a point cloud. By analyzing the topology, geometry, and dimensionality of manifold structure in such point clouds, we reveal insights to aid in the modeling, forecast, and control of spreading processes. Our approach highlights contagion maps also as a viable tool for inferring low-dimensional structure in networks.

1 Results

This section examines how WTM contagion maps relate spreading dynamics to network structure, introducing the network, contagion, and mapping setup and analyzing noisy rings and London’s transit network. It considers how WFP and ANC regimes, infinite activation times, and network heterogeneity shape geographic agreement, contagion behavior, and map geometry.

1.1 Noisy Geometric Networks

  • Noisy geometric networks combine edges between nearby nodes on an embedded manifold with randomly placed non-geometric edges.The network construction distinguishes geometric connections, based on distance along the manifold, from non-geometric connections between otherwise unconnected node pairs.Source: §1.1 · p. 4

1.2 Watts Threshold Model (WTM)

  • WTM contagions use node-specific thresholds and irreversible synchronous adoption, producing monotonic network filtrations for topological analysis.The model represents social reinforcement and yields filtrations that support the paper’s computational-topology methodology.Source: §1.2 · p. 5

1.3 Contagion Maps

  • WTM maps place nodes in a point cloud using their activation times across contagion realizations, and symmetric maps induce a metric on the node set.Cluster seeding can increase the range of thresholds with finite activation times, although these maps do not automatically induce a metric.Source: §1.3 · pp. 5, 7

1.4 WTM Contagions on Noisy Ring Lattices

  • On noisy rings, bifurcation regimes distinguish wavefront propagation from new cluster formation; increasing the threshold slows WFP and makes ANC less frequent.For the studied regimes, low thresholds can rapidly saturate the network through new clusters, moderate thresholds yield slower WFP, and high thresholds can prevent either form of spread.Source: §1.4 · pp. 7–9, Figure 4 · p. 8

1.5 Analyzing WTM Maps for Noisy Ring Lattices

  • In the WFP-without-ANC regime, WTM maps recover ring geometry, dimension, and topology; across large parameter regimes, they reveal the ring more clearly than shortest-path or diffusion-based maps.For the ring regime, ρ ≈1, P ≈2, and Δ is large; WTM maps’ advantage over shortest-path and diffusion maps is reported for generalized noisy-ring networks.Source: §1.5 · pp. 9–11, Figure 6 · p. 11

1.6 Contagions on a London Transit Network

  • London’s transit network exhibits both WFP and ANC, and their threshold sensitivity is reflected in WTM-map geometry; the analysis omits one-dimensional homology because of its computational cost.The network represents intersections as nodes, roads as geometric edges, and metropolitan lines as non-geometric edges.Source: §1.6 · pp. 11–12, Figure 7 · p. 12
  • In Fig. 7(d), ignoring infinite activation times (“part”) yields a range of T with higher ρ and better geographic agreement, whereas retaining them (“full”) lowers ρ for T ≳ 0.1.The improvement is characteristic of increased WFP versus ANC.Source: §1.6 · p. 12
  • London’s heterogeneity and mean degree ≈2.59 make WFP and ANC highly sensitive to T for only a few seeds, yet those minority cases significantly affect WTM maps.The synthetic networks studied are homogeneous or only slightly heterogeneous, so WFP and ANC tend to behave similarly across starting locations; London contagions vary by starting region.Source: §1.6 · pp. 12–13
  • London’s low degrees and heterogeneity make contagion behavior vary by starting region and require multiple strategies for handling infinite activation times.These complexities complement the synthetic-network investigation.Source: §1.6 · p. 13
  • In an egocentric analysis, local WTM-map geometry at a node relates strongly to its proximity to a metro line.This analysis examines individual nodes rather than averaging results over the network.Source: §1.6 · p. 13

2 Discussion

The paper presents WTM contagion maps as tools for studying spreading dynamics and inferring low-dimensional network structure. Its analyses distinguish wavefront propagation from new-cluster formation and specify how geometry, dimensionality, topology, and infinite activation times are examined.

2 Discussion

  • WTM maps recover an underlying manifold’s topology, geometry, and dimensionality when contagions predominantly spread by wavefront propagation, and can also help identify manifold structure in networks.The authors also describe applications to contagion analysis, modeling, and control, and to other dynamics that construct network filtrations.Source: §2 · p. 13

3.1 Data and Code Availability

  • The authors provide the London transit network and code used to construct WTM maps as supplementary files.Source: §3.1 · p. 14

3.2 Bifurcation Analysis

  • The bifurcation analysis contrasts wavefront propagation along geometric edges with new-cluster formation through non-geometric edges; its WFP speed result applies most directly early in large networks.The WFP analysis assumes boundary nodes have no infected non-geometric neighbors; the authors state this assumption holds with high probability when contagion size is much smaller than network size. With small heterogeneity, regime boundaries thicken rather than transitions occurring simultaneously at every node.Source: §3.2 · pp. 14–15
  • For ANC, possible adoption thresholds reflect how many infected non-geometric neighbors a boundary-excluded node can have.The corresponding probability estimate assumes non-geometric edges are generated uniformly at random.Source: §3.2 · p. 14

3.3 Activation Times of Infinity in WTM Maps

  • Infinite activation times complicate distances between mapped nodes, so the paper either replaces them with 2N or excludes contagions with infinite times from the map.The authors note, but do not explore, mapping an unbounded metric space into a topologically equivalent bounded one.Source: §3.3 · p. 16

3.4 Geometry of WTM Maps

  • WTM-map geometry is assessed by correlating node-to-node distances in the map with distances between intrinsic node locations.The correlation is computed over unordered node pairs and compared across ambient dimensions.Source: §3.4 · p. 16

3.5 Dimensionality of WTM Maps

  • The embedding dimension is the smallest PCA projection dimension whose residual variance is below 0.05.Residual variance is defined as 1 − (ρ(p))^2, where ρ(p) measures geometric similarity to the unprojected map.Source: §3.5 · p. 16

3.6 Topology of WTM Maps

  • The topology analysis uses persistent homology of a Vietoris–Rips filtration to assess ring structure in WTM-map point clouds.It records the difference between the two largest 1-cycle lifetimes, normalized by point-cloud diameter.Source: §3.6 · pp. 16–17

5 Author Contributions

All authors designed the research and wrote the text; the authors report no competing financial interests.

5 Author Contributions

  • All authors designed the research and wrote the text; DT and FK developed the analytical results and conducted the numerical experiments.Source: §5 · p. 21

6 Financial Interest Statement

  • The authors declare no competing financial interests.Source: §6 · p. 21

1 Supplementary Note 1: Complex Contagions on a London Transit Network

The London transit study uses WTM contagions to examine spreading on a network combining roads and metro links. Its maps’ agreement with geographic location varies with threshold and with how infinite activation times are treated, while nodes’ contagion roles relate to their isolation and proximity to metro stations.

1 Supplementary Note 1: Complex Contagions on a London Transit Network

  • WTM maps are proposed for studying wavefront propagation versus new-cluster formation and for inferring potentially unknown low-dimensional structure in empirical networks.Source: §1 · p. 23

Description of the London Transit Network

  • The London network combines 2,854 road-based geometric edges with 15 metro-based non-geometric edges across 2,217 nodes, including 11 nodes representing both intersections and stations.The metro lines are drawn from the portion within the road network’s convex hull.Source: Figure 1 · p. 23, Description of the London Transit… · p. 24
  • For a Bond Street-centered seed, low threshold T=0.02 allows spread over roads and metro lines, whereas T=0.18 produces road-based wavefront propagation without metro-line spread.These threshold-sensitive cases are described as uncommon but influential for the resulting maps.Source: Description of the London Transit… · p. 25

Numerical Results for the Geometry of WTM Maps

  • As T rises, nodes shift from class (1) toward class (4); classes (2) and (3) are sparse around T ∈ (0.2, 0.25), and class (4) dominates above roughly 0.35.The classes distinguish nodes by their ability to initiate large contagions and to adopt contagions; the paper uses N/2 as the large/small cutoff.Source: Numerical Results for the Geometry of… · pp. 26–27
  • Ignoring infinite activation times yields higher agreement with geographic locations for WTM maps at approximately T ∈ (0.1, 0.2) than at other thresholds.Setting infinite times to 2N instead produces lower correlations for T ≳ 0.1 than for T ≲ 0.1, distorting the map from the known spatial embedding.Source: Numerical Results for the Geometry of… · pp. 26–27
  • Nodes that are not reached by seeded contagions tend to be relatively isolated, while inability to seed large contagions relates to both local and global network properties.Class (2) nodes are often two or three edges from a metro station or isolated; class (3) nodes are relatively isolated.Source: Numerical Results for the Geometry of… · pp. 27–29

“Egocentric” Analysis of Geometry

The study examines London-network contagions through node-level geometry, summarizes threshold-dependent findings, and tests whether WTM-map edge lengths can identify non-geometric links. The denoising results show that edge classification can remain predictive even when map geometry disagrees with geographic geometry.

“Egocentric” Analysis of Geometry

  • Egocentric correlation compares distances from each node in the intrinsic locations with distances from that node in a WTM-map point cloud.For thresholds 0.1 and 0.18, correlations typically rise at the higher threshold, but the increase is heterogeneous and has a heavy-tailed distribution.Source: “Egocentric” Analysis of Geometry · pp. 29–30

Summary of Experiments with the London Transit Network

  • On the London transit network, WFP and ANC both occur, and propagation depends on threshold; map geometry agrees better with intrinsic locations around T ∈ (0.1, 0.2).Ignoring infinite activation times was more useful for this network than setting them to 2N.Source: Summary of Experiments with the London… · pp. 30–31

2 Supplementary Note 2: Denoising Networks with WTM Maps

  • Denoising classifies edges by their WTM-map lengths, on the expectation that non-geometric edges are longer than geometric ones, and compares performance with a local Jaccard-index approach.The WTM-map procedure is global, using the entire network, unlike the local subgraph-statistics method.Source: §2 · p. 32

Denoising the London Transit Network

  • For London, WTM-map denoising outperforms the Jaccard-index approach for T ≳ 0.1, and remains predictive of edge type even when map geometry diverges from the network’s geographic geometry.Performance depends strongly on T; at T=0.1 it is poor and similar to Jaccard-index performance.Source: Denoising the London Transit Network · pp. 32–33, Figure 6 · p. 33

Denoising Noisy Two-Dimensional Square Lattices

WTM maps can identify noisy edges in geometric networks, with performance depending on network structure and geometric-edge stochasticity. The experiments also extend the noisy ring lattice to networks with heterogeneous degrees or node locations.

Denoising Noisy Two-Dimensional Square Lattices

  • The square-lattice experiment uses a periodic 2D lattice with 4 geometric edges per node and 2 randomly added non-geometric edges per node on average.The experiment motivates testing local methods based on 3-cycles because road networks can instead contain structures such as 4-cycles.Source: Denoising Noisy Two-Dimensional Square… · p. 33
  • On noisy 2D square lattices, the WTM map with T = 0.3 almost reaches AUC 1, while the Jaccard-index approach has AUC approximately 0.5.The Jaccard result is comparable to random guessing in this scenario.Source: Denoising Noisy Two-Dimensional Square… · p. 34

Denoising Noisy Ring Lattices with Removal of Geometric Edges

  • As geometric-edge stochasticity increases, inference accuracy generally decreases, and WTM maps can outperform or underperform the Jaccard index depending on T and network parameters.In the highest-stochasticity example, T = 0.2 gives the best ROC curve.Source: Figure 7 · p. 34, Denoising Noisy Ring Lattices with… · p. 35

Summary of Experiments for Denoising Networks

  • WTM maps can be advantageous when geometric networks lack enough 3-cycles, while WTM and Jaccard performance is similar when 3-cycles are prevalent.For noisy ring lattices with stochastic geometric edges, the relative AUC depends on T.Source: Summary of Experiments for Denoising… · p. 35

Families of Noisy Geometric Networks on a Ring Manifold

  • The four noisy ring-network families vary node-location, geometric-degree, and non-geometric-degree heterogeneity while keeping mean degrees at 4 and 2, respectively.They include evenly spaced nodes with constant degrees as well as variants with heterogeneous degrees or sampled node locations.Source: Families of Noisy Geometric Networks… · pp. 36–37

Perturbed Bifurcation Results

Degree heterogeneity makes WTM contagion thresholds node-specific, but the four qualitative regimes persist when heterogeneity is small relative to mean degrees. Their boundaries then vary across nodes, and the family (a) analysis is only approximate for sufficiently small heterogeneity.

Perturbed Bifurcation Results

  • With heterogeneous degrees, node-specific critical thresholds can produce different WFP and ANC dynamics among nodes in the same network.Some nodes may support WFP without ANC while others support both.Source: Perturbed Bifurcation Results · p. 38
  • The family (a) bifurcation analysis approximates families (b)–(d) when degree heterogeneities are sufficiently small compared with the mean degrees.The approximation is expected to improve as mean degrees grow relative to heterogeneity.Source: Perturbed Bifurcation Results · p. 39
  • The plotted Supplementary Figure 9 thresholds cover nodes with |δ(G)_i| ≤ 2, so the boundary interpretation does not account for the full node-degree distribution.The approximation is limited when geometric or non-geometric degree heterogeneity is not small relative to its mean.Source: Perturbed Bifurcation Results · p. 39
  • With sufficiently small degree perturbations relative to mean degrees, the four WFP/ANC regimes persist, but their boundaries occur at different parameter values across nodes.For fixed perturbations, the perturbed curves approach the zero-heterogeneity curves as mean degrees increase.Source: Perturbed Bifurcation Results · pp. 38, 40

4 Supplementary Note 4: A Set of Filtrations Defines a Metric

The paper proves a general route from filtrations to metrics and applies it to WTM contagions. For a connected network with finite activation times, the WTM activation times induce a metric on the node set.

4 Supplementary Note 4: A Set of Filtrations Defines a Metric

  • A complete and consistent set of filtrations on a finite node set induces a metric.The argument generalizes beyond the specific WTM contagion setting.Source: §4 · p. 41
  • WTM contagion realizations from each node as seed satisfy the completeness and consistency conditions used in the general result.The paper assumes activation times are finite for every node pair.Source: §4 · p. 41
  • Consequently, WTM activation times define a metric on the node set.Source: §4 · p. 41

Complete and Consistent Filtrations

The section defines conditions on nested node sets and establishes that they induce a metric. WTM contagions meet those conditions when seeded separately at every node and have finite activation times.

Complete and Consistent Filtrations

Filtration-Induced Metrics

  • Complete and consistent filtrations induce a metric; WTM realizations seeded at each node provide such filtrations when activation times are finite.The proof uses monotone contagion updates: a larger infected set cannot reduce a node's infected-neighbor fraction.Source: Filtration-Induced Metrics · pp. 42–43

5 Supplementary Note 5: Algorithm for Constructing WTM Maps

The algorithm constructs a WTM map by running a contagion from each node-centered cluster seed until equilibrium. Its typical cost is O(N²d), although a pathological general-WTM case can reach O(N³).

Algorithm and Computational Complexity

Numerical Investigation of Computational Cost

Computational experiments show that WTM-map construction scales approximately quadratically with network size and linearly with node degree. Additional analysis relates runtime and ANC behavior to contagion thresholds.

Numerical Investigation of Computational Cost

  • Runtime scales approximately quadratically with N and linearly with degree d; at N = 2000 it is much smaller for α ≥ 1/2 than for α < 1/2.The size-scaling fits use thresholds T = 0.05, 0.2, 0.35, and 0.45; the degree experiment fixes T = 0.35.Source: Numerical Investigation of… · p. 45, Figure 10 · p. 46
  • Near T(WFP) ≈ 0.4167, runtime drops sharply; for T ≤ 0.4, it increases with T, with sharp jumps aligned to contagion bifurcations.For T just above 0.4167, the contagion spreads to few or no additional nodes and reaches equilibrium quickly.Source: Numerical Investigation of… · p. 46

Appearance of New Contagion Clusters (ANC)

  • The ANC analysis finds that the rate of appearance of new clusters increases as the contagion threshold T decreases.For T ≥ T(ANC)0, contagion cannot spread exclusively via non-geometric edges.Source: Appearance of New Contagion Clusters… · p. 48
  • The ANC-only estimate g(t) ignores geometric-edge spreading and is a lower bound on contagion size q(t) in the regime with ANC but no WFP.The estimate averages over noisy-ring-lattice ensembles.Source: Appearance of New Contagion Clusters… · p. 49

Wavefront Propagation (WFP)

The WFP analysis bounds contagion growth along a noisy ring lattice under an assumption about boundary nodes’ non-geometric edges. The extended point-cloud analysis uses geometry, dimensionality, and topology measures to examine network manifold structure and contagion dynamics.

Wavefront Propagation (WFP)

  • For large networks early in a contagion, the WFP assumption is likely valid; as contagion size approaches N, its invalidation can accelerate propagation.WFP speed increases over time up to d(G)/2 nodes per time step; the assumed-case growth h(t) is a lower bound.Source: Wavefront Propagation (WFP) · p. 50

7 Supplementary Note 7: Extended Discussion of Point-Cloud Analyses

  • The point-cloud analysis uses Pearson correlation ρ, embedding dimension P, and the lifetime difference ∆ between the two most persistent 1-cycles to assess geometry, dimensionality, and topology.For certain WTM parameters, these measures quantify manifold structure and can also indicate whether WFP or ANC dominates.Source: §7 · p. 51

Analysis of Geometry

  • Geometry analysis compares distances in a WTM point cloud with distances in the network’s original embedding using Pearson correlation across node pairs.The correlation is computed over all N(N − 1)/2 distinct unordered pairs.Source: Analysis of Geometry · pp. 51–52
  • That distance correlation requires finite activation times for every node and contagion realization, which fails when some nodes never activate.At sufficiently large T, activation times can be infinite for nodes outside the seed.Source: Analysis of Geometry · p. 52

Analysis of Dimensionality

The section assesses WTM point clouds using PCA-based residual variance and multiscale 1-cycle persistence, then tests how their geometry tracks an underlying ring across network conditions.

Analysis of Dimensionality

  • Embedding dimension is estimated as the smallest PCA projection dimension with residual variance below 0.05, with dimensions capped at 20 to limit computational cost.Source: Analysis of Dimensionality · p. 52

Analysis of Topology

  • The analysis uses Vietoris-Rips persistence to track 1-cycles across scales and summarizes ring evidence by Δ = l1 − l2, the gap between the two longest lifetimes.A large Δ indicates a single dominant 1-cycle and supports a ring-manifold interpretation.Source: Analysis of Topology · pp. 54–55

8 Supplementary Note 8: Complex Contagions on a Ring Manifold

  • For some thresholds, WTM maps reveal ring geometry, dimensionality, and topology more clearly than Laplacian eigenmaps or Isomap; at other thresholds, the manifold is less apparent.Source: §8 · p. 57

Numerical Results for Geometry

  • The geometry correlation ρ drops abruptly near the WFP threshold, changes little across the ANC threshold, and tracks WFP less closely as degree heterogeneity increases.The reported agreement between the WFP threshold and the observed shifts in ρ decreases as node degrees become more heterogeneous.Source: Numerical Results for Geometry · p. 58
  • Network heterogeneity shifts the WFP-associated threshold to smaller T, but qualitative behavior in the (T, α) plane remains similar across all four network families.Source: Numerical Results for Geometry · p. 58
  • Increasing mean degree raises ρ across mapping methods and smooths WTM's dependence on T; in heterogeneous low-degree networks, the abrupt drop can shift to smaller T.For mean degrees (6, 2), the drop shifts from T = 0.375 in family (a) to approximately T ≈ 0.29 in families (b)–(d).Source: Numerical Results for Geometry · pp. 58, 60
  • As N grows, WTM ρ falls when WFP is not dominant but remains above 0.85 in the WFP regime; Laplacian eigenmaps and Isomap decline with N.Source: Numerical Results for Geometry · pp. 58, 59, 61

Numerical Results for Dimensionality

The symmetric WTM maps produce low-dimensional point clouds in the predicted wavefront-propagation-without-appearance-of-new-clusters regime. Their embedding dimension rises away from that regime, while shortest-path maps yield much higher dimensions in these experiments.

Numerical Results for Dimensionality

Numerical Results for Topology

The normalized difference between the two largest 1-cycle lifetimes provides evidence of ring topology in WTM-map point clouds. That evidence is strongest in the predicted WFP-without-ANC regime and weakens as network heterogeneity increases.

Numerical Results for Topology

  • The topology measure ∆ subtracts the second-largest 1-cycle lifetime from the largest, with lifetimes measured across spatial scales using a Vietoris-Rips filtration.The difference is normalized to [0, 1].Source: Numerical Results for Topology · p. 65
  • Across all four network families, ∆ is largest in the predicted WFP-without-ANC regime, with values above 0.9 in part of the parameter plane for family (a) but below 0.6 in family (d).The comparison indicates weaker ring-topology identifiability with greater degree heterogeneity.Source: Numerical Results for Topology · p. 65, Figure 19 · p. 66
  • At α = 1/3, ∆ generally decreases as heterogeneity increases, with much smaller values in families (c) and (d) than in (a) and (b) in the WFP-without-ANC regime.The effect of mean degree on ∆ is not simple across network families.Source: Numerical Results for Topology · p. 65, Figure 20 · p. 67
  • For Isomap, ∆ ≈ 0 in all cases, while the higher-degree setting (24, 8) yields smaller ∆ values than (12, 4) in one experiment.The authors note that the degree comparison may reflect the relatively small difference between mean degrees and network size N = 200.Source: Numerical Results for Topology · p. 65
  • Increasing heterogeneity weakens ring-topology evidence, and in families (c) and (d), ∆ ≈ 0 at small mean degrees across thresholds.For the same parameter range, family (d) has smaller ∆ than families (b) and (c), which are smaller than family (a).Source: Numerical Results for Topology · pp. 66–67

Non-Uniform Sampling of a Ring Manifold

Varying the heterogeneity of node spacing along the ring changes the geometry, dimensionality, and topology of symmetric WTM-map point clouds. Greater spacing heterogeneity generally makes the underlying ring manifold harder to recover.

Non-Uniform Sampling of a Ring Manifold

  • The parameter s tunes heterogeneity in node spacing and therefore in geometric degrees; s → ∞ corresponds to uniformly random locations on the unit circle.The experiments consider both identical and heterogeneous non-geometric degrees.Source: Non-Uniform Sampling of a Ring Manifold · p. 68
  • As s increases, the threshold range with P ≈ 2 narrows and shifts left, while the range with large ∆ also narrows and shifts left.For s = ∞, ∆ remains small across thresholds in one network family; in another, ∆ stays small for all s and T.Source: Non-Uniform Sampling of a Ring Manifold · p. 68
  • Increasing spacing heterogeneity decreases the maps’ ability to recover manifold properties, most clearly through drops in geometric correlation ρ and topology measure ∆.The experiments vary s while holding mean geometric degree at 8, with N = 200.Source: Non-Uniform Sampling of a Ring Manifold · pp. 68–69, Figure 21 · p. 69

Summary of Experiments with a Ring Manifold

On ring networks, contagion-map structure and the balance between wavefront propagation and new-cluster appearance vary with contagion thresholds and network parameters; bifurcation analysis predicts regimes with similar point-cloud structures. The discussion extends the approach to other spreading processes and dimension-reduction settings, while identifying computational efficiency as future work.

Summary of Experiments with a Ring Manifold

  • WTM-map structure and the balance between WFP and ANC depend strongly on contagion thresholds and network parameters, while bifurcation analysis predicts regimes with similar point-cloud structures.The approximation's accuracy generally increases with mean node degree but is sensitive to threshold, network size, and structural heterogeneity.Source: Summary of Experiments with a Ring… · p. 70

9 Supplementary Discussion

  • The supplementary discussion considers implications for three research areas that share an interest in understanding spreading processes on networks.These include network epidemiology, high-dimensional analysis of contagions and other dynamics, and dimension reduction.Source: §9 · p. 71

High-Dimensional Data Analysis of Contagions and Other Dynamics

  • WTM-map geometry, dimensionality, and topology depend sensitively on contagion parameters, unlike the parameter-insensitive node-to-node distances reported for a human-mobility contagion model.The authors attribute this sensitivity to thresholding and expect it to matter for complex contagions because of social reinforcement.Source: High-Dimensional Data Analysis of… · p. 71
  • Contagion maps can be constructed for other spreading and network processes that satisfy filtration conditions, including percolation, complex contagions, and some local community-detection methods.The authors identify computational homology as a promising approach for studying these settings.Source: High-Dimensional Data Analysis of… · p. 71

Dimension Reduction of Networks

  • WTM maps use adoption times across initial conditions to form a metric space, enabling simultaneous study of network topology, geometry, and dimensionality.The paper compares this global approach to network denoising with a local method based on subgraph statistics.Source: Dimension Reduction of Networks · p. 71
  • Constructing a WTM map with all possible initial conditions and clustering seeding typically has computational complexity O(NM), motivating work on faster methods.Network sampling and random projections are suggested as approximation approaches.Source: Dimension Reduction of Networks · p. 71

Dimension Reduction of Point-Cloud Data

  • WTM maps extend to point-cloud data after inferring a proximity network, and their robustness to noisy edges in WFP-dominated contagions motivates exploring noisy-data applications.The authors distinguish WTM maps, based on nonlinear nonconservative dynamics, from diffusion-based dimension reduction and note that the different dynamics can yield different results.Source: Dimension Reduction of Point-Cloud Data · p. 72
Loading 1408.1168v3…