Search

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.

Given a family of real or complex monic polynomials of fixed degree with one affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or root abscissa (largest real part of the roots). We give constructive methods for efficiently computing the globally optimal value as well as an optimal polynomial when the optimal value is attained and an approximation when it is not. An optimal polynomial can always be chosen to have at most two distinct roots in the real case and just one distinct root in the complex case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems.

We consider the problem of inferring meaningful spatial information in networks from incomplete information on the connection intensity between the nodes of the network. We consider two spatially distributed networks: a population migration flow network within the US, and a network of mobile phone calls between cities in Belgium. For both networks we use the eigenvectors of the Laplacian matrix constructed from the link intensities to obtain informative visualizations and capture natural geographical subdivisions. We observe that some low order eigenvectors localize very well and seem to reveal small geographically cohesive regions that match remarkably well with political and administrative boundaries. We discuss possible explanations for this observation by describing diffusion maps and localized eigenfunctions. In addition, we discuss a possible connection with the weighted graph cut problem, and provide numerical evidence supporting the idea that lower order eigenvectors point out local cuts in the network. However, we do not provide a formal and rigorous justification for our observations., 15 pages

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

In this paper, we present several descent methods that can be applied to nonnegative matrix factorization and we analyze a recently developed fast block coordinate method called Rank-one Residue Iteration (RRI). We also give a comparison of these different methods and show that the new block coordinate method has better properties in terms of approximation error and complexity. By interpreting this method as a rank-one approximation of the residue matrix, we prove that it \(converges\) and also extend it to the nonnegative tensor factorization and introduce some variants of the method by imposing some additional controllable constraints such as: sparsity, discreteness and smoothness.

In this study we analyze one year of anonymized telecommunications data for over one million customers from a large European cellphone operator, and we investigate the relationship between people's calls and their physical location. We discover that more than 90% of users who have called each other have also shared the same space (cell tower), even if they live far apart. Moreover, we find that close to 70% of users who call each other frequently (at least once per month on average) have shared the same space at the same time - an instance that we call co-location. Co-locations appear indicative of coordination calls, which occur just before face-to-face meetings. Their number is highly predictable based on the amount of calls between two users and the distance between their home locations - suggesting a new way to quantify the interplay between telecommunications and face-to-face interactions., AT & T Foundation, National Science Foundation (U.S.) (grant number 0735956), Singapore-MIT Alliance for Research and Technology, General Electric Company, Volkswagen Foundation, IBM Research, Orange Labs (France), France. Société Nationale des Chemins de fer français, Ente nazionale per l'energia elettrica

This paper considers problems of simultaneous stabilization using a linear time-invariant compensator incorporated with a sampler and zeroth-order hold function. It is shown that this controller strongly stabilizes a number of plants which may not be stabilizable by a conventional linear time-invariant controller. A controller design procedure is given which is illustrated by an example.

We study a simple continuous-time multi-agent system related to Krause's model of opinion dynamics: each agent holds a real value, and this value is continuously attracted by every other value differing from it by less than 1, with an intensity proportional to the difference.

Given a family of real or complex monic polynomials of fixed degree with one fixed affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or abscissa (largest real part of the roots). We give constructive methods for finding globally optimal solutions to these problems. In the real case, our methods are based on theorems that extend results in Raymond Chen's 1979 PhD thesis. In the complex case, our methods are based on theorems that are new, easier to state but harder to prove than in the real case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems.

In this article, we examine the existence of regions and borders in Belgium by means of an original data set of more than 200 million mobile communications and a mathematical method which allows networks to be divided into coherent groups in a natural and automatic manner. A geography of mobile communications is thus proposed based on the relative frequency of communications as well as their average duration. In the case of the relative frequency of communications, we obtain a map of Belgium composed of 17 groups or “telephone areas” that each contain only adjacent municipalities. On this first map, the area of Brussels is the only one which runs across the linguistic border and covers the three institutional regions of the country. In the case of the average duration of communications, we obtain a group in the north and a group in the south of the country. These two groups concentrate within themselves almost 98% of telephone calls; only 2% of communications are from one group to the other. The group in the south includes the 19 municipalities of Brussels, all of the municipalities in the Walloon region as well as eight municipalities with facilities located in the Flemish region. In particular, all of the municipalities with facilities in the outskirts of Brussels (with the exception of Wemmel) are part of the group in the south of the country.

