Search

This paper presents a novel meta-algorithm, Partition-Merge (PM), which takes existing centralized algorithms for graph computation and makes them distributed and faster. In a nutshell, PM divides the graph into small subgraphs using our novel randomized partitioning scheme, runs the centralized algorithm on each partition separately, and then stitches the resulting solutions to produce a global solution. We demonstrate the efficiency of the PM algorithm on two popular problems: computation of Maximum A Posteriori (MAP) assignment in an arbitrary pairwise Markov Random Field (MRF) and modularity optimization for community detection. We show that the resulting distributed algorithms for these problems become fast, which run in time linear in the number of nodes in the graph. Furthermore, PM leads to performance comparable – or even better – to that of the centralized algorithms as long as the graph has polynomial growth property. More precisely, if the centralized algorithm is a $\mathcal {C}-$ factor approximation with constant $\mathcal {C}\ge 1$ , the resulting distributed algorithm is a $(\mathcal {C}+\delta)$ -factor approximation for any small $\delta >0$ ; and even if the centralized algorithm is a non-constant (e.g., logarithmic) factor approximation, then the resulting distributed algorithm becomes a constant factor approximation. For general graphs, we compute explicit bounds on the loss of performance of the resulting distributed algorithm with respect to the centralized algorithm. To show the efficiency of our algorithm, we conducted extensive experiments both on real-world networks and on synthetic networks. The experiments demonstrate that the PM algorithm provides a good trade-off between accuracy and running time.

A nonnegative matrix $A$ is called primitive if $A^k$ is positive for some integer $k>0$. A generalization of this concept to finite sets of matrices is as follows: a set of matrices $\mathcal M = \{A_1, A_2, \ldots, A_m \}$ is primitive if $A_{i_1} A_{i_2} \ldots A_{i_k}$ is positive for some indices $i_1, i_2, ..., i_k$. The concept of primitive sets of matrices comes up in a number of problems within the study of discrete-time switched systems. In this paper, we analyze the computational complexity of deciding if a given set of matrices is primitive and we derive bounds on the length of the shortest positive product. We show that while primitivity is algorithmically decidable, unless $P=NP$ it is not possible to decide primitivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be superpolynomial in the dimension of the matrices. On the other hand, defining ${\mathcal P}$ to be the set of matrices with no zero rows or columns, we give a simple combinatorial proof of a previously-known characterization of primitivity for matrices in ${\mathcal P}$ which can be tested in polynomial time. This latter observation is related to the well-known 1964 conjecture of Cerny on synchronizing automata; in fact, any bound on the minimal length of a synchronizing word for synchronizing automata immediately translates into a bound on the length of the shortest positive product of a primitive set of matrices in ${\mathcal P}$. In particular, any primitive set of $n \times n$ matrices in ${\mathcal P}$ has a positive product of length $O(n^3)$.

The recent development of telecommunication networks is producing an unprecedented wealth of information and, as a consequence, an increasing interest in analyzing such data both from telecoms and from other stakeholders' points of view. In particular, mobile phone datasets offer access to insights into urban dynamics and human activities at an unprecedented scale and level of detail, representing a huge opportunity for research and real-world applications. This article surveys the new ideas and techniques related to the use of telecommunication data for urban sensing. We outline the data that can be collected from telecommunication networks as well as their strengths and weaknesses with a particular focus on urban sensing. We survey existing filtering and processing techniques to extract insights from this data and summarize them to provide recommendations on which datasets and techniques to use for specific urban sensing applications. Finally, we discuss a number of challenges and open research areas currently being faced in this field. We strongly believe the material and recommendations presented here will become increasingly important as mobile phone network datasets are becoming more accessible to the research community.

A set of stochastic matrices ${\cal P}$ is a consensus set if for every sequence of matrices $P(1), P(2), \ldots$ whose elements belong to ${\cal P}$ and every initial state $x(0)$, the sequence of states defined by $x(t) = P(t) P(t-1) \cdots P(1) x(0)$ converges to a vector whose entries are all identical. In this paper, we introduce an "avoiding set condition" for compact sets of matrices and prove in our main theorem that this explicit combinatorial condition is both necessary and sufficient for consensus. We show that several of the conditions for consensus proposed in the literature can be directly derived from the avoiding set condition. The avoiding set condition is easy to check with an elementary algorithm, and so our result also establishes that consensus is algorithmically decidable. Direct verification of the avoiding set condition may require more than a polynomial time number of operations. This is however likely to be the case for any consensus checking algorithm since we also prove in this paper that unless $P=NP$, consensus cannot be decided in polynomial time.

