Non-binary maximum entropy network ensembles and their application to the study of urban mobility

Abstract

Complex networks grow subject to structural constraints which affect their measurable properties. Assessing the effect that such constraints impose on their observables is thus a crucial aspect to be taken into account in their analysis, if one wants to quantify the effect a given topological property has on other observed network quantities observed in empirical datasets.

Null models are needed for this end. A well understood analytical approach to face the generation and development of flexible models for binary networks is based on considering ensembles of networks obtained using an entropy maximization principle. In this work, we explore the generalization of maximum entropy ensembles to networks where multiple or non-dihcotomic connections among nodes are allowed. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and non-linear constraints including those depending both on the weight per link and their binary projection. We furthermore identify three different relevant cases that lead to distinctively different edge statistics, depending on the distinguishable nature of the events allocated to each link. For each case, we perform an extensive study considering microcanonical or hard constrained ensembles as well as grand canonical or soft constrained ones. We provide tools for the generation an analysis of network instances belonging to each model which are implemented and available in the form of open-source software packages, and we provide also analytical tools to obtain null model expectations to later compare to real data.

Developing the theory developed, we apply the obtained insights to the analysis of urban mobility considering four large datasets of taxi displacements in the cities of New York, Singapore, San Francisco and Vienna. We show that, once they are appropriately transformed, mobility patterns are highly stable over long time scales and display common features across the studied datasets which are very conveniently represented using one of the cases earlier studied maximum entropy ensembles. We furthermore perform a critical review on existing mobility demand forecasting models and discuss their strengths and weaknesses when adapted to the urban environment, while showing how entropy maximizing models display the best descriptive power of the datasets using a number of network-based, information and matrix similarity metrics to assess the accuracy of the predicted vehicle flows.

Based on our observations, we develop two practical applications based on our theoretical work. On the hand, we envisage a supersampling methodology to reliably extrapolate mobility records from a reduced sample which opens the possibility to scale up data from limited records when information on the full system is required. On the other hand, we adapt previous work on graph filtering to our proposed models that allows to extract random contributions from the observed empirical data. This allows to obtain simplified network backbones which contain the most relevant features of mobility datasets not explained by the considered constraints imposed in the maximum entropic models considered. Such a filter is useful for easing the analysis, computational handling and visualization of dense datasets, as well as assessing the degree of proximity between a model and empirical data

using suitable hypothesis testing arguments.

Les xarxes complexes tenen una estructura complicada, on sovint es fa difícil establir les relacions de causalitat entre les seves propietats macroscòpiques (mesurables). Per tal de fer-ho es necessiten models nuls amb propietats flexibles que es puguin fixar. Per a xarxes amb connexions binàries (que tenen valor dicotòmic u o zero), s'han proposat col·lectivitats de xarxes que compleixen un principi de màxima entropia per a resoldre el problema de generació d'aquest tipus de models. En aquest treball explorem la seva generalització per a xarxes no-binàries, on les connexions entre elements estan graduades. Desenvolupem un tractament matemàtic que ens permet obtenir prediccions sobre els observables més rellevants d'una xarxa que tingui certes propietats prefixades, a triar en un rang ampli de funcions lineals i no-lineals pertanyent a col·lectivitats micro-canòniques (propietats fixades de manera estricta) i gran canòniques (propietats fixades sols en promig sobre la col·lectivitat). Detectem tres possibles varietats que duen a estadístiques d'ocupació d'enllaços diferents, depenent de la distingibilitat dels elements a partir del qual s'ha generat la xarxa. Per cada cas, desenvolupem eines per a la generació computacional i l'anàlisi de mostres de xarxes pertanyents a cada col·lectivitat.

Tot seguit apliquem la teoria desenvolupada a l'anàlisi de mobilitat humana emprant sets de dades de desplaçaments de taxis a Nova York, Singapur, San Francisco i Viena. Mostrem l'estabilitat espaciotemporal de les dades estudiades i l'aparició de propietats comunes. Tot seguit realitzem un anàlisi crític de models de predicció de mobilitat existents i la seva possible adaptació als entorns urbans, mostrant com els models de màxima entropia tenen el major poder predictiu per descriure les dades. Finalment presentem dues aplicacions de la teoria desenvolupada que exploten les propietats comunes detectades a les dades estudiades. D'una banda, derivem un model que permet extrapolar dades de mobilitat sobre sets de dades reduïts. De l'altra, proposem un mètode de filtratge per extreure les contribucions de les dades reals dels trajectes esperats d'acord a qualssevol dels nostres models de màxima entropia. Aquest procediment permet obtenir versions simplificades de les xarxes originals que continguin les seves propietats més rellevants.