Dans cet article, nous explorons l’existence de regions et de frontieres en Belgique au moyen d’un jeu de donnees original de plus de 200 millions de communications mobiles et d’une methode mathematique qui permet de decouper de maniere naturelle et automatique des reseaux en groupes coherents. Une geographie des communications mobiles est ainsi proposee sur la base de la frequence relative des communications ainsi que de leur duree moyenne. Dans le cas de la frequence relative des communications, nous obtenons une carte de Belgique composee de 17 groupes ou « bassins telephoniques » spatialement bien ancres, aux communes etonnamment toutes adjacentes. Sur cette premiere carte, le bassin de Bruxelles est le seul qui traverse largement la frontiere linguistique et couvre les trois regions institutionnelles du pays. Dans le cas de la duree moyenne des communications, nous obtenons un groupe au nord et un groupe au sud du pays. Ces deux groupes concentrent en leur sein pres de 98 % des appels telephoniques ; seuls 2 % des communications passent d’un groupe a l’autre. Le groupe du sud comprend les 19 communes de Bruxelles, toutes les communes de la region Wallonne ainsi que huit communes a facilites situees en region flamande. En particulier, toutes les communes a facilites de la peripherie bruxelloise (a l’exception de Wemmel) font partie du groupe du sud du pays.

In dit artikel onderzoeken we het bestaan van regio’s en van grenzen in Belgie op basis van een originele databank die gegevens bevat van meer dan 200 miljoen mobiele telefoongesprekken en van een wiskundige methode die toelaat op automatische en natuurlijke wijze netwerken in coherente groepen te verdelen. Op die manier kan een geografie van mobiel telefoonverkeer voorgesteld worden op basis van de relatieve frequenties van de telefoongesprekken en hun gemiddelde duur. Als we de relatieve frequentie van de gesprekken als criterium gebruiken, krijgen we een kaart van Belgie die bestaat uit 17 groepen of “telefoonbassins” die ruimtelijk verankerd zijn in gemeenten die allemaal verbazend aangrenzend zijn. Op deze eerste kaart is het enkel het bassin van Brussel dat de taalgrens nadrukkelijk doorbreekt en de drie institutionele gewesten van het land bedekt. Als we de gemiddelde duur van de gesprekken als criterium hanteren, krijgen we een groep in het noorden en een groep in het zuiden van het land. Binnen deze twee groepen vindt ongeveer 98% van de gesprekken plaats; slechts 2% van het telefoonverkeer gaat van de ene groep naar de andere. De zuidelijke groep bevat de 19 Brusselse gemeenten, alle gemeenten van het Waals Gewest en acht faciliteitengemeenten die in het Vlaams Gewest liggen. Het is opmerkelijk dat alle faciliteitengemeenten van de Brusselse rand (met uitzondering van Wemmel) deel uitmaken van de groep van het zuiden van het land.

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

We study a simple continuous-time multi-agent system related to Krause's model of opinion dynamics: each agent holds a real value, and this value is continuously attracted by every other value differing from it by less than 1, with an intensity proportional to the difference. We prove convergence to a set of clusters, with the agents in each cluster sharing a common value, and provide a lower bound on the distance between clusters at a stable equilibrium, under a suitable notion of multi-agent system stability. To better understand the behavior of the system for a large number of agents, we introduce a variant involving a continuum of agents. We prove, under some conditions, the existence of a solution to the system dynamics, convergence to clusters, and a non-trivial lower bound on the distance between clusters. Finally, we establish that the continuum model accurately represents the asymptotic behavior of a system with a finite but large number of agents., 25 pages, 2 figures, 11 tex files and 2 eps files