The process of coral larval dispersal is important for coral reef ecosystems, but remains poorly understood and hard to gauge. Better knowledge of inter-reef connectivity patterns would be useful in enabling better management of coral reef waters however. By employing a spatially explicit numerical modelling approach, we simulate larval dispersal through the central section of the Great Barrier Reef (GBR), comprising over 1000 reefs, and identify spatial patterns in the inter-reef connectivity network using a community detection method from network science. This paper presents the modelling approach used and discusses the significance of the results. Inter-reef connectivity networks were estimated for 4 different coral species, and significant differences between them were found. We show how we can partition reefs into clusters, or “communities”, that are sparsely connected with each other, and therefore identify important barriers to larval dispersal. By fine-tuning a resolution parameter in the community detection method, we can find dispersal barriers of varying strength. Finally, we show that the average connectivity length scale varies significantly across the different reef communities, and suggest that this may have repercussions for the optimal placement of marine protected areas (MPAs) to maximise connectivity with surrounding reefs.

Mobile phone datasets allow for the analysis of human behavior on an unprecedented scale. The social network, temporal dynamics and mobile behavior of mobile phone users have often been analyzed independently from each other using mobile phone datasets. In this article, we explore the connections between various features of human behavior extracted from a large mobile phone dataset. Our observations are based on the analysis of communication data of 100000 anonymized and randomly chosen individuals in a dataset of communications in Portugal. We show that clustering and principal component analysis allow for a significant dimension reduction with limited loss of information. The most important features are related to geographical location. In particular, we observe that most people spend most of their time at only a few locations. With the help of clustering methods, we then robustly identify home and office locations and compare the results with official census data. Finally, we analyze the geographic spread of users' frequent locations and show that commuting distances can be reasonably well explained by a gravity model., Comment: 16 pages, 12 figures

Massive datasets that capture human movements and social interactions have catalyzed rapid advances in our quantitative understanding of human behavior during the past years. One important aspect affecting both areas is the critical role space plays. Indeed, growing evidence suggests both our movements and communication patterns are associated with spatial costs that follow reproducible scaling laws, each characterized by its specific critical exponents. Although human mobility and social networks develop concomitantly as two prolific yet largely separated fields, we lack any known relationships between the critical exponents explored by them, despite the fact that they often study the same datasets. Here, by exploiting three different mobile phone datasets that capture simultaneously these two aspects, we discovered a new scaling relationship, mediated by a universal flux distribution, which links the critical exponents characterizing the spatial dependencies in human mobility and social networks. Therefore, the widely studied scaling laws uncovered in these two areas are not independent but connected through a deeper underlying reality.

In this study, a method is presented to compute the optimal sampling time in a network such that consensus is reached with a minimum number of iterations. In particular, the authors analyse a network composed of N first-order agents with communication delays. The communication is done in discrete time, sampling all the signals associated with every agent at the same sampling time, taking into account the existence of a time delay. The authors look for the optimal sampling time such that consensus is reached in a minimum number of iterations, which minimises the communication cost, in terms of energy and bandwidth. The analysis is performed by minimising an objective function that takes into account a measure of the convergence rate to reach a consensus. This objective function mainly depends on the eigenvalues of the sampled transition matrix of the system. The method can be applied to medium/large-scale networks, since it requires computing the eigenvalues of the adjacency matrix just once. Finally, a case study is presented based on the torus topology, where the interconnection of 100 agents is analysed, and we obtain the optimal sampling time to reach consensus with and without communication delay.

International audience; We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.

The concept of elementary flux vector is valuable in a number of applications of metabolic engineering. For instance, in metabolic flux analysis, each admissible flux vector can be expressed as a non-negative linear combination of a small number of elementary flux vectors. However a critical issue concerns the total number of elementary flux vectors which may be huge because it combinatorially increases with the size of the metabolic network. In this paper we present a fast algorithm that randomly computes a decomposition of admissible flux vectors in a minimal number of elementary flux vectors without explicitly enumerating all of them.

