On the reorderability of node-filtered order complexes
arXiv:1905.02330 · doi:10.1103/PhysRevE.101.052311
Abstract
Growing graphs describe a multitude of developing processes from maturing brains to expanding vocabularies to burgeoning public transit systems. Each of these growing processes likely adheres to proliferation rules that establish an effective order of node and connection emergence. When followed, such proliferation rules allow the system to properly develop along a predetermined trajectory. But rules are rarely followed. Here we ask what topological changes in the growing graph trajectories might occur after the specific but basic perturbation of permuting the node emergence order. Specifically we harness applied topological methods to determine which of six growing graph models exhibit topology that is robust to randomizing node order, termed global reorderability, and robust to temporally-local node swaps, termed local reorderability. We find that the six graph models fall upon a spectrum of both local and global reorderability, and furthermore we provide theoretical connections between robustness to node pair ordering and robustness to arbitrary node orderings. Finally we discuss real-world applications of reorderability analyses and suggest possibilities for designing reorderable networks.
arXiv comment41 pages, 16 figures
References in corpus (36)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Epidemic spreading in scale-free networks
- Hierarchical organization of modularity in metabolic networks
- The spread of epidemic disease on networks
- Identification of influential spreaders in complex networks
- Simplicial models of social contagion
- Synchronization reveals topological scales in complex networks
- A roadmap for the computation of persistent homology
- Statistical topological data analysis using persistence landscapes
- Clique topology reveals intrinsic geometric structure in neural correlations
- Topological strata of weighted complex networks
- Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
- Dynamic network drivers of seizure generation, propagation and termination in human epilepsy
- Spatial Growth of Real-world Networks
- Topology of biological networks and reliability of information processing
- Simplicial Activity Driven Model
- Random geometric complexes
- Emergent Hyperbolic Network Geometry
- Network geometry with flavor: from complexity to quantum geometry
- Topological analysis of the connectome of digital reconstructions of neural microcircuits
- Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks
- Emergent Complex Network Geometry
- Sparse exchangeable graphs and their limits via graphon processes
- Weighted Growing Simplicial Complexes
- Phase transition in the economically modeled growth of a cellular nervous system
- Neural development features: Spatio-temporal development of the Caenorhabditis elegans neuronal network
- Persistence paths and signature features in topological data analysis
- Totally Homogeneous Networks
- On the topology of random complexes built over stationary point processes
- Computing Multidimensional Persistence
- Edge exchangeable models for network data
- Resilience in Hierarchical Fluid Flow Networks
- The emergent integrated network structure of scientific research
- The landscape of NeuroImage-ing research
- Network structure of cascading neural systems predicts stimulus propagation and recovery