We consider a network of mobile phone customers aggregated by geographical proximity. We analyze the anonymous communication patterns of 2.5 million customers of a Belgian mobile phone operator. Grouping customers by billing address, we build a social network of cities, that consists of communication between 571 cities in Belgium. We show that inter-city communication intensity is characterized by a gravity model: the communication intensity between two cities is proportional to the product of the size of the population of these cities divided by the square of their distance.

We study the effect of latency on binary-choice opinion formation models. Latency is introduced into the models as an additional dynamic rule: after a voter changes its opinion, it enters a waiting period of stochastic length where no further changes take place. We first focus on the voter model and show that as a result of introducing latency, the average magnetization is not conserved, and the system is driven toward zero magnetization, independently of initial conditions. The model is studied analytically in the mean-field case and by simulations in one dimension. We also address the behavior of the Majority Rule model with added latency, and show that the competition between imitation and latency leads to a rich phenomenology.

We study the propagation of information in social networks. To do so, we focus on a cascade model where nodes are infected with {probability $p_1$ after their first contact with the information and with probability $p_2$ at all subsequent contacts.} The diffusion starts from one random node and leads to a cascade of infection. It is shown that first and {subsequent} trials play different roles in the propagation and that the size of the cascade depends in a non-trivial way on $p_1$, $p_2$ and on the network structure. Second trials are shown to amplify the propagation in dense parts of the network while first trials are {dominant for the exploration of} new parts of the network and launching new seeds of infection., 7 pages, 6 figures

Book abstract: Setting out core theory and reviewing a range of new methods, theoretical problems and applications, this handbook shows how hybrid dynamical systems can be modelled and understood. 60 expert authors involved in the recent research activities and industrial application studies provide practical insights on topics ranging from the theoretical investigations over computer-aided design to applications in energy management and the process industry. Structured into three parts, the book opens with a thorough introduction to hybrid systems theory, illustrating new dynamical phenomena through numerous examples. Part II then provides a survey of key tools and tool integration activities. Finally, Part III is dedicated to applications, implementation issues and system integration, considering different domains such as industrial control, automotive systems and digital networks. Three running examples are referred to throughout the book, together with numerous illustrations, helping both researchers and industry professionals to understand complex theory, recognise problems and find appropriate solutions.

We study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by less than one. We give a new proof of convergence into clusters of agents, with all agents in the same cluster holding the same opinion. We then introduce a particular notion of equilibrium stability and provide lower bounds on the inter-cluster distances at a stable equilibrium. To better understand the behavior of the system when the number of agents is large, we also introduce and study a variant involving a continuum of agents, obtaining partial convergence results and lower bounds on inter-cluster distances, under some mild assumptions.

Researchers have been unable to predict the large-scale features of aggregate social networks. We analyze the anonymous communications patterns of 2.5 million customers of a Belgian mobile phone operator. With these communications, we construct the social network of the customers, that we call microscopic network. Grouping customers together by billing address city, we obtain a social network of cities, which we call the macroscopic network, is built from 571 towns and cities in Belgium. Using the mobile phone network, we are able to show that the macroscopic network has both a degree distribution and edge weight distribution with lognormal characteristics. We find that inter-city communications can be characterized by a gravity model: the intensity of communication between two cities is proportional to the product of the two populations divided by the square of the distance between them. Furthermore, we observe that intra-urban communications scale superlinearly with city population.

We propose a new method to compute the joint spectral radius and the joint spectral subradius of a set of matrices. We first restrict our attention to matrices that leave a cone invariant. The accuracy of our algorithm, depending on geometric properties of the invariant cone, is estimated. We then extend our method to arbitrary sets of matrices by a lifting procedure, and we demonstrate the efficiency of the new algorithm by applying it to several problems in combinatorics, number theory, and discrete mathematics.