An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors. When the agent is able to determine his position only from time to time, the graph is said to be \emph{partly observable}. Observability in graphs is desirable in situations where autonomous agents are moving on a network and one wants to localize them (or the agent wants to localize himself) with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to observable discrete event systems and to local automata. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. From this it follows that it may be necessary for an agent to pass through the same node several times before he is finally able to determine his position in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete., 15 pages, 8 figures

This work presents a method to compute the optimal sampling time that makes N MIMO agents converge to the consensus state with minimum energy consumption. In its turn, every agent in the network is composed of n continuous time first order linear systems. The communication is done in discrete time, sampling all the signals associated to every agent at the same sampling time. In order to minimize the energy consumed in the process of communication, we will look for the optimal sampling time such that the consensus is reached in a minimum number of iterations. The analysis is performed by minimizing objective functions that take into account a measure of the convergence rate to reach a consensus. These objective functions mainly depend on the eigenvalues of the sampled transition matrix of the system. The method can be applied to medium/large scale networks, since it requires computing the eigenvalues of the adjacency matrix just once. Finally, we present a case study based on the torus topology, where a MIMO case of communication (1000 systems) is analyzed, obtaining the optimal sampling time to reach the consensus.

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate of products of matrices in the set. This quantity appears in many applications but is known to be difficult to approximate. Several approaches to approximate the joint spectral radius involve the construction of long products of matrices, or the construction of an appropriate extremal matrix norm. In this article we present a brief overview of several recent approximation algorithms and introduce a genetic algorithm approximation method. This new method does not give any accuracy guarantees but is quite fast in comparison to other techniques. The performances of the different methods are compared and are illustrated on some benchmark examples. Our results show that, for large sets of matrices or matrices of large dimension, our genetic algorithm may provide better estimates or estimates for situations where these are simply too expensive to compute with other methods. As an illustration of this we compute in less than a minute a bound on the capacity of a code avoiding a given forbidden pattern that improves the bound currently reported in the literature.

We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. In particular, we show that the continuous version of the nonnegativity problem is NP-hard in general and we show that the presence of a zero is decidable for several subcases, including instances of depth two or less, although the decidability in general is left open. The problems may also be stated as reachability problems related to real zeros of exponential polynomials or solutions to initial value problems of linear differential equations, which are interesting problems in their own right.

This work presents a method to analyze the convergence to consensus of a network of first order linear systems, when the signals associated to the interconnections are sampled from the continuous time systems. In order to minimize the energy consumed in the process of communication, we will look for the optimal sampling time such that the consensus is reached in a minimum number of iterations (communications). The analysis is performed by minimizing several objective functions that take into account a measure of the convergence rate to reach a consensus. These objective functions mainly depend on the eigenvalues of the sampled transition matrix of the system. Finally, we present a case study based on the torus topology, where a simple case of communication is analyzed and the optimal sampling time to reach a consensus is obtained.

We study the number u"@a(n) of @a-power-free binary words of length n, and the asymptotics of this number when n tends to infinity, for a fixed rational number @a in (2,7/3]. For any such @a, we prove a structure result that allows us to describe constructively the sequence u"@a(n) as a 2-regular sequence. This provides an algorithm that computes the number u"@a(n) in logarithmic time, for fixed @a. Then, generalizing recent results on 2^+-free words, we describe the asymptotic behaviour of u"@a(n) in terms of joint spectral quantities of a pair of matrices that one can efficiently construct, given a rational number @a. For @a=7/3, we compute the automaton and give sharp estimates for the asymptotic behaviour of u"@a(n).

The convexity arguments used in the consensus literature to prove synchronization in vector spaces can be applied to the circle only when all agents are initially located on a semicircle. Existing strategies for (almost-)global synchronization on the circle are either restricted to specific interconnection topologies or use auxiliary variables. The present paper first illustrates this problem by showing that weighted, directed interconnection topologies can be designed to make any reasonably chosen configuration of the agents on the circle a stable equilibrium of a basic continuous-time consensus algorithm. Then it proposes a so-called “gossip algorithm”, which achieves global asymptotic synchronization on the circle with probability 1 for a large class of interconnections, without using auxiliary variables, thanks to the introduction of randomness in the system.

