CS Paper Radar

Structural Sign Herdability in Temporal Networks: A Sufficient Condition via $π_p$-Graphs

Pradeep M, Twinkle Tripathy

eess.SY ·submitted 2026-09-09 19:39 UTC · v2

Abstract

In this letter, we study the herdability of temporally switching directed networks. A temporal network is modeled as a switched system with a fixed switching sequence, which imposes more restrictive herdability conditions than those of conventional switched systems. By exploiting the relationship between temporal walks and the entries of the controllability matrix, we derive sufficient conditions for herdability. We further show that the magnitude of edge weights influences the sign pattern of the controllability matrix, thereby affecting herdability. Consequently, herdability in temporal networks depends not only on the network topology and switching durations, but also on the magnitude of the edge weights. Motivated by this observation, we establish equivalent graph-theoretic conditions for structural sign ($\mathcal{SS}$) herdability in temporal networks. In particular, we introduce the union multigraph of temporal subsystems and propose the notion of a $π$-graph. We show that the existence of a $π_p$-graph, which is a temporally evolving $π$-graph, is sufficient to guarantee $\mathcal{SS}$ herdability. Illustrative examples are provided to demonstrate the proposed results.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Discernibility of Topology Changes in Networked LTI Systems

eess.SY ·2026-10-23 ·Giulio Fattore, Maria Elena Valcher
similarity 0.64
Abstract · Submitted as an invited paper to the Bicentennial Special Issue of the Journal of the Franklin Institute. Under review

This article investigates the discernibility of topology changes in networked linear time-invariant systems, with particular focus on edge disconnection. We introduce a new notion of discernibility motivated by a limitation of the definition commonly adopted in the literature. In consensus networks, topology changes are inherently indiscernible for all initial conditions belonging to the synchronization subspace. To overcome this issue, we first introduce the notion of dynamical discernibility of a topology change for elementary consensus networks. This notion explicitly disregards the intrinsic indiscernibility associated with states in the consensus subspace. We characterize this property for directed communication graphs and then specialize the resulting conditions to topology changes arising from either the disconnection of an edge or a variation in its weight. We then extend the analysis to networks of homogeneous agents by introducing discernibility modulo synchronization, which factors out the unavoidable indiscernibility associated with synchronized trajectories. We derive a general characterization showing how discernibility depends jointly on the topology change and on the dynamics of the individual agents. Finally, we specialize the analysis to undirected communication graphs and show that, under mild additional assumptions, discernibility modulo synchronization is equivalent to the dynamical discernibility of the corresponding topology change. This establishes a direct connection between the two notions and extends existing results on the discernibility of topology variations in dynamical networks. The resulting characterizations are then further specialized to the case of edge disconnection.

0.20

Intervention problems in the Linear Threshold Model: A general formulation and new results

cs.GT math.OCcs.MAcs.SI+1 ·2026-09-15 ·Giacomo Como, Fabio Fagnani, Stephane Durand
similarity 0.59
Abstract

We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.

0.33

On the Limits of Stochastic Push-Pull over Time-Varying Digraphs

cs.LG math.OC ·2026-10-23 ·Feiming Wang, Yutong He, Sulaiman Alghunaim, Kun Yuan
similarity 0.59
Abstract · 33 pages, 3 figures

Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.

0.28

Flocking Time and Graph Volume in Nonlinear Cucker-Smale Models with Dynamic Networks

cs.LG math.DSnlin.AO ·2026-11-17 ·Sooyeon Song, Jea-Hyun Park
publishedtheory similarity 0.59
Abstract · 14 pages, 3 figures. Accepted manuscript of the article published in J. Inf. Commun. Converg. Eng. 24(2), 155-164 (2026)

This study proposes a Cucker-Smale model incorporating dynamic networks and the discrete $p$-Laplacian ($p \in (1,2)$) and analyzes the relationship between flocking time constraints and graph connectivity from both theoretical and experimental perspectives. We establish that this model achieves flocking within finite time and derive a quantitative relationship between the lower bound of flocking time and graph volume. Based on these results, we observe that imposing sufficiently small flocking time induces an increase in network volume, and that larger initial velocity variance requires greater volume under the same time constraint. In our experiments, we trained a transformer-based PPO policy to select network structures at each time step. Under the most stringent time constraint, the maximum average number of connections increased sharply, confirming a threshold effect. The negative correlation between convergence time and average number of connections reflects the theoretical results well. This study provides quantitative evidence for the phenomenon that time constraints induce connection mobilization.

0.40