In this chapter we analyze a recent conjecture stating that the finiteness property holds for pairs of binary matrices. We show that the finiteness property holds for all pairs of binary matrices if and only if it holds for all sets of nonnegative rationalmatrices.We provide a similar result for matrices with positive and negative entries. We finally prove the conjecture for 2×2 matrices.

Overlap-free words are words over the binary alphabet $A=\{a, b\}$ that do not contain factors of the form $xvxvx$, where $x \in A$ and $v \in A^*$. We analyze the asymptotic growth of the number $u_n$ of overlap-free words of length $n$ as $ n \to \infty$. We obtain explicit formulas for the minimal and maximal rates of growth of $u_n$ in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of certain sets of matrices of dimension $20 \times 20$. Using these descriptions we provide new estimates of the rates of growth that are within 0.4% and $0.03 %$ of their exact values. The best previously known bounds were within 11% and 3% respectively. We then prove that the value of $u_n$ actually has the same rate of growth for ``almost all'' natural numbers $n$. This ``average'' growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. In order to obtain our estimates, we introduce new algorithms to compute spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest., Comment: 26 pages, 2 figures

We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks. ., 6 pages, 5 figures, 1 table; new version with new figures in order to clarify our method, where we look more carefully at the role played by the ordering of the nodes and where we compare our method with that of Wakita and Tsurumi

In this paper, we analyze statistical properties of a communication network constructed from the records of a mobile phone company. The network consists of 2.5 million customers that have placed 810 millions of communications (phone calls and text messages) over a period of 6 months and for whom we have geographical home localization information. It is shown that the degree distribution in this network has a power-law degree distribution $k^{-5}$ and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases like $d^{-2}$, where $d$ is the distance between the customers. We also consider the geographical extension of communication triangles and we show that communication triangles are not only composed of geographically adjacent nodes but that they may extend over large distances. This last property is not captured by the existing models of geographical networks and in a last section we propose a new model that reproduces the observed property. Our model, which is based on the migration and on the local adaptation of agents, is then studied analytically and the resulting predictions are confirmed by computer simulations., Comment: 17 pages, 8 figures

We propose two simple upper bounds for the joint spectral radius of sets of nonnegative matrices. These bounds, the joint column radius and the joint row radius, can be computed in polynomial time as solutions of convex optimization problems. We show that for general matrices these bounds are within a factor 1/n of the exact value, where n is the size of the matrices. Moreover, for sets of matrices with independent column uncertainties of with independent row uncertainties, the corresponding bounds coincide with the joint spectral radius. In these cases, the joint spectral radius is also given by the largest spectral radius of the matrices in the set. As a byproduct of these results, we propose a polynomial-time technique for solving Boolean optimization problems related to the spectral radius. We also consider economics and engineering applications of our results which were never considered practice due to their intrinsic computational complexity.

Overlap-free words are words over the alphabet A = {a, b} that do not contain factors of the form xvxvx, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlapfree words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03% of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that un actually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it.

We consider local leaders in random uncorrelated networks, i.e. nodes whose degree is higher or equal than the degree of all of their neighbors. An analytical expression is found for the probability of a node of degree $k$ to be a local leader. This quantity is shown to exhibit a transition from a situation where high degree nodes are local leaders to a situation where they are not when the tail of the degree distribution behaves like the power-law $\sim k^{-\gamma_c}$ with $\gamma_c=3$. Theoretical results are verified by computer simulations and the importance of finite-size effects is discussed., Comment: 4 pages, 2 figures

We deal with the issue of automatic discovery of similar words (synonyms and near-synonyms) from different kinds of sources: from large corpora of documents, from the Web, and from monolingual dictionaries. We present in detail three algorithms that extract similar words from a large corpus of documents and consider the specific case of the World Wide Web. We then describe a recent method of automatic synonym extraction in a monolingual dictionary. The method is based on an algorithm that computes similarity measures between vertices in graphs. We use the 1913 Webster’s Dictionary and apply the method on four synonym queries. The results obtained are analyzed and compared with those obtained by two other methods.