In this paper, we generalize the notion of persistence, which has been originally introduced for two-dimensional formations, to R^d for d>=3, seeking to provide a theoretical framework for real world applications, which often are in three-dimensional space as opposed to the plane. Persistence captures the desirable property that a formation moves as a cohesive whole when certain agents maintain their distances from certain other agents. We verify that many of the properties of rigid and/or persistent formations established in R^2 are also valid for higher dimensions. Analysing the closed subgraphs and directed paths in persistent graphs, we derive some further properties of persistent formations. We also provide an easily checkable necessary condition for persistence. We then turn our attention to consider some practical issues raised in multi-agent formation control in three-dimensional space. We display a new phenomenon, not present in R^2, whereby subsets of agents can behave in a problematic way. When this behaviour is precluded, we say that the graph depicting the multi-agent formation has structural persistence. In real deployment of controlled multi-agent systems, formations with underlying structurally persistent graphs are of interest. We analyse the characteristics of structurally persistent graphs and provide a streamlined test for structural persistence. We study the connections between the allocation of degrees of freedom (DOFs) across agents and the characteristics of persistence and/or structural persistence of a directed graph. We also show how to transfer DOFs among agents, when the formation changes with new agent(s) added, to preserve persistence and/or structural persistence.

We consider in this paper formations of autonomous agents moving in a two-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant and the problem is to determine if one can guarantee that the distance between every pair of agents (even those not explicitly maintained) remains constant, resulting in the persistence of the formation shape. We provide here a theoretical framework for studying this problem. We describe the constraints on the distance between agents by a directed graph and define persistent graphs. A graph is persistent if the shapes of almost all corresponding agent formations persist. Although persistence is related to the classical notion of rigidity, these are two distinct notions. We derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define minimal persistence (persistence with the least possible number of edges), and we apply our results to the interesting special case of cycle-free graphs. Copyright (C) 2006 John Wiley & Sons, Ltd.

We prove distortion theorems for rational functions without poles or zeros in simply connected domains. The distance between the values u(z 1) and u(z 2) assumed by such a rational function is limited by its degree and by the hyperbolic distance between z 1 and z 2. For discs and halfplanes, the case of equality in these estimates is fully explored. These results have appUcations in control theory which are illustrated by examples.

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.

In this paper, we consider the conditional affine eigenvalue problem lambda x = Ax + b, lambda is an element of R, x >= 0, parallel to x parallel to = 1, where A is an n x n nonnegative matrix, b a nonnegative vector, and parallel to center dot parallel to a monotone vector norm. Under suitable hypotheses, we prove the existence and uniqueness of the solution (lambda(*), x(*)) and give its expression as the Perron root and vector of a matrix A + bc(*)(T) where c(*) has a maximizing property depending on the considered norm. The equation x (Ax + b)/ parallel to Ax + b parallel to has then a unique nonnegative solution, given by the unique Perron vector of A + bc(*)(T). (c) 2005 Elsevier Inc. All rights reserved.

We introduce a concept of {similarity} between vertices of directed graphs. Let GA and GB be two directed graphs with, respectively, nA and nB vertices. We define an nB \times nA similarity matrix S whose real entry sij expresses how similar vertex j (in GA) is to vertex i (in GB): we say that sij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of Sk+1 = BSkAT + BTSkA, where A and B are adjacency matrices of the graphs and S0 is a matrix whose entries are all equal to 1. In the special case where GA = GB = G, the matrix S is square and the score sij is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a nonnegative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.

We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our results we prove that the problem of determining if the set of all products of two 47 x 47 matrices with nonnegative rational entries is bounded is undecidable.

We prove that there exist (infinitely many) values of the real parameters a and b for which the matrices ( \begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array} \right) \qquad \mbox{ and } \qquad b \left( \begin{array}{ll} 1 & 0 \\ 1 & 1 \end{array} \right) $$ have the following property: all infinite periodic products of the two matrices converge to zero, but there exists a nonperiodic product that doesn't. Our proof is self-contained and fairly elementary; it uses only elementary facts from the theory of formal languages and from linear algebra. It is not constructive in that we do not exhibit any explicit values of a and b with the stated property; the problem of finding explicit matrices with this property remains open.

