PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Sign Herdability in Temporal Networks: A Sufficient Condition via $\pi_p$-Graphs

Pradeep M, Twinkle Tripathy

arXiv:2609.10785v2eess.SYcs.SY

TL;DR

Herdability in temporal networks concerns reaching the positive orthant under a fixed switching sequence, where temporal ordering and path signs complicate its analysis. The paper connects temporal walks and controllability to herdability conditions, then shows that a spanning π_p-graph in the union multigraph suffices for structural sign herdability.

  • Problem

    The paper addresses how to characterize herdability in temporally switching networks, where a predefined switching order makes temporal analysis distinct from static-network graph conditions.

    Source: §I · p. 1, §V · p. 5

  • Method

    The authors relate temporal walks to controllability and study edge-weight and duration effects, then introduce a union multigraph and a π-graph condition.

    Source: §I · p. 2

  • Results

    A spanning π_p-graph across the temporal sequence in the union multigraph suffices for structural sign herdability.

    Source: B. π-Graph and Conditions for SS… · p. 7

  • Takeaways & Limitations

    The proposed π_p-graph criterion provides a sufficient graph-theoretic condition for structural sign herdability in temporal networks.

    Source: §I · p. 2, §VI · p. 7

    The paper leaves extensions to temporal networks with arbitrary topologies for future work.

    Source: §VI · p. 7

Abstract

from arXiv · show

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 $\pi$-graph. We show that the existence of a $\pi_p$-graph, which is a temporally evolving $\pi$-graph, is sufficient to guarantee $\mathcal{SS}$ herdability. Illustrative examples are provided to demonstrate the proposed results.

I. INTRODUCTION

Herdability asks whether a network state can be driven into the positive orthant, but a fixed temporal switching order can make results from conventional switched or union-graph analyses insufficient. The paper develops temporal-walk conditions and a dilation-independent graph condition for structural sign herdability.

I. INTRODUCTION

  • A fixed switching order can leave a temporal network not herdable even when another order makes the switching system herdable.For the example, {A1 → A3 → A2} works, whereas the predefined {A1 → A2 → A3} does not.Source: §I · p. 2
  • The authors motivate a temporal graph criterion because union-graph herdability may not hold for a predefined temporal sequence.Their example distinguishes the fixed-order temporal setting from arbitrary switching and union-graph analysis.Source: §I · pp. 1–2
  • Input connectivity alone does not guarantee structural sign herdability because opposing path signs can cancel in the controllability matrix.The introduction motivates seeking structural guarantees beyond connectivity.Source: §I · p. 2
  • Temporal-walk analysis yields necessary and sufficient herdability conditions for a given realization, with DAG-specific conditions also identified.The introduction describes the DAG conditions as separately necessary and sufficient.Source: §I · p. 2
  • Herdability depends on edge-weight magnitudes and snapshot durations as well as network topology.The paper examines these effects alongside structural sign herdability under temporal variation.Source: §I · p. 2
  • A spanning π_p-graph in the union multigraph suffices for structural sign herdability in temporal networks.The condition is independent of signed and layer dilation.Source: §I · p. 2

A. Notation and Matrix Theory

This section establishes notation for indices, vector entries, sign-consistent vectors, matrix components, images, and null spaces.

A. Notation and Matrix Theory

B. Graph Theory

The graph-theory section defines a weighted signed digraph and the walk and path-product terminology used in the paper.

B. Graph Theory

  • A weighted signed digraph is specified by node set V, edge set E ⊆ V × V, and adjacency matrix A.Source: B. Graph Theory · p. 2
  • A walk is a sequence of directed edges connecting an initial node to a final node.Source: B. Graph Theory · p. 2
  • A walk's path product is the product of its corresponding edge weights.Source: B. Graph Theory · p. 2

A. Linear Temporally Switching Systems

The paper represents a temporal network as a sequence of linear systems active over successive intervals, then characterizes its reachable directions and time-ordered walks.