Quiver Semistability and Structured Kalman Decompositions for Networked Linear Dynamical Systems

eess.SY math.OCmath.RT ·2026-08-30 ·Kazuo Murota, Tasuku Soma
similarity 0.57
Abstract

We introduce new notions of controllability and observability for networked linear time-invariant (LTI) systems based on $σ$-semistability of quiver representations. Utilizing King's criterion for $σ$-semistability, we define a network generalization of the Kalman decomposition for networked LTI systems, which systematically decomposes the local and interconnection dynamics while respecting the underlying network structure. Furthermore, we present efficient algorithms for deciding the proposed controllability and observability of a given networked LTI system and for finding the Kalman-type decomposition. We also show efficient algorithms for deciding the $σ$-semistability of representations of acyclic quivers with self-loops if the weight $σ$ has the same sign for all vertices with self-loops. Such quiver representations and weights arise from networked LTI systems.

0.25

Resource competition and survival for random walkers on complex networks

cs.SI physics.comp-phstat.AP ·2026-10-24 ·Snehal Shekatkar
similarity 0.57
Abstract · 4 pages, 4 figures

We consider the problem of $W$ random walkers on a complex network where each walker requires an amount $θ$ of resource at each time to survive. Resource is stochastically produced at each vertex of the network with a specified distribution. The survival time of the system of walkers is defined as the time required for all $W$ walkers to die. Using numerical simulations, we show that Erd{\H o}s-Rényi networks a have higher mean survival time than Scale-free networks as expected, but also that uniform distribution production leads to higher mean survival time than exponential distribution with the same mean. We derive an exact expression for the survival-time distribution under the assumption of independent walker lifespans, and use it to show that scale-free network topology produces strong dependence in the lifespans but homogeneous topology does not. We moreover demonstrate how the survival time can be substantially increased without changing the resource production or network topology by appropriately biasing the movement of the walkers towards low degree vertices on Scale-free networks, but has no effect on Erd{\H o}s-R{é}nyi networks.

0.27

On Real Eventual Exponential Positive property of complex-valued Laplacians and their pseudoinverses

eess.SY ·2026-11-07 ·Aditi Saxena, Twinkle Tripathy, Rajasekhar Anguluri
similarity 0.56
Abstract

The property of real eventual exponential positivity guarantees the state trajectories of a linear time-invariant system to evolve asymptotically to right half of the complex-plane [1]. It has applications in the characterization of herdability and reachability of states in networked systems. Networks with complex-valued edge-weights arise in AC power systems and opinion dynamics. Recent work has introduced real eventual exponential positive (rEEP) Laplacians, for which the trajectories of the associated network flow eventually converge to consensus. We establish further properties of rEEP Laplacians and their pseudoinverses. Firstly, we show that the rEEP property for complex-valued matrices exhibits invariance under specific rotational transformations. Secondly, we establish that the property of rEEP is preserved under the MoorePenrose pseudoinverse operation, highlighting its robustness under algebraic manipulations. These results apply to effective impedance computation in AC networks and to consensus in multi-agent systems. Finally, we provide numerical examples to validate our theoretical results.

0.27

Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs

cs.DS cs.DM ·2026-10-05 ·Daniele Carnevale
theory similarity 0.56
Abstract · 21 pages, 2 figures

A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time step wait or move along an edge of the current snapshot, and the temporal graph is explored once the agent has visited every vertex. We consider always-connected temporal graphs, in which every snapshot is connected, and ask how long exploration can be forced to take when the underlying graph, the union of all snapshots, has maximum degree at most~$Δ$. Two lower bounds were known in this setting, $Ω(Δn)$ and $Ω(n\log n)$, realised by different constructions. We establish a stronger lower bound, answering a question of Bastide, Groenland, Michel and Rambaud. Specifically, for every $n$ and $Δ$ with $Δ_0\leΔ\le n-1$ we construct an always-connected temporal graph on $n$ vertices with underlying maximum degree at most~$Δ$ that cannot be explored in fewer than $γ\,Δn\,(1+\log(n/Δ))$ time steps from any start vertex, where $γ>0$ and $Δ_0$ are absolute constants. The construction is deterministic, and every snapshot is a spanning tree with exactly one vertex of degree greater than three. Time is divided into phases. In each phase, a rotating-cycle gadget prevents the agent from reaching more than half of the trees attached to it. Between phases, we reassign target vertices among these trees using walks on a constant-degree expander, and a Gray code order of the targets keeps the underlying degree bounded. The reassignment guarantees that, for any walk of the agent, some target remains unvisited throughout all phases.

0.41