We perform an analytical sensitivity analysis for a model of a continuous-time branching process evolving on a fixed network. This allows us to determine the relative importance of the model parameters to the growth of the population on the network. We then apply our results to the early stages of an influenza-like epidemic spreading among a set of cities connected by air routes in the United States. We also consider vaccination and analyze the sensitivity of the total size of the epidemic with respect to the fraction of vaccinated people. Our analysis shows that the epidemic growth is more sensitive with respect to transmission rates within cities than travel rates between cities. More generally, we highlight the fact that branching processes offer a powerful stochastic modeling tool with analytical formulas for sensitivity which are easy to use in practice., Comment: 17 pages (30 with SI), Journal of Complex Networks, Feb 2015

International audience; During the past few decades, technologies such as remote sensing, geographical information systems, and global positioning systems have transformed the way the distribution of human population is studied and modeled in space and time. However, the mapping of populations remains constrained by the logistics of censuses and surveys. Consequently, spatially detailed changes across scales of days, weeks, or months, or even year to year, are difficult to assess and limit the application of human population maps in situations in which timely information is required, such as disasters, conflicts, or epidemics. Mobile phones (MPs) now have an extremely high penetration rate across the globe, and analyzing the spatiotemporal distribution of MP calls geolocated to the tower level may overcome many limitations of census-based approaches, provided that the use of MP data is properly assessed and calibrated. Using datasets of more than 1 billion MP call records from Portugal and France, we show how spatially and temporarily explicit estimations of population densities can be produced at national scales, and how these estimates compare with outputs produced using alternative human population mapping methods. We also demonstrate how maps of human population changes can be produced over multiple timescales while preserving the anonymity of MP users. With similar data being collected every day by MP network providers across the world, the prospect of being able to map contemporary and changing human population distributions over relatively short intervals exists, paving the way for new applications and a near real-time understanding of patterns and processes in human geography.

During recent years, it has been shown that a number of problems in matrix theory are NP-hard, including robust nonsingularity, robust stability, robust positive semidefiniteness, robust bounded norm, state feedback stabilization with structural and norm constraints, etc. In this paper, we use standard bounds on empirical probabilities as well as recent results from statistical learning theory on the VC-dimension of families of sets defined by a finite number of polynomial inequalities, to show that for each of the above problems, as well as for still more general and more difficult problems, there exists a polynomial-time randomized algorithm that can provide a yes or no answer to arbitrarily small levels of accuracy and confidence.

We show that the boundedness of the set of all products of a given pair Sigma of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius rho(Sigma) is not computable: because testing whether rho(Sigma)less than or equal to1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called "finiteness conjecture". Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable. (C) 2000 Elsevier Science B.V. All rights reserved.

The purpose of this paper is twofold: (a) to provide a tutorial introduction to some key concepts from the theory of computational complexity, highlighting their relevance to systems and control theory, and (b) to survey the relatively recent research activity lying at the interface between these fields. We begin with a brief introduction to models of computation, the concepts of undecidability, polynomial-time algorithms, NP-completeness, and the implications of intractability results. We then survey a number of problems that arise in systems and control theory, some of them classical, some of them related to current research. We discuss them from the point of view of computational complexity and also point out many open problems. In particular, we consider problems related to stability or stabilizability of linear systems with parametric uncertainty, robust control, time-varying linear systems, nonlinear and hybrid systems, and stochastic optimal control.

The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral radius is traditionally called the Lyapunov exponent. When one performs these products in the max-algebra, we obtain quantities that measure the performance of discrete event systems. We show that approximating the lower and average max-algebraic spectral radii is NP-hard.

In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of hybrid systems in which the state space is partitioned into two halfspaces, and the dynamics in each halfspace correspond to a different linear system.

