Víctor M. Preciado

Victor M. Preciado, Ali Jadbabaie

The eigenvalues of matrices representing the structure of large-scale complex networks present a wide range of applications, from the analysis of dynamical processes taking place in the network to spectral techniques aiming to rank the importance of nodes in the network. A common approach to study the relationship between the structure of a network and its eigenvalues is to use synthetic random networks in which structural properties of interest, such as degree distributions, are prescribed. Although very common, synthetic models present two major flaws: (\emph{i}) These models are only suitable to study a very limited range of structural properties, and (\emph{ii}) they implicitly induce structural properties that are not directly controlled and can deceivingly influence the network eigenvalue spectrum. In this paper, we propose an alternative approach to overcome these limitations. Our approach is not based on synthetic models, instead, we use algebraic graph theory and convex optimization to study how structural properties influence the spectrum of eigenvalues of the network. Using our approach, we can compute with low computational overhead global spectral properties of a network from its local structural properties. We illustrate our approach by studying how structural properties of online social networks influence their eigenvalue spectra.

Chinwendu Enyioha, Ali Jadbabaie, Victor Preciado et al.

We present a distributed resource allocation strategy to control an epidemic outbreak in a networked population based on a Distributed Alternating Direction Method of Multipliers (D-ADMM) algorithm. We consider a linearized Susceptible- Infected-Susceptible (SIS) epidemic spreading model in which agents in the network are able to allocate vaccination resources (for prevention) and antidotes (for treatment) in the presence of a contagion. We express our epidemic control condition as a spectral constraint involving the Perron-Frobenius eigenvalue, and formulate the resource allocation problem as a Geometric Program (GP). Next, we separate the network-wide optimization problem into subproblems optimally solved by each agent in a fully distributed way. We conclude the paper by illustrating performance of our solution framework with numerical simulations.

Jingqi Li, Ximing Chen, Sérgio Pequito et al.

In this paper, we consider the structural stabilizability problem of undirected networks. More specifically, we are tasked to infer the stabilizability of an undirected network from its underlying topology, where the undirected networks are modeled as continuous-time linear time-invariant (LTI) systems involving symmetric state matrices. Firstly, we derive a graph-theoretic necessary and sufficient condition for structural stabilizability of undirected networks. Then, we propose a method to infer the maximum dimension of stabilizable subspace solely based on the network structure. Based on these results, on one hand, we study the optimal actuator-disabling attack problem, i.e., removing a limited number of actuators to minimize the maximum dimension of stabilizable subspace. We show this problem is NP-hard. On the other hand, we study the optimal recovery problem with respect to the same kind of attacks, i.e., adding a limited number of new actuators such that the maximum dimension of stabilizable subspace is maximized. We prove the optimal recovery problem is also NP-hard, and we develop a (1-1/e) approximation algorithm to this problem.

Soheil Eshghi, Victor M. Preciado, Saswati Sarkar et al.

We analyze optimal strategies for the allocation of a finite budget that can be invested in different advertising channels over time with the objective of influencing social opinions in a network of individuals. In our analysis, we consider both exogenous influence mechanisms, such as advertising campaigns, as well as endogenous mechanisms of social influence, such as word-of-mouth and peer-pressure, which are modeled using diffusion dynamics. We show that for a broad family of objective functions, the optimal influence strategy at every time uses all channels at either their maximum rate or not at all, i.e., a bang-bang strategy. Furthermore, we prove that the number of switches between these extremes is bounded above by a term that is typically much smaller than the number of agents. This means that the optimal influence strategy is to exert maximum effort in waves for every channel, and then cease effort and let the effects propagate. We also show that, at the beginning of the campaign, the total cost-adjusted reach of an exogenous advertising channel determines its relative value. In contrast, as we approach our investment horizon (e.g., election day), the optimal strategy is to invest in channels able to target individuals instead of broad-reaching channels. We demonstrate that the optimal influence strategies are easily computable in several practical cases, and explicitly characterize the optimal controls for the case of linear objective functions in closed form. Finally, we see that, in the canonical example of designing an election campaign, identifying late-deciders is a critical component in the optimal design.

Michael M. Zavlanos, Victor M. Preciado, Ali Jadbabaie

