Dynamical Stability of Threshold Networks over Undirected Signed Graphs

In this paper we study the dynamic behavior of threshold networks on undirected signed graphs. While much attention has been given to the convergence and long-term behavior of this model, an open question remains: How does the underlying graph structure influence network dynamics? While similar papers have been carried out for threshold networks (as well as for other networks) these have largely focused on unsigned networks. However, the signed graph model finds applications in various real-world domains like gene regulation and social networks. By studying a graph parameter that we call "stability index," we search to establish a connection between the structure and the dynamics of threshold network. Interestingly, this parameter is related to the concepts of frustration and balance in signed graphs. We show that graphs that present negative stability index exhibit stable dynamics, meaning that the dynamics converges to fixed points regardless of threshold parameters. Conversely, if at least one subgraph has positive stability index, oscillations in long term behavior may appear. Finally, we generalize the analysis to network dynamics under periodic update schemes and we explore the case in which the stability index is positive for some subgraph finding that attractors with superpolynomial period on the size of the network may appear.