One of the open problems in the max-plus-algebraic system theory for discrete event systems is the minimal realization problem. In this paper we present some results in connection with the minimal realization problem in the max-plus algebra. First we characterize the minimal system order of a max-linear discrete event system. We also introduce a canonical representation of the impulse response of a max-linear discrete event system. Next we consider a simplified version of the general minimal realization problem: the boolean minimal realization problem, i.e., we consider models in which the entries of the system matrices are either equal to the max-plus-algebraic zero element or to the max-plus-algebraic identity element. We give a lower bound for the minimal system order of a max-plus-algebraic boolean discrete event system. We show that the decision problem that corresponds to the boolean realization problem (i.e., deciding whether or not a boolean realization of a given order exists) is decidable, and that the boolean minimal realization problem can be solved in a number of elementary operations that is bounded from above by an exponential of the square of (any upper bound of) the minimal system order. We also point out some open problems, the most important of which is whether or not the boolean minimal realization problem can be solved in polynomial time.

We show that some basic linear control design problems are NP-hard, implying that, unless P=NP, they cannot be solved by polynomial time algorithms. The problems that we consider include simultaneous stabilization by output feedback, stabilization by state or output feedback in the presence of bounds on the elements of the gain matrix, and decentralized control. These results are obtained by first showing that checking the existence of a stable matrix in an interval family of matrices is an NP-hard problem.

A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal if it is k-mortal for some finite k. We show that the problem of deciding whether a pair of 48 × 48 integer matrices is mortal is undecidable, and that the problem of deciding, for a given k, whether a pair of matrices is k-mortal is NP-complete.

We analyze the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices are not approximable in polynomial time, and that two related quantities—the lower spectral radius and the largest Lyapunov exponent—are not algorithmically approximable.

The use of a necessarily approximate system model for the design of a feedback controller for an actual plant introduces strictures on the quality of the model which are different from those pertaining in open loop. This has been the focus of a raft of recent papers on closed loop modelling, model validation, and iterative control design where appropriate measures of approximation quality have been proposed, analysed and implemented. Our attention here will concentrate on underlying implicit or understood questions of an algebraic nature which need to be resolved prior to any quantitative analysis of approximation. For example, it should be evident that a model P is useful as a design input for a controller for the actual plant P only if the pair ([Pcirc], P) is simultaneously stabilizable. Yet this question has not really been asked. For given P and T we characterize the set of admissible models {[Pcirc]}, where admissible means that a controller designed from [Pcirc] and T yields a stable closed loop. N...

Networks are commonly used to define underlying interaction structures where infections, information, or other quantities may spread. Although the standard approach has been to aggregate all links into a static structure, some studies suggest that the time order in which the links are established may alter the dynamics of spreading. In this paper, we study the impact of the time ordering in the limits of flow on various empirical temporal networks. By using a random walk dynamics, we estimate the flow on links and convert the original undirected network (temporal and static) into a directed flow network. We then introduce the concept of flow motifs and quantify the divergence in the representativity of motifs when using the temporal and static frameworks. We find that the regularity of contacts and persistence of vertices (common in email communication and face-to-face interactions) result on little differences in the limits of flow for both frameworks. On the other hand, in the case of communication within a dating site (and of a sexual network), the flow between vertices changes significantly in the temporal framework such that the static approximation poorly represents the structure of contacts. We have also observed that cliques with 3 and 4 vertices con- taining only low-flow links are more represented than the same cliques with all high-flow links. The representativity of these low-flow cliques is higher in the temporal framework. Our results suggest that the flow between vertices connected in cliques depend on the topological context in which they are placed and in the time sequence in which the links are established. The structure of the clique alone does not completely characterize the potential of flow between the vertices.

This chapter presents a simple and intuitive stochastic model of a temporal network and investigate how a simulated infection co-evolves with the temporal structures, focusing on the growth dynamics of the epidemics. The model assumes no underlying topological structure and is only constrained by the time between two consecutive events of vertex activation, hereafter called vertex inter-event time. The network model consists of random activations of a vertex according to a pre-defined vertex inter-event time distribution. The vertices active at a given time are randomly connected in pairs during one time unit. The link is then destroyed and the vertices set to the inactive state. The infection event occurs through this link if one of the vertices is in an infective state. This model has been studied by using a susceptible infective dynamics with one (SI) and two (SII) infective stages. The first dynamics is motivated for being an upper limit case, where once infected, the vertex continues infecting at every contact. The second dynamics is more realistic and corresponds to a model of HIV spreading including an acute (high infectivity) and chronic (low infectivity) stages of infection with different periods. If the second stage is set to zero in the SII model, we recover the susceptible infected recovered (SIR).