The eigenvalue spectrum of the adjacency matrix of a network is closely related to the behavior of many dynamical processes run over the network. In the field of robotics, this spectrum has important implications in many problems that require some form of distributed coordination within a team of robots. In this paper, we propose a continuous-time control scheme that modifies the structure of a position-dependent network of mobile robots so that it achieves a desired set of adjacency eigenvalues. For this, we employ a novel abstraction of the eigenvalue spectrum by means of the adjacency matrix spectral moments. Since the eigenvalue spectrum is uniquely determined by its spectral moments, this abstraction provides a way to indirectly control the eigenvalues of the network. Our construction is based on artificial potentials that capture the distance of the network's spectral moments to their desired values. Minimization of these potentials is via a gradient descent closed-loop system that, under certain convexity assumptions, ensures convergence of the network topology to one with the desired set of moments and, therefore, eigenvalues. We illustrate our approach in nontrivial computer simulations.

Victor M. Preciado, Moez Draief, Ali Jadbabaie

We study how the behavior of viral spreading processes is influenced by local structural properties of the network over which they propagate. For a wide variety of spreading processes, the largest eigenvalue of the adjacency matrix of the network plays a key role on their global dynamical behavior. For many real-world large-scale networks, it is unfeasible to exactly retrieve the complete network structure to compute its largest eigenvalue. Instead, one usually have access to myopic, egocentric views of the network structure, also called egonets. In this paper, we propose a mathematical framework, based on algebraic graph theory and convex optimization, to study how local structural properties of the network constrain the interval of possible values in which the largest eigenvalue must lie. Based on this framework, we present a computationally efficient approach to find this interval from a collection of egonets. Our numerical simulations show that, for several social and communication networks, local structural properties of the network strongly constrain the location of the largest eigenvalue and the resulting spreading dynamics. From a practical point of view, our results can be used to dictate immunization strategies to tame the spreading of a virus, or to design network topologies that facilitate the spreading of information virally.

Shuo Yang, Shaoru Chen, Victor M. Preciado et al.

Learning-based controllers, such as neural network (NN) controllers, can show high empirical performance but lack formal safety guarantees. To address this issue, control barrier functions (CBFs) have been applied as a safety filter to monitor and modify the outputs of learning-based controllers in order to guarantee the safety of the closed-loop system. However, such modification can be myopic with unpredictable long-term effects. In this work, we propose a safe-by-construction NN controller which employs differentiable CBF-based safety layers, and investigate the performance of safe-by-construction NN controllers in learning-based control. Specifically, two formulations of controllers are compared: one is projection-based and the other relies on our proposed set-theoretic parameterization. Both methods demonstrate improved closed-loop performance over using CBF as a separate safety filter in numerical experiments.

Victor M. Preciado, Jaelynn Oh, Ali Jadbabaie

This paper studies $n$-person simultaneous-move games with linear best response function, where individuals interact within a given network structure. This class of games have been used to model various settings, such as, public goods, belief formation, peer effects, and oligopoly. The purpose of this paper is to study the effect of the network structure on Nash equilibrium outcomes of this class of games. Bramoullé et al. derived conditions for uniqueness and stability of a Nash equilibrium in terms of the smallest eigenvalue of the adjacency matrix representing the network of interactions. Motivated by this result, we study how local structural properties of the network of interactions affect this eigenvalue, influencing game equilibria. In particular, we use algebraic graph theory and convex optimization to derive new bounds on the smallest eigenvalue in terms of the distribution of degrees, cycles, and other relevant substructures. We illustrate our results with numerical simulations involving online social networks.

Michael Zargham, Zixuan Zhang, Victor Preciado