Statistical Learning Theory: A Pack-based Strategy for Uncertain Feasibility and Optimization Problems.- UAV Formation Control: Theory and Application.- Electrical and Mechanical Passive Network Synthesis.- Output Synchronization of Nonlinear Systems with Relative Degree One.- On the Computation of Optimal Transport Maps Using Gradient Flows and Multiresolution Analysis.- Realistic Anchor Positioning for Sensor Localization.- Graph Implementations for Nonsmooth Convex Programs.- When Is a Linear Continuous-time System Easy or Hard to Control in Practice?.- Metrics and Morphing of Power Spectra.- A New Type of Neural Computation.- Getting Mobile Autonomous Robots to Form a Prescribed Geometric Arrangement.- Convex Optimization in Infinite Dimensional Spaces.- The Servomechanism Problem for SISO Positive LTI Systems.- Passivity-based Stability of Interconnection Structures.- Identification of Linear Continuous-time Systems Based on Iterative Learning Control.- A Pontryagin Maximum Principle for Systems of Flows.- Safe Operation and Control of Diesel Particulate Filters Using Level Set Methods.- Robust Control of Smart Material-based Actuators.- Behaviors Described by Rational Symbols and the Parametrization of the Stabilizing Controllers.

It has become increasingly apparent this last decade that many problems in systems and control are NP-hard and, in some cases, undecidable. The inherent complexity of some of the most elementary problems in systems and control points to the necessity of using alternative approximate techniques to deal with problems that are unsolvable or intractable when exact solutions are sought.

We consider a simple dynamical model of agents distributed on the real line. The agents have a limited vision range and they synchronously update their positions by moving to the average position of the agents that are within their vision range. This dynamical model was initially introduced in the social science literature as a model of opinion dynamics and is known there as the “Krause model”. It gives rise to surprising and partly unexplained dynamics that we describe and discuss in this paper. One of the central observations is the 2R-conjecture: when sufficiently many agents are distributed on the real line and have their position evolve according to the above dynamics, the agents eventually merge into clusters that have inter-cluster distances roughly equal to 2R (R is the vision range of the agents). This observation is supported by extensive numerical evidence and is robust under various modifications of the model. It is easy to see that clusters need to be separated by at least R. On the other hand, the unproved bound 2R that is observed in practice can probably only be obtained by taking into account the specifics of the model's dynamics. In this paper, we study these dynamics and consider a number of issues related to the 2R conjecture that explicitly uses the model's dynamics. In particular, we provide bounds for the vision range that lead all agents to merge into only one cluster, we analyze the relations between agents on finite and infinite intervals, and we introduce a notion of equilibrium stability for which clusters of equal weights need to be separated by at least 2R to be stable. These results, however, do not prove the conjecture. To understand the system behavior for a large agent density, we also consider a version of the model that involves a continuum of agents. We study properties of this continuous model and of its equilibria, and investigate the connections between the discrete and continuous versions.

We consider the problem of determining the proportion of edges that are discovered in an Erdos-Renyi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a new way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies., 12 pages, 8 figures (18 .eps files)

Motivated by [1], [2] and [3], we consider here formations of autonomous agents in a 2-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 structure of the formation will persist, i.e., if the distance between any pair of agents will remain constant. A natural way to represent such a formation is to use a directed graph. We provide a theoretical framework for this problem, and give a formal definition of persistent graphs (a graph is persistent if almost all corresponding agents formations persist). Note that although persistence is related to rigidity (concerning which much is known [4]), these are two distinct notions. We then derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define the notion of minimal persistence (persistence with least number of edges), and eventually, we apply these notion to the interesting special case of cycle-free graphs.