Let f be an analytic function in the open unit disk that assumes the values 0 and 1 at least once and an unequal number of rimes in a disk of radius 1 10-5 entered at the origin. We prove that fmust assume the value 0 or 1 elsewhere in the unit disk. This result is motivated by a control engineering design problem which is also presented.

A stable linear system controlled by a proportional controller is closed-loop stable provided the controller has sufficiently small gain. If the system has an unstable zero then any proportional controller with sufficiently large gain is destabilizing. In this note we give an upper bound for the gain of stabilizing proportional controllers of stable systems that have one or more unstable zeros.

We study the computational complexity of a general consensus problem for switched systems. A set of n × n stochastic matrices {P 1 , …, P k } is a consensus set if for every switching map τ : ℕ → {1, …, k} and for every initial state x(0), the sequence of states defined by x(t + 1) = P τ(t) x(t) converges to a state whose entries are all identical. We show in this paper that, unless P = NP, the problem of determining if a set of matrices is a consensus set cannot be decided in polynomial-time. As a consequence, unless P = NP, it is not possible to give efficiently checkable necessary and sufficient conditions for consensus. This provides a possible explanation for the absence of such conditions in the current literature on consensus. On the positive side, we provide a simple algorithm which checks whether {P 1 , …, P k } is a consensus set in a number of operations which scales as a doubly exponential in n.

We study fifteen months of human mobility data for one and a half million individuals and find that human mobility traces are highly unique. In fact, in a dataset where the location of an individual is specified hourly, and with a spatial resolution equal to that given by the carrier's antennas, four spatio-temporal points are enough to uniquely identify 95% of the individuals. We coarsen the data spatially and temporally to find a formula for the uniqueness of human mobility traces given their resolution and the available outside information. This formula shows that the uniqueness of mobility traces decays approximately as the [1 over 10] power of their resolution. Hence, even coarse datasets provide little anonymity. These findings represent fundamental constraints to an individual's privacy and have important implications for the design of frameworks and institutions dedicated to protect the privacy of individuals., Communauté française de Belgique (Actions de Recherche Concertée. Grant 09/14-017)

Complex networks are often constructed by aggregating empirical data over time, such that a link represents the existence of interactions between the endpoint nodes and the link weight represents the intensity of such interactions within the aggregation time window. The resulting networks are then often considered static. More often than not, the aggregation time window is dictated by the availability of data, and the effects of its length on the resulting networks are rarely considered. Here, we address this question by studying the structural features of networks emerging from aggregating empirical data over different time intervals, focussing on networks derived from time-stamped, anonymized mobile telephone call records. Our results show that short aggregation intervals yield networks where strong links associated with dense clusters dominate; the seeds of such clusters or communities become already visible for intervals of around one week. The degree and weight distributions are seen to become stationaryaround a few days and a few weeks, respectively. An aggregation interval of around 30 days results in the stablest similar networks when consecutive windows are compared. For longer intervals, the effects of weak or random links become increasingly stronger, and the average degree of the network keeps growing even for intervals up to 180 days. The placement of the time window is also seen to affect the outcome: for short windows, different behavioural patterns play a role during weekends and weekdays, and for longer windows it is seen that networks aggregated during holiday periods are significantly different.

The problem of the simultaneous stabilizability of a finite family of single-input, single-output time-invariant systems by a time- invariant controller is studied. The link between stabilization and avoidance is shown and is used to derive necessary conditions for the simultaneous stabilization of k plants. These necessary conditions are proved to be, in general, not sufficient. This result also disproves a long- standing conjecture on the stabilizability condition of a single plant with a stable minimum phase controller. The main result is to show that, unlike the case of two plants, the existence of a simultaneous stabilizing controller for more than two plants is not guaranteed by the existence of a controller such that the closed loops have no real unstable poles.

Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people's movements and thus reveal their trajectories and spatial behaviour. Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks. In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology. In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks. We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes. Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated., This preprint version combines paper and supplemenatary material of published version. Original title "Beyond Space For Spatial Networks" changed for journal