Decentralized Ledger Technology, popularized by the Bitcoin network, aims to keep track of a ledger of valid transactions between agents of a virtual economy without a central institution for coordination. In order to keep track of a faithful and accurate list of transactions, the ledger is broadcast and replicated across machines in a peer-to-peer network. To enforce validity of transactions in the ledger (i.e., no negative balance or double spending), the network as a whole coordinates to accept or reject new transactions based on a set of rules aiming to detect and block operations of malicious agents (i.e., Byzantine attacks). Consensus protocols are particularly important to coordinate operation of the network, since they are used to reconcile potentially conflicting versions of the ledger. Regardless of architecture and consensus mechanism used, resulting economic networks remain largely similar, with economic agents driven by incentives under a set of rules. Due to the intense activity in this area, proper mathematical frameworks to model and analyze behavior of blockchain-enabled systems are essential. In this paper, we address this need and provide the following contributions: (i) we establish a formal framework, with tools from dynamical systems theory, to mathematically describe core concepts in blockchain-enabled networks, (ii) we apply this framework to the Bitcoin network and recover its key properties, and (iii) we connect our modeling framework with powerful tools from control engineering, such as Lyapunov-like functions, to properly engineer economic systems with provable properties. Apart from the aforementioned contributions, the mathematical framework herein proposed lays a foundation for engineering more general economic systems built on emerging Turing complete networks, such as the Ethereum network, through which complex alternative economic models are explored.

Victor M. Preciado, Michael Zargham, Chinwendu Enyioha et al.

In this chapter, we consider the problem of designing protection strategies to contain spreading processes in complex cyber-physical networks. We illustrate our ideas using a family of bio-motivated spreading models originally proposed in the epidemiological literature, e.g., the Susceptible-Infected-Susceptible (SIS) model. We first introduce a framework in which we are allowed to distribute two types of resources in order to contain the spread, namely, (i) preventive resources able to reduce the spreading rate, and (ii) corrective resources able to increase the recovery rate of nodes in which the resources are allocated. In practice, these resources have an associated cost that depends on either the resiliency level achieved by the preventive resource, or the restoration efficiency of the corrective resource. We present a mathematical framework, based on dynamic systems theory and convex optimization, to find the cost-optimal distribution of protection resources in a network to contain the spread. We also present two extensions to this framework in which (i) we consider generalized epidemic models, beyond the simple SIS model, and (ii) we assume uncertainties in the contact network in which the spreading is taking place. We compare these protection strategies with common heuristics previously proposed in the literature and illustrate our results with numerical simulations using the air traffic network.

M. Amin Rahimian, Victor M. Preciado

In this paper the focus is on the relationship between the occurrence of failures in a (directed or undirected) network of linear single integrator agents and the presence of jump discontinuities in the derivatives of the network output. Based on this relationship, an algorithm for sensor placement is proposed, which enables the designer to detect and isolate any link failures across the network, based on the jump discontinuities observed by the sensor nodes. These results are explained through elaborative examples and computer experiments.

Mikhail Hayhoe, Hans Riess, Victor M. Preciado et al.

We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs), which we call a Hyper-graph Expansion Neural Network (HENN), and provide the first bounds on the stability and transferability error of a hypergraph signal processing model. To do so, we provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity. By bounding the difference between two graph shift operators (GSOs) in the positive semi-definite sense via their eigenvalue spectrum, we show that this error depends only on the properties of the GNN and the magnitude of spectral similarity of the GSOs. Moreover, we show that existing transferability results that assume the graphs are small perturbations of one another, or that the graphs are random and drawn from the same distribution or sampled from the same graphon can be recovered using our approach. Thus, both GNNs and our HENNs (trained using normalized Laplacians as graph shift operators) will be increasingly stable and transferable as the graphs become larger. Experimental results illustrate the importance of considering multiple graph representations in HENN, and show its superior performance when transferability is desired.

Renukanandan Tumu, Cristian Ioan Vasile, Victor Preciado et al.

We present the Social Influence Game (SIG), a framework for modeling adversarial persuasion in social networks with an arbitrary number of competing players. Our goal is to provide a tractable and interpretable model of contested influence that scales to large systems while capturing the structural leverage points of networks. Each player allocates influence from a fixed budget to steer opinions that evolve under DeGroot dynamics, and we prove that the resulting optimization problem is a difference-of-convex program. To enable scalability, we develop an Iterated Linear (IL) solver that approximates player objectives with linear programs. In experiments on random and archetypical networks, IL achieves solutions within 7% of nonlinear solvers while being over 10x faster, scaling to large social networks. This paper lays a foundation for asymptotic analysis of contested influence in complex networks.

Victor M. Preciado