We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values asynchronously and form weighted averages with (possibly outdated) values possessed by their neighbors. We overview existing convergence results, and establish some new ones, for the case of unbounded intercommunication intervals.

The authors disprove conjectures on simultaneous stabilizability conditions by showing 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. An example of a plant which has the even interlacing property but which is not stabilizable by a bistable controller is presented. >

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears in a number of application contexts, in particular it characterizes the growth rate of switched linear systems. The joint spectral radius is notoriously difficult to compute and to approximate. We introduce in this paper the first polynomial time approximations of guaranteed precision. We provide an approximation (p) over cap that is based on ellipsoid norms that can be computed by convex optimization and that is such that the joint spectral radius belongs to the interval [(p) over cap/ rootn (p) over cap] where n is the dimension of the matrices. We also provide a simple approximation for the special case where the entries of all the matrices are non-negative; in this case the approximation is proved to be within a factor at most m (m is the number of matrices) of the exact value.

We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems., 10 pages

In this paper, we introduce a procedure for approximating the joint spectral radius of a finite set of matrices with arbitrary precision. Our approximation procedure is based on semidefinite liftings and can be implemented in a recursive way. For two matrices even the first step of the procedure gives an approximation, whose relative quality is at least 1/sq.2, that is, more than 70%. The subsequent steps improve the quality but also increase the dimension of the auxiliary problem from which this approximation can be found. In an improved version of our approximation procedure we show how a relative quality of (1/sq.2exp.1/k) can be obtained by evaluating the spectral radius of a single matrix of dimension nexp.k(nexp.k+1)/2 where n is the dimension of the initial matrices. This result is computationally optimal in the sense that it provides an approximation of relative quality 1-E in time polynomial in nexp.1/E and it is known that, unless P=NP, no such algorithm is possible that runs in time polynomial in n and 1/E. For the special case of matrices with non-negative entries we prove that (1/2)exp.1/k pexp.1/k (A1exp.k + A2exp.k)

We analyse the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalised 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. As a corollary of these results we show that: 1) the problem of deciding if all possible products of two given matrices are stable is NP-hard, 2) the problem of deciding if at, least one product of two given matrices is stable is undecidable.

The authors study the following problem: 'under what condition(s) is it possible to find a single controller which stabilizes k single-input-single-output (SISO) linear time-invariant plants p/sub i/(s) (i=l,. . .,k)?'. They show that the problem admits a solution if and only if an avoidance condition in the complex plane is satisfied, and this result is used to derive a sufficient condition for k plants to be simultaneously stabilizable. >

The use of an identified 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 identification. For example, a model P/spl circ/ is admissible for the design of a controller for the actual plant P only if the pair (P/spl circ/, P) is simultaneously stabilizable. This paper addresses the question of the quality of a model to be used for control design, by analysing the interplay between the plant P, the designed closed loop system T and the set of admissible models {P/spl circ/}. For given P and T we characterize the set of admissible models {P/spl circ/}, where admissible means that a controller designed from P/spl circ/ and T yields a stable closed loop. Necessary conditions on (P, T) are derived for this set to be nonempty.

We show that the simultaneous stabilization question: When are three linear systems stabilizable by the same controller? cannot be solved by a semialgebraic set description nor be answered by computational machines.

The condition under which it is possible to find a single controller that stabilizes k single-input single-output linear time-invariant systems p/sub i/(s) (i=1,. . .,k) is investigated. The concept of avoidance in the complex plane is introduced and used to derive a sufficient condition for k systems to be simultaneously stabilizable. A method for constructing a simultaneous stabilizing controller is also provided and is illustrated by an example. >

In this paper we study problems such as: given a discrete time dynamical system of the form x(t + 1)= f(x(t)) where f: R-n --> R-n is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n greater than or equal to2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that AM-activity and Stability become decidable in dimension 1 for continuous functions. (C) 2001 Elsevier Science B.V. All rights reserved.