Search

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.

Opinion evolution and judgment revision are mediated through social influence. Based on a large crowdsourced in vitro experiment (n=861), it is shown how a consensus model can be used to predict opinion evolution in online collective behaviour. It is the first time the predictive power of a quantitative model of opinion dynamics is tested against a real dataset. Unlike previous research on the topic, the model was validated on data which did not serve to calibrate it. This avoids to favor more complex models over more simple ones and prevents overfitting. The model is parametrized by the influenceability of each individual, a factor representing to what extent individuals incorporate external judgments. The prediction accuracy depends on prior knowledge on the participants' past behaviour. Several situations reflecting data availability are compared. When the data is scarce, the data from previous participants is used to predict how a new participant will behave. Judgment revision includes unpredictable variations which limit the potential for prediction. A first measure of unpredictability is proposed. The measure is based on a specific control experiment. More than two thirds of the prediction errors are found to occur due to unpredictability of the human judgment revision process rather than to model imperfection., Accepted for publication in PLOS ONE (2016)

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.

In this paper, we review some advances made recently in the study of mobile phone datasets. This area of research has emerged a decade ago, with the increasing availability of large-scale anonymized datasets, and has grown into a stand-alone topic. We will survey the contributions made so far on the social networks that can be constructed with such data, the study of personal mobility, geographical partitioning, urban planning, and help towards development as well as security and privacy issues.

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.

The focused organization theory of social ties proposes that the structure of human social networks can be arranged around extra-network foci, which can include shared physical spaces such as homes, workplaces, restaurants, and so on. Until now, this has been difficult to investigate on a large scale, but the huge volume of data available from online location-based social services now makes it possible to examine the friendships and mobility of many thousands of people, and to investigate the relationship between meetings at places and the structure of the social network. In this paper, we analyze a large dataset from Foursquare, the most popular online location-based social network. We examine the properties of city-based social networks, finding that they have common structural properties, and that the category of place where two people meet has very strong influence on the likelihood of their being friends. Inspired by these observations in combination with the focused organization theory, we then present a model to generate city-level social networks, and show that it produces networks with the structural properties seen in empirical data., 13 pages, 7 figures. IEEE/ASE SocialCom 2013

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

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.

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.

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.

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 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 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.

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.

This paper discusses the problem of designing fault tolerant compensators that stabilize a given system both in the nominal situation, as well as in the situation where one of the sensors or one of the actuators has failed. It is shown that such compensators always exist, provided that the system is detectable from each output and that it is stabilizable. The proof of this result is constructive, and a worked example shows how to design a fault tolerant compensator for a simple, yet challeging system. A family of second order systems is described that requires fault tolerant compensators of arbitrarily high order. Udgivelsesdato: FEB

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.