We establish a canonical decomposition of the infinitesimal Koopman generator of any port-Hamiltonian (pH) system into skew-adjoint (energy-conserving), positive-semidefinite (dissipative), and input-port components, proving that the generator satisfies an energy-dissipation inequality on a dense subdomain of $L^2(μ)$ for any invariant measure $μ$ satisfying a mild joint-invariance condition stated in Theorem 1. This infinite-dimensional splitting carries over exactly to finite-dimensional Galerkin approximations, yielding structure-constrained surrogate models that provably inherit passivity with a quadratic storage function in the lifted observable space. Leveraging this structure, we design passivity-based controllers directly in the lifted space and establish asymptotic stability of the lifted closed-loop system via LaSalle's invariance principle under a mild detectability condition. For linear pH systems, the decomposition recovers the true pH matrices exactly, confirming that the structural constraints arise naturally from the operator theory rather than being imposed by hand. The framework unifies port-Hamiltonian systems theory and Koopman spectral methods, providing a rigorous operator-theoretic foundation for energy-consistent lifting of nonlinear pH dynamics.

Victor M. Preciado

In Willems' behavioral systems theory, a dynamical system is identified with the set of all trajectories compatible with its laws of motion. For nonlinear or stochastic systems, however, the admissible trajectory set is generally nonconvex, obstructing direct optimization over the behavior. In this paper, we lift the behavioral viewpoint from trajectories to probability measures on trajectories by representing a finite-horizon dynamical system with the set of all Borel probability measures supported on its admissible trajectories. This behavioral-measure set is convex and weakly closed even for nonlinear or stochastic dynamics, because convex combinations of trajectory distributions remain dynamically admissible even when convex combinations of trajectories do not. The extreme points are precisely the Dirac masses on individual admissible trajectories, so the classical deterministic theory is embedded as the extremal skeleton of the richer measure-valued object. On this foundation we establish two core deterministic results and outline a stochastic extension based on conditional kernel consistency. First, optimal control for a prescribed initial distribution becomes a linear program over occupation measures whose dual is exactly Bellman's dynamic-programming recursion, with strong duality under compactness and continuity. Second, for controllable linear time-invariant systems under persistency of excitation, we prove a measure-level Fundamental Lemma: every probability measure on the finite-horizon behavior factors through the data Hankel matrix, reducing any optimization over trajectory distributions to an equivalent optimization over coefficient-space distributions. This is an exact data-driven reformulation requiring no model knowledge beyond a single informative trajectory; the classical Fundamental Lemma is recovered as the special case of Dirac measures.

Georgios Kissas, Jacob Seidman, Leonardo Ferreira Guilhoto et al.

Supervised operator learning is an emerging machine learning paradigm with applications to modeling the evolution of spatio-temporal dynamical systems and approximating general black-box relationships between functional data. We propose a novel operator learning method, LOCA (Learning Operators with Coupled Attention), motivated from the recent success of the attention mechanism. In our architecture, the input functions are mapped to a finite set of features which are then averaged with attention weights that depend on the output query locations. By coupling these attention weights together with an integral transform, LOCA is able to explicitly learn correlations in the target output functions, enabling us to approximate nonlinear operators even when the number of output function in the training set measurements is very small. Our formulation is accompanied by rigorous approximation theoretic guarantees on the universal expressiveness of the proposed model. Empirically, we evaluate the performance of LOCA on several operator learning scenarios involving systems governed by ordinary and partial differential equations, as well as a black-box climate prediction problem. Through these scenarios we demonstrate state of the art accuracy, robustness with respect to noisy input data, and a consistently small spread of errors over testing data sets, even for out-of-distribution prediction tasks.

Alp Aydinoglu, Philip Sieg, Victor M. Preciado et al.

We propose a control framework which can utilize tactile information by exploiting the complementarity structure of contact dynamics. Since many robotic tasks, like manipulation and locomotion, are fundamentally based in making and breaking contact with the environment, state-of-the-art control policies struggle to deal with the hybrid nature of multi-contact motion. Such controllers often rely heavily upon heuristics or, due to the combinatorial structure in the dynamics, are unsuitable for real-time control. Principled deployment of tactile sensors offers a promising mechanism for stable and robust control, but modern approaches often use this data in an ad hoc manner, for instance to guide guarded moves. This framework can close the loop on tactile sensors and it is non-combinatorial, enabling optimization algorithms to automatically synthesize provably stable control policies. We demonstrate this approach on multiple numerical examples, including quasi-static friction problems and a high dimensional problem with ten contacts. We also validate our results on an experimental setup and show the effectiveness of the proposed method on an underactuated multi-contact system.