A. Linear Temporally Switching Systems

  • Snapshot i governs the system pair (A_i, B_i) over interval [t_(i−1), t_i), with its adjacency matrix describing that snapshot.Source: A. Linear Temporally Switching Systems · p. 2
  • The analysis assumes one leader node shared across snapshots and takes node 1 as that leader, with B_i = B = b_i e_1.Here e_1 is the first standard basis vector and b_i is the snapshot's scalar input gain.Source: A. Linear Temporally Switching Systems · p. 2
  • Temporal herdability requires piecewise-continuous inputs that steer every initial state into the positive orthant at the final time.The inputs are specified separately over the successive snapshot intervals.Source: A. Linear Temporally Switching Systems · p. 3
  • The reachable subspace combines snapshot controllable subspaces propagated through later snapshot dynamics.For example, e^(A_N T_N) C_(N−1) propagates directions generated during interval N−1 through the final interval.Source: A. Linear Temporally Switching Systems · p. 3
  • A temporal walk follows edges whose snapshot indices are nondecreasing; its path sign is the sign of the edge-weight product.A node is input-connected when a temporal walk reaches it from a leader across the snapshot sequence.Source: A. Linear Temporally Switching Systems · p. 3

IV. NECESSARY AND SUFFICIENT CONDITIONS FOR HERDABILITY IN TEMPORAL NETWORKS

This section links herdability to temporal walks and controllability-matrix structure: input connectivity is necessary, while sign-consistent columns or paths provide sufficient tests. The fixed switching sequence and snapshot durations shape the temporal-walk contributions.

IV. NECESSARY AND SUFFICIENT CONDITIONS FOR HERDABILITY IN TEMPORAL NETWORKS

  • Herdability on [t0, tf) holds iff Null(C(tf)^T) ∩ R^n_{≥0} = {0}, equivalently a strictly positive vector lies in Im(C(tf)).Source: §IV · p. 3
  • Every node must be input-connected by at least one temporal walk from the leader for the network to be herdable.Each nonzero controllability-matrix entry corresponds to a temporal walk.Source: §IV · pp. 3–4
  • A network is herdable if every row of its controllability matrix has a nonzero entry in a unisigned column.A unisigned column has nonzero entries sharing one sign.Source: §IV · p. 4
  • A unique same-sign temporal walk per node is sufficient; more generally, Theorem 1 requires same-sign leader paths to every node in at least one snapshot.Source: §IV · pp. 4–5
  • If the final subsystem pair (A_N, B) is herdable, the temporal network is herdable throughout the final interval [t_f−1, t_f).Source: §IV · p. 4
  • Two temporal walks to node 5 contribute −T2^2 and −T2T3, so their sum depends on the durations of the snapshots they span.One walk lies entirely within snapshot G2; the other spans G2 and G3.Source: §IV · p. 5

V. A SUFFICIENT CONDITION FOR SS HERDABILITY OF TEMPORALLY SWITCHING NETWORKS

This section examines structural sign herdability through graph-theoretic conditions and shows that changing edge-weight magnitudes can change herdability even when the sign pattern is fixed.

V. A SUFFICIENT CONDITION FOR SS HERDABILITY OF TEMPORALLY SWITCHING NETWORKS

  • The section seeks graph-theoretic conditions for SS herdability, against the background of the cactus criterion for structural controllability of directed graphs.Source: §V · p. 5
  • In the example, equality between the compared edge-weight terms makes rows 4–5 vanish and fails herdability, while the stated strict inequality yields SS herdability.The conclusion holds under the stated assumption.Source: §V · p. 6
  • SS herdability asks whether a realization preserving the subsystem zero-nonzero and sign patterns is herdable over a temporal sequence, while magnitudes may vary.Source: §V · p. 6

A. Union Multigraph GU(A, B)

The union multigraph combines the subsystem digraphs while preserving their node sets, edge weights, and edge multiplicities.

A. Union Multigraph GU(A, B)

B. π-Graph and Conditions for SS Herdability

A temporally evolving πp-graph spanning the union multigraph provides a sufficient condition for structural sign herdability. The condition relies on consistent path signs, while cycles complicate herdability verification.

B. π-Graph and Conditions for SS Herdability

VI. CONCLUSIONS

The paper derives herdability conditions for temporally switching directed networks and shows that edge-weight magnitudes can affect herdability. It also establishes a sufficient graph-theoretic condition for structural sign herdability and identifies arbitrary-topology extensions as future work.

VI. CONCLUSIONS

  • The study derives necessary and sufficient herdability conditions for temporal networks and shows that edge-weight magnitudes influence herdability.Source: §VI · p. 7
  • A spanning πp-graph in the union multigraph is sufficient to guarantee structural sign herdability.Source: §VI · p. 7
  • Future work will extend the results to temporal networks with arbitrary topologies.Source: §VI · p. 7
Loading 2609.10785v2…