Jacob H. Seidman, Mahyar Fazlyab, Victor M. Preciado et al.

The fragility of deep neural networks to adversarially-chosen inputs has motivated the need to revisit deep learning algorithms. Including adversarial examples during training is a popular defense mechanism against adversarial attacks. This mechanism can be formulated as a min-max optimization problem, where the adversary seeks to maximize the loss function using an iterative first-order algorithm while the learner attempts to minimize it. However, finding adversarial examples in this way causes excessive computational overhead during training. By interpreting the min-max problem as an optimal control problem, it has recently been shown that one can exploit the compositional structure of neural networks in the optimization problem to improve the training time significantly. In this paper, we provide the first convergence analysis of this adversarial training algorithm by combining techniques from robust optimal control and inexact oracle methods in optimization. Our analysis sheds light on how the hyperparameters of the algorithm affect the its stability and convergence. We support our insights with experiments on a robust classification problem.

Alp Aydinoglu, Victor M. Preciado, Michael Posa

While many robotic tasks, like manipulation and locomotion, are fundamentally based in making and breaking contact with the environment, state-of-the-art control policies struggle to deal with the hybrid nature of multi-contact motion. Such controllers often rely heavily upon heuristics or, due to the combinatoric structure in the dynamics, are unsuitable for real-time control. Principled deployment of tactile sensors offers a promising mechanism for stable and robust control, but modern approaches often use this data in an ad hoc manner, for instance to guide guarded moves. In this work, by exploiting the complementarity structure of contact dynamics, we propose a control framework which can close the loop on rich, tactile sensors. Critically, this framework is non-combinatoric, enabling optimization algorithms to automatically synthesize provably stable control policies. We demonstrate this approach on three different underactuated, multi-contact robotics problems.

Jingqi Li, Ximing Chen, Sérgio Pequito et al.

In this paper, we study the target controllability problem of networked dynamical systems, in which we are tasked to steer a subset of network states towards a desired objective. More specifically, we derive necessary and sufficient conditions for the structural target controllability problem of linear time-invariant (LTI) systems with symmetric state matrices, such as undirected dynamical networks with unknown link weights. To achieve our goal, we first characterize the generic rank of symmetrically structured matrices, as well as the modes of any numerical realization. Subsequently, we provide a graph-theoretic necessary and sufficient condition for the structural controllability of undirected networks with multiple control nodes. Finally, we derive a graph-theoretic necessary and sufficient condition for structural target controllability of undirected networks. Remarkably, apart from the standard reachability condition, only local topological information is needed for the verification of structural target controllability.

Victor M. Preciado, M. Amin Rahimian

We propose a theoretical framework to study the eigenvalue spectra of the controllability Gramian of systems with random state matrices, such as networked systems with a random graph structure. Using random matrix theory, we provide expressions for the moments of the eigenvalue distribution of the controllability Gramian. These moments can then be used to derive useful properties of the eigenvalue distribution of the Gramian (in some cases, even closed-form expressions for the distribution). We illustrate this framework by considering system matrices derived from common random graph and matrix ensembles, such as the Wigner ensemble, the Gaussian Orthogonal Ensemble (GOE), and random regular graphs. Subsequently, we illustrate how the eigenvalue distribution of the Gramian can be used to draw conclusions about the energy required to control random system.

Nikolay A. Atanasov, Roberto Tron, Victor M. Preciado et al.

This paper addresses the problem of collaborative tracking of dynamic targets in wireless sensor networks. A novel distributed linear estimator, which is a version of a distributed Kalman filter, is derived. We prove that the filter is mean square consistent in the case of static target estimation. When large sensor networks are deployed, it is common that the sensors do not have good knowledge of their locations, which affects the target estimation procedure. Unlike most existing approaches for target tracking, we investigate the performance of our filter when the sensor poses need to be estimated by an auxiliary localization procedure. The sensors are localized via a distributed Jacobi algorithm from noisy relative measurements. We prove strong convergence guarantees for the localization method and in turn for the joint localization and target estimation approach. The performance of our algorithms is demonstrated in simulation on environmental monitoring and target tracking tasks.