O Bouhamama

M Potse

L Bear

L Weynans

A Patchwork Method to improve the performance of the current ECGI methods for sinus rythm

Keywords: Inverse Problems, Method of fundamental solutions (MFS), FEM, Electrocardiography

Introduction

Noninvasive electrocardiographic imaging (ECGI) provides real-time panoramic images of epicardial electrical activity from potential measurements on the torso surface. This non-invasive imaging modality can become a powerful clinical tool to help understand the mechanisms underlying many cardiac diseases, and to define the appropriate treatment. ECGI is mathematically represented by a Cauchy problem for the Laplace equation div(σ∇u) = 0 in the torso volume, u = u T and σ∇u • n = 0 on the torso surface, (1) where u is the electric potential and σ the conductivity. This problem being ill-posed, regularization is needed to numerically solve u in the heart from the given u T . Several numerical methods are commonly used for ECGI: the finite-element method (FEM), the boundary-element method (BEM) and the method of fundamental solutions (MFS). Each of them can be used with various regularization terms, leading to a wide range of possible algorithms. While the accuracy of these methods have been compared using different types of data [5], there is still no consensus that one method globally outperforms the others.

Validation studies have shown that ECGI provides accurate activation maps in healthy hearts to localize ectopic sources of ventricular activity [6] and characterize ventricular dyssynchrony [1]. However, current implementations are inaccurate in reconstructing electrical activity during sinus rhythm in the presence of conduction abnormalities such as LBBB [1,3] and in structurally heterogeneous hearts [7]. Epicardial breakthrough sites can be missed or inaccurately localized, and artificial lines of block can appear. To prevent such artefacts we propose a method that locally selects, from several numerical solutions, the one that minimizes the estimated reconstruction error.

Patchwork method 2.1 Algorithm

We propose a patchwork method (PM) that locally selects the best solution among several methods. The linear relationship between the cardiac sources and * Corresponding author.

Email: oumayma.bouhamama@ubordeaux.fr the torso surface potentials after the discretization can be written in matrix form:

Au h = u T ,
where A is the transfer matrix, obtained from multiple resolutions of the forward problem, u h represents the unknown cardiac sources, and u T the torso measurements. We denote by A F , A B and A M the transfer matrices with the FEM, BEM and MFS. The residuals R γ (u h ) = A γ u h -u T , with γ = F, B, M represent the difference between the numerical solution on the torso obtained with u h and the measurements u T .

Let us denote u ex the array representing the exact solution of the inverse problem discretized on an epicardial mesh. For all methods, the residual of u ex tends to zero when the mesh size tends to zero:

lim h→0 R γ (u ex ) = 0, γ = F , B, M,
We propose to use this property as a criterion to select locally, among several numerical solutions obtained with different algorithms, the one that is closest to the exact solution, without knowing what the exact solution is. As a first example, we compared the results obtained with the FEM and the MFS and a zeroth-order Tikhonov regularization.

Our algorithm is the following:

• For each time step n:

-Compute the approximate solutions u n h,F and u n h,M with the FEM and the MFS, -Use these solutions to compute the forward solution and the associated residuals R B (u n h,F ) and R B (u n h,M ) on the torso surface using the BEM formulation, -For each epicardial point, select the method whose residual is the smallest on the nearest torso point, and define a coefficient α n = 0 if the MFS has the smallest residual, and 1 otherwise,

• Perform a temporal regularization of the coefficient α to avoid sudden variations between successive time steps,

• For each time step n, compute the new approximate solution as

u n h = α n u n h,F + (1 -α n )u n h,M .

Data

The method was tested using data generated with a detailed heart-torso model that was previously tailored to a patient. We used a set of 8 simulations, including 7 with tissue damage. Activation was simulated with a monodomain reaction-diffusion equation using the TNNP membrane model, at 0.2-mm resolution. Extracellular potentials were computed by solving the elliptic bidomain equation in a whole-torso model at 1-mm resolution. Damage patterns consisted of sheets of connective tissue aligned with the 3 coordinate axes [4]. The sheets were 0.4 mm thick and were placed at 1-mm intervals. 20 % of the surface of the sheets consisted of holes. The sheets extended through the entire myocardium but not through the thin layer that represents the Purkinje system in the model.

Evaluation test

Activation times were determined from ECGI electrograms using a spatio-temporal algorithm [2]. Correlation coefficients (CC) and relative errors (RE) were computed between ECGI-detected and true activation times. Epicardial breakthrough sites were identified from activation maps as sites with a local minimum in activation time. The centers of the early activation areas were taken as the breakthrough sites. We also calculated the localization error of the breakthrough sites (LE1-LE3) using the geodesic distance and the time difference between the ECGI-detected and the nearest actual breakthroughs. Statistical analyses were performed using GraphPad Prism 8.3. For each metric, the significance of the differences was tested using paired t-tests with p < 0.05 defined as significant. Data are expressed as mean ± SD.

Results and discussion

Figure 1 shows the correlation and relative error between activation maps of different methods. Activation maps reconstructed by PM were more correlated to the simulated maps than those recontructed by MFS and FEM (p = 0.0049). PM also reduced the RE for activation maps (p = 0.0009). Table 1 presents numerical comparisons of ECGIdetected and the nearest true breakthroughs sites. MFS captured only 2 breakthrough sites and FEM sometimes missed one breakthrough. However PM always succeeded in detecting all the breakthrough sites. The localization error obtained by PM and MFS was smaller than that obtained by FEM. Time differences between ECGI-detected breakthroughs and the nearest actual breakthrough was similar for the three methods.

Conclusion

We presented a novel ECGI approach to reconstruct electrical activity in sinus rhythm in structurally abnormal hearts. This new approach, called the patchwork method, is an efficient tool to help overcome some of the limitations of current numerical methods, improving the accuracy of activation maps and localization of epicardial breakthroughs.

Figure 1 :Table 1 :

 11 Figure 1: Correlation coefficients (CC) and relative errors (RE) for activation time for new method (PM), MFS and FEM.

Acknowledgements

This work was supported by the French National Research Agency (ANR-10-IAHU04-LIRYC).


Licia Amichi
email: licia.amichi@inria.fr

Aline Viana Carneiro

Mark Crovella
email: crovella@bu.edu

Antonio Loureiro
email: loureiro@dcc.ufmg.br

An inherent limiting factor of human mobility prediction

Keywords: Individual Mobility, Exploration, Mobility Profiling, I. INTRODUCTION

Predicting how we humans move within space and time is becoming a central topic in many scientific domains, ranging from epidemic propagation, urban planning to ride-sharing. However, current works neglect individuals' preferences for exploration and discovery of new places. Yet, noveltyseeking activities appear to have significant consequences on the ability to understand and predict individuals' trajectories. In this work, we propose a new approach for the identification of moments of novelty-seeking. Subsequently, we construct individuals' mobility profiles based on their exploration inclinations -Scouters (i.e., extreme explorers), Routiners (i.e., extreme returners), and Regulars (i.e., without extreme behavior).

trajectories and forecast his/her future locations. Indeed, accurate mobility models and predictors are crucial for epidemic prevention [START_REF] Belik | Natural human mobility patterns and spatial spread of infectious diseases[END_REF], disaster response [START_REF] Lu | Predictability of population displacement after the 2010 haiti earthquake[END_REF][START_REF] Bengtsson | Improved response to disasters and outbreaks by tracking population movements with mobile phone network data: A post-earthquake geospatial study in haiti[END_REF], improving the services provided by pervasive computing applications [START_REF] Quercia | Recommending social events from mobile phone location data[END_REF][START_REF] Aalto | Bluetooth and wap push based location-aware mobile advertising system[END_REF][START_REF] Karamshuk | Geo-spotting: Mining online location-based services for optimal retail store placement[END_REF], providing energy-efficient and cost-effective network infrastructures [START_REF] Nadembega | Mobility-prediction-aware bandwidth reservation scheme for mobile networks[END_REF][START_REF] De Rango | Utility-based predictive services for adaptive wireless networks with mobile hosts[END_REF], or traffic management [START_REF] Serdar | Understanding congested travel in urban areas[END_REF].

Previous studies have shown that individual mobility exhibit high temporal and spatial regular patterns characterized by few locations where users return frequently and predictably, interrupted by irregular sporadic visits to unknown or rarely visited places [START_REF] Brockmann | The scaling laws of human travel[END_REF][START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. But, to what extent is human mobility predictable? In this regard, several works have been conducted, either by measuring the theoretical upper bound (theoretical predictability) [START_REF] Lu | Predictability of population displacement after the 2010 haiti earthquake[END_REF][START_REF] Song | Limits of Predictability in Human Mobility[END_REF][START_REF] Lin | Predictability of individuals' mobility with high-resolution positioning data[END_REF] or by computing the accuracy of prediction (practical predictability) [START_REF] Lu | Approaching the Limit of Predictability in Human Mobility[END_REF][START_REF] Gao | Mobile location prediction in spatio-temporal context[END_REF][START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF] of the advanced developed predictive algorithms. Nevertheless, the empirical results suggested the predictability takes variable values ranging from under 40% to higher than 90% [START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF]. So, what are the origins behind this large variation in the predictability measures? Alternatively stated, what are the significant factors influencing the predictability?

A non-negligible impacting factor is the tendency of individuals to explore and discover new places. Indeed, novelty-seeking is highly present in our daily lives, we are continuously hunting for new places and spots to go [START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF]. Moreover, the susceptibility to break the returning routine to explore and discover new places is heterogeneous among the populations, in this vein several profiling according to the proclivity to explore were disclosed [START_REF] Pappalardo | Returners and explorers dichotomy in human mobility[END_REF], and [START_REF] Scherrer | Travelers or locals? Identifying meaningful sub-populations from human movement data in the absence of ground truth[END_REF]. This indicates that the novelty-seeking factor can be a critical factor and should not be overlooked for certain categories of individuals who present a high exploration activity. A noteworthy question essential for the development of optimal predictors is, to what degree do novelty-seeking activities obstruct the predictability of human mobility trajectories?

This paper is an extended version of the earlier work published in the Proceedings of the 28th International Conference on Advances in Geographic Information Systems (SIGSPATIAL '20) [START_REF] Amichi | Understanding individuals' proclivity for novelty seeking[END_REF]. We provide a more thorough understanding of the exploration phenomenon and propose a mobility profiling accordingly. The key contributions of this paper are:

• We propose a novel per-user approach for the classification of the visited locations: (i) RV places visited for regular and routine activities, and (ii) EV places visited when being carried by the tendency to explore. Next, we validate our proposal by a thorough experimental validation and a comparison of the performance with a state-of-the-art approach. Based on February 3, 2021 DRAFT this classification, we highlight moments of novelty-seeking of the individuals.

• We introduce a modeling approach that splits each individual visit into two categories: exploration -i.e., the discovery of new places -and return -i.e., the revisit of known locations. Then we define new metrics that capture individuals' propensity to explore new places and their intermittency -i.e., the shift between the two types of visits. Next, using our newly designed metrics we reveal the existence of three visiting profiles: Scouters, Routiners, and Regulars. For this, we use four urban datasets, describing people's mobility from 5 cities in 3 different continents around the world (Section III).

The remainder of this paper is organized as follows. We start with an overview of the related works in the field of predictability and its impacting factors in Section II. Following, in Section III we describe the datasets used throughout the study and the experimental settings. Next, we present our new method for the identification of exploratory moments, based upon we introduce our newly developed metrics able to capture the propensity of individuals for novelty-seeking and propose an exploration-based mobility profiling and reveal the existence of three main profiles -Scouters, Regulars, and Routiners-in Section IV. Finally, we provide a discussion on the future research directions and open issues and challenges in Section V.

II. RELATED WORKS

Over the last decade, human mobility has been extensively scrutinized to understand the mechanisms ruling an individual's movements. Several works have demonstrated that human movements are far from being random and have a high degree of predictability [START_REF] Barbosa | Human mobility: Models and applications[END_REF].

The seminal paper of Song et al. [START_REF] Song | Limits of Predictability in Human Mobility[END_REF] proposed an approach based on the entropic level of a mobility trace to measure the upper bound of its maximum predictability Π max . Analyzing a three-month-long CDR dataset of 50,000 users, their study revealed that there is a 93% potential predictability in an individual's mobility trace. Several subsequent works tried to refine the predictability upper bound Π max . For instance, Lu et al. [START_REF] Lu | Predictability of population displacement after the 2010 haiti earthquake[END_REF] find that, on a CDR dataset containing the mobility trace of 2.9 million individuals, the upper limit of the predictability is estimated to be 85%.

Building upon the above findings, many advanced predicting algorithms were designed attempting to approach the theoretical predictability, such as Markovian predictors, Bayesian network models, neural network algorithms, and so on. Lu et al. [START_REF] Lu | Approaching the Limit of Predictability in Human Mobility[END_REF] sought to approach the theoretical limits of the predictability and utilized a Markov Chain based predictor with a varying order, and showed that the practical predictability reaches 91%. Moreover, they showed that higher-order Markov Chain models do not significantly improve the practical predictability. Gao et al. [START_REF] Gao | Mobile location prediction in spatio-temporal context[END_REF] proposed and implemented a novel predictor based on Bayes Networks and found that, using the Nokia Mobile Data Challenge that contains the mobility traces of 80 users, the practical predictability is about 50%.

Subsequent works employing the same approach as in [START_REF] Song | Limits of Predictability in Human Mobility[END_REF] attempted to dig out the significant factors that affect the predictability of human mobility, and shed light on origins of the limitations in predicting the next location:

Novelty-seeking: Recent studies have shown the importance of considering individuals' proclivity to explore new locations when modeling their mobility. [START_REF] Song | Modelling the scaling properties of human mobility[END_REF]. Cuttone et al. [START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF] highlighted the importance of considering the exploration phenomenon when designing mobility predictors.

Indeed, the higher an individual is prone to discover new places the less predictive he/she is as it is impossible to forecast the unknown. This led to an important question being raised, do all individuals explore at the same rate? Or, is there a category of individuals who explore more and hence are less predictable?

In this regard, Pappalardo et al. [START_REF] Pappalardo | Returners and explorers dichotomy in human mobility[END_REF] discerned two categories of people: explorers and returners. They based their classification on the number of regularly visited places, explores are those who visit many locations on a regular basis, whereas returners limit their mobility between few places.

Besides, Scherrer et al. [START_REF] Scherrer | Travelers or locals? Identifying meaningful sub-populations from human movement data in the absence of ground truth[END_REF] using an unsupervised approached classified individuals into travelers and locals. Travelers have a spread mobility, whereas locals move in a more constrained area and revisit many of their locations.

Moreover, in our previous work [START_REF] Amichi | Understanding individuals' proclivity for novelty seeking[END_REF] we proposed a mobility profiling based on individuals' tendency to explore that we further improve in this paper. We revealed the existence of three main categories of individuals: (i) Scouters or extreme explorers: whose proclivity for noveltyseeking is the most eminent all over the week and have a more spread spatial mobility; (ii)

Routiners or extreme returners: who rarely perform explorations and have confined mobility;

(iii) Regulars: who have a medium behavior.

Accordingly, exploratory activities are not consistent among the population. While some February 3, 2021 DRAFT groups depict a high propensity for discovering new areas and spots, others spend their time between familiar places. Investigating how novelty-seeking inclinations of individuals affect the predictability of their mobility traces is a topic that has yet to be researched.

Spatial and temporal resolutions: Jensen et al. [START_REF] Jensen | Estimating human predictability from mobile sensor data[END_REF] examined the upper bound predictability using various types of mobile sensor data, namely, GSM, WLAN, Bluetooth, and acceleration of 48 days' records for 14 individuals. Likewise, they reported high potential predictability for the data. Additionally, they showed that by varying the temporal resolution from a few minutes to a few hours, the highest predictive performance is obtained when the time scale is 4 to 5 minutes. Later, Lin et al. [START_REF] Lin | Predictability of individuals' mobility with high-resolution positioning data[END_REF] used a high spatial and temporal resolution GPS dataset of 40 individual. The authors showed that their finer-grained dataset produces higher upper bounds with a predictability exceeding 98% with a temporal scale of 20 minutes or less. Smith et al. [START_REF] Smith | A refined limit on the predictability of human mobility[END_REF] and Teixeira et al. [START_REF] De C. Teixeira | Deciphering predictability limits in human mobility[END_REF], showed that the predictability is correlated with the temporal resolution and have an inverse correlation with the spatial resolution.

Type of prediction: Ikanovic et al. [START_REF] Lind | An alternative approach to the limits of predictability in human mobility[END_REF] emphasized the origins of the high potential predictability of individuals' mobility obtained in earlier works [START_REF] Lu | Predictability of population displacement after the 2010 haiti earthquake[END_REF][START_REF] Song | Limits of Predictability in Human Mobility[END_REF]. They focused on the next-place prediction that considers moments of transitions only -i.e., . moving from a place to a distinct one-, then estimated the upper bound limit of the predictability, and obtained an accuracy of approximately 71%. Thereby, they validated that the high estimated values of predictability stem from the stationarity rather than movements. Cuttone et al. [START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF] analyzed the predictability of a GPS dataset with the two widespread formulations of prediction, namely, the next-time step prediction and the next-place prediction. While the next-time step prediction is shown to have a very high upper bound Π max = 95% due to the stationarity in the human mobility, the next-place prediction appears to be more challenging with an upper bound lower than 68%.

Position of our work: While the impacts of prediction formulation on the upper-limit of predictability have been widely investigated, the limiting factors that arise from the intrinsic nature of human mobility have rarely been addressed. In this paper, on the one hand, we shed light on one of the main limiting factors of predictability that arouses from the intrinsic uncertain nature of human mobility, namely, individuals' propensity to explore and perform a mobility profiling accordingly. On the other hand, we investigate how the prediction formulation and the spatial and temporal qualities of the used data can impact the predictability of each mobility profile.

III. DATA DESCRIPTION

In this work, we use two categories of data sources to investigate individuals' proclivity for novelty-seeking; three Global Positioning System (GPS) and one of Call Detail Records (CDR).

These datasets capture spatio-temporal footprints of individuals' mobility with high spatial and temporal resolutions. We outline our datasets in Table I

A. GPS datasets

GPS technology allows tracking individuals' movements with the highest level of accuracy and temporal frequency. Hereafter, we describe our three GPS data sources.

Macaco: it consists of the anonymized digital activities tracks of 132 volunteers from 6 different countries collected by the MACACO project [START_REF] Jaffres-Runser | Crowdsensing Mobile Content and Context Data: Lessons Learned in the Wild[END_REF]. The project provides a long-term and finegrained sampling of individual behavior and network usage with a frequency of one sample every 5 minutes for a duration of 34 months. The data source contains about 900k tuples with raw GPS coordinates (latitude and longitude) and timestamp. Each tuple has a unique ID, which relates to a specific user.

Privamov: it contains mobility traces collected in the Privamov sensing compaign [START_REF] Benmokhtar | PRIVA'MOV: Analysing Human Mobility Through Multi-Sensor Datasets[END_REF], capturing the spatio-temporal footprints of 100 unique volunteers over 15 months around a city in Europe.

The data source was gathered over 156 million GPS records with a frequency of sampling roughly equal to a few seconds.

Geolife: our last GPS data source was collected in (Microsoft Research Asia) Geolife [START_REF] Zheng | Understanding mobility based on gps data[END_REF][START_REF] Zheng | Geolife: A collaborative social networking service among user, location and trajectory[END_REF].

The dataset stores information about the GPS trajectories of 182 individuals distributed in over

(id i = lon i c
, lat i c ) as in [START_REF] Cuttone | Understanding predictability and exploration in human mobility[END_REF], where c meters is the cell-size in the grid. Hence, the mobility trajectory of the individual u is converted into sequences of timestamped discrete symbols -a discrete mobility trajectory-, T u,c = (id 0 , t 0 ), (id 1 , t 0 + δ), . . . (id N , t 0 + N δ) . Afterward, given that the location of each individual is obtained at different uniform temporal rates in our GPS data sources -i.e., 5 min for the Macaco, few seconds for Privamov, and 5 seconds for Geolife -, we re-sampled all the GPS datasets to have an equal frequency of one sample every 5 min, i.e, δ = 5min. However, some records can be missing due to delayed measurements produced by the sleeping phases of mobile devices collecting the data. Hence, to have a more uniform and complete traces, we comply with some steps proposed by Chen et al. [START_REF] Chen | Complete Trajectory Reconstruction from Sparse Mobile Phone Data[END_REF] and complete them as follows,

• First, per individual u, we identify the most frequent daily location id wpa between 10 am and 11 am and name it workplace A.

• Second, we locate the most visited location id wp b between 2 pm and 5 pm and name it workplace B.

• Next, we determine the most prevalent place id h between 2 am and 6 am (night), which we refer to as home location.

• Once home (id h ), workplace A (id wpa ), and workplace B (id wp b ) locations are identified, if a record is missing at t x between 10 am and 11 am we complete the mobility trajectory T u,c with a new record (id wpa , t x ) if a record is missing at t x ∈ [2 pm, 5 pm], we add the tuple (id wp b , t x ) to the mobility trajectory T u,c .

if a record is missing at t x ∈ [2 am, 6 am], we add to the mobility trajectory T u,c the record (id h , t x ) .

D. Experimental settings

In what follows, we give a brief description of the parameter settings we used in this study.

We define a complete day for the GPS datasets as a day in which an individual has on average one record each 15 min. And select only participants that have at least 1 month of complete days of data. We are left with 264 users: 82 in Macaco, 77 in Privamov, and 103 in Geolife. For the CDR data, given the low frequency of sampling, we define a complete day as a day having on average one record every 2 hours and select only participants that have at least 15 days of complete data, we are left with 4860 individuals.

We discretize locations to grid cells of size c = 200m, with a frequency of 1 record each 5 min for the GPS datasets, and 1 record per hour for the CDR dataset. There are two reasons to consider these spatial and temporal resolutions. First, in this paper we focus on the discoveries of new places on a daily basis, for instance, going to a new restaurant or a new shop. Therefore, a cell of size 200m × 200m along with the imprecision and uncertainty of GPS systems, roughly February 3, 2021 DRAFT corresponds to daily regions of interest. Second, the higher is the temporal resolution the better is the understanding of human movements. Nevertheless, there is a tradeoff between expanding the set of selected individuals and increasing the temporal resolution. A resolution of 5 min for the GPS datasets allows uniforming the frequency of sampling between the different sources while increasing the number of individuals and being reasonable for capturing most transitions.

Moreover, having different datasets with the same resolutions allows us to test the effectiveness of our methods and to extensively validate our work.

IV. PROFILING METHODOLOGY

There exists a perplexity in understanding and predicting individuals' mobility patterns. Human beings' movements are a mixture of repetitive and regular transitions between known places and sporadic discoveries of new areas [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF][START_REF] Pappalardo | Returners and explorers dichotomy in human mobility[END_REF][START_REF] Schneider | Unravelling daily human mobility motifs[END_REF], both subject to a certain degree of uncertainty associated with free will and arbitrariness [START_REF] Alessandretti | Evidence for a conserved quantity in human mobility[END_REF]. At each instant, an individual is confronted with an extensive list of choices with regard to how and where to spend his/her time, and has two alternatives: he/she either returns to a place he/she visited in the past or explores a new location.

Here, we intend to investigate whether there exist patterns when commuting from an exploration mode to a return mode and vice versa. For this, we divide human movements into two primary states: explorations and returns. We define (i) the exploration as a discovery of a new location, i.e., a visit to a location that is not present in the visiting history of an individual and (ii) a return as a visit to a previously seen locality.

A. Formalization

Let M be the Finite-State Automaton (FSA) describing an individual's movements, as shown in Fig.

B. Novelty-seeking identification

Strictly speaking, an exploration is a discovery of a new geographical location, i.e., a place where the concerned individual was never seen before. Given the mobility trace of an individual u, how can we distinguish his/her novelty-seeking visits from his/her routine visits? To this end we adopt two methods to characterize and classify the visited locations at the individual level:

1) Visitation-frequency-based identification: let F u = {id 1 , id 2 , . . . , id n } be the set of location visited by the user u. First, for each location id i ∈ F u , we assign a weight w, given by,

w u (id i ) = f req u (id i , T u,c ) |F | j=1 f req u (id j , T u,c ) , (1)
where f req u (id i , T u,c ) is the number of occurrences of the location id i in the discrete mobility trajectory T u,c of the user u. Next, we compute the average value of the visitation frequency

w u = 1 |F | × |F | i=1 w u (id i ).
Following, we categorize the visited locations into locations used for:

(i)Exploratory Visits (EV), (ii) Return Visits(RV). Each location id i that has a weight w u (id i ) ≥ w u × level is added to the set of locations used for RV, T RV , otherwise it is assigned to the list of places used for EV, T EV (see Algorithm 1).

2) Baseline identification: we compute the Relevance R u of the location id i visited by the user u as proposed in [START_REF] Papandrea | On the properties of human mobility[END_REF],

R u (id i ) = d visit (id i , u) d total (u) , (2)
Algorithm 1 Novelty-seeking identification A 1: function location classification a (T u,c , level)

2: w u , T RVu , T EVu ← ∅ 3: F u ← UNIQUE(T u,c ) 4: for j in F u do 5: w u [j] ← FREQUENCY OF APPEARANCE(j, T u,c ), (1)
6: end for

7: w u ← MEAN(w u ) 8: for j in F u do 9: if w u [j] ≥ w u × level then 10:
T RVu .ADD(j) T EVu .ADD(j) is the number of days the individual has been active. Following, as in [START_REF] Papandrea | On the properties of human mobility[END_REF] we use the kmean unsupervised approach to classify the location into: (i) Mostly Visited Places (MVP), i.e, locations most frequently visited by the user; (ii) Occasionally Visited Places (OVP), i.e, locations of interest for the user, but visited just occasionally; (iii) Exceptionally Visited Places (EVP), i.e, rarely visited locations (see Algorithm 2).

For each individual u of our datasets, we classify his/her visited locations into EV or RV using our proposed Algorithm 1 at first with level = 80%, then with level = 20%. Following we use Algorithms 2 for the categorisation of the visited places into EVP, OVP, and MVP.

Next, we compute the percentage of the places within each category (see Figure 2a). Afterward, we evaluate the average visitation frequency in each group as shown in Figure 2b. daily routines of the individuals. Likewise the proportion of locations used for EVs surpasses 78% while level is set to 80%, and is higher that 60% with level = 20%. Moreover, we can notice in the case where level = 80%, the proportion of places classified as EV by Algorithm 1 corresponds roughly to the percentage of places categorized as EVP and OVP by Algorithms 2.

In contrast, Algorithm 1 with level = 20% captures almost the same faction of EV as the number of locations classified as EVP. This indicates that setting level to 80% may lead to an overestimation of the locations used for EV, while 20% seems a more reasonable setting.

Figure 2b illustrates the proportion of the average frequency of visits to each category of places (EV and RV by Algorithm 1; EVP, OVP, and MVP for Algorithms 2 ). Firstly, we see the markedly high proportion of visits to location used for RV, more than 90% of the visits February 3, 2021 DRAFT are towrds this category of places for level ∈ {20, 80}%. Whereas the same score is obtained by Algorithms 2 while taking MVP and OVP together. Additionally, the average frequency of visits hold by EV for all datasets is lower than the scores obtained by EVP. Contrary to our assumption above, a setting with leve = 80% is not an over estimation of the locations used for EV, but it allows a more thorough capture of visits enhanced by the proclivity to explore of the individuals.

In summary, the proposed method Algorithm 1 allows a more satisfactory classification of the visited places compared to the baseline Algorithms 2. On the one hand, it allows the detection of a higher number of places used for EV, on the other hand, it guarantees that the visitation frequencies to these locations are notably lower compared to the RV as well as EVP of Algorithms 2. Withal, the performance of Algorithm 1 with level = 80% allows the identification of a higher number of places used for EV, and hence enables a better detection of moments of exploration compared to the setting with level = 20%. Indeed, the first occurrence of a location present int the T EVu of a user u in his/her mobility trace is presumed to be a moment of exploration. In the remaining of the paper, we use Algorithm 1 and set level to 80%

for the categorization of the visited locations at the cost of sometimes overestimating moments of novelty-seeking.

C. Mobility Profiling

Initially, each user u has an empty set of known locations L u (t = t 0 ) = ∅. Using Algorithm 1 with level set to 80%, for each user u we classify his/her visited locations into EV and RV.

Subsequent, all locations classified as RV are added to the set of known locations L u ← T RVu .

Therefore, each occurence of a location present the set of known locations L u is a return, else it is an exploration. Note that after the discovery of new place, this latter is added to L u , i.e., its next occurence will be viewed as a return.

After dissecting human transitions into explorations and returns, we first extract two sets:

• Returning set ret u : is a set containing the sets of consecutive returns

ret u = {r 0 , r 1 , . . . , r n } , (3)
where each r i = {id 0 , id 1 , . . . , id x } is a set containing the ids of the cells where the individual u performed successive returns.

• Exploring set exp u : is a set containing the sets of consecutive explorations exp u = {e 0 , e 1 , . . . , e n } ,

where each e i = {id 0 , id 1 , . . . , id x } is a set containing the ids of the cells where the individual u performed successive explorations. To characterize how individuals balance the trade-off between revisits of familiar locations and discoveries of new places, we define the following metrics that utterly capture the exploration habits of an individual. The first metric captures the shifting habits between the exploration and the return modes.

Definition 1 (Intermittency µ). is the sum of the average number of successive explorations #E and the average number of successive returns #R, µ = #R + #E.

The intermittency measure reveals whether an individual is versatile or prefers to remain steady. Namely, it helps to recognize if a user is constantly fluctuating between visits to familiar places and discoveries of new spots or once he/she starts a discovery he/she does is it repeatedly, before switching to revisits and vice versa. The second metric captures users' proclivity to make revisits rather than explore new places.

Definition 2 (Degree of return α). is the angle whose tangent is the ratio between the average number of successive returns R over the average number of successive explorations E,α = arctg #R #E .

The degree of return describes the exploration conducts of an individual compared to his/her returns. Having a high degree of returns suggests that: the average number of successive returns is higher than the average number of successive explorations #R > #E. Hence, the degree of return reveals what kind of explorer an individual is, whether he/she visits many new places on a row, or just after a few discoveries he/she goes back to a familiar location.

In what follows, we investigate whether the novelty-seeking habit is the same among the population or if it is a distinctive property. Namely, if there exist patterns followed by individuals while shifting between the exploration mode and returning mode or if there are several groups of users sharing the same habits but distinct from the others. After computing the intermittency µ and degree of return α for each individual, we use two clustering algorithms-the Gaussian Mixture probabilistic Model (GMM) and-the k-means clustering method to prob whether we can split the population into distinct cohesive and significant groups or not. To identify the best number of components of the clustering algorithms, and hence, the individuals' types we use the silhouette score statistical test and the Davies-Bouldin Index and run one hundred fits for five different sets of clusters (two to six). Then, we consider the mean value when choosing the best score. The results show that the best performance is obtained with a clustering with three components (see [START_REF] Amichi | Understanding individuals' proclivity for novelty seeking[END_REF]).

We now apply, the GMM and k-mean with three components on our data sources, we roughly obtain the same groups. Henceforth, hereafter we only present the results obtained with the GMM algorithm. Fig. 3 depicts the normalized intermittency of individuals against their normalized degree of return and displays the clusters resulting from the application of the GMM algorithm to our GPS and CDR data sets. We can observe that our metrics can clearly capture the dissimilarity between the individuals in terms of human mobility dynamics. More importantly, the GMM identifies three distinct groups that have identical intermittency and degree of return characteristics for all our data sources. We label the resulting groups as Scouters (red), Routiners (green), and Regulars (blue).

• Cluster 1: Scouters or extreme explorers, although holding varying degrees of return α, they are low compared to the others'. Moreover, they are notably intermittent -i.e., they are constantly shifting between the exploring and the returning states. These users are more prone to explore and discover new areas.

• Cluster 2: Routiners or extreme-returners have a surprisingly large degree of return. Besides, they tend to be steady in the different states of the automaton M -i.e., they rarely break their routine. Hence, we can deduce that these users rarely explore and prefer to stick among their common and known places.

• Cluster 3: Regulars adopt a medium behavior and have large degrees of return compared to the Scouters. Though, their intermittencies are distinctly smaller than those of Routiners.

These users constantly alternate between explorations and revisits. Yet, their proclivity to February 3, 2021 DRAFT

February 3

 3 , 2021 DRAFT 30 cities mainly in China, the USA, and Europe. The dataset includes time-stamped GPS tuples recorded every 1 to 5 seconds for more than 64 months.B. CDR datasetMobile phone records consist of time-stamped and geo-referenced records of voice phone calls and SMS of mobile network subscribers, called Call Detail Records. Each record usually contains the hashed identifiers of the caller, the timestamp for the call time, and the location of the cell tower to which the caller's device is connected to when the call originated.ChineseDB: this dataset is collected from 642K anonymized mobile phone subscribers in Shanghai, China 1 , and contains 400k calls. It provides aggregated human footprints in the frequency of one location per hour during a period of 2 weeks. The locations in this dataset are gathered by merging the locations of the original CDR in each one-hour interval. Each location of an hour represents the user's centroid of the hour with the precision of 200 meters according to the instruction of the data provider. This accuracy of positioning is higher than that of the original CDR.C. Data handlingModeling and predicting individuals' mobility focus on the location data i.e. latitude and longitude. First, we reconstruct the mobility trajectory H u of each individual u by extracting the sequence of recorded locations along with the associated timestamps at fixed time periods δ, H u = (lon 0 , lat 0 , t 0 ), (lon 1 , lat 1 , t 0 + δ), . . . (lon N , lat N , t 0 + N δ) . Next, we discretize the geographical maps by placing uniform grids of c meters × c meters and draw out the grid cell IDs associated with the coordinates, by converting the tuple (lat i , lon i ) into a cell identifier

Fig. 1 :

 1 Fig. 1: Finite-State Automaton M .

15 :

 15 return T RVu , T EVu 16: end function where d visit (id i , u) is the number of days the individual u visited the location id i , and d total (u)

Figure 2a reports the 1 : 4 : 7 :Fig. 2 :

 1472 Figure 2a reports the percentages of places classified in each category; EV and RV by Algorithm 1; EVP, OVP, and MVP by Algorithms 2. First, we observe the high ratio of EVP and OVP categorized by Algorithms 2, more than 78% of the places are not integrated in the

  Next, we assign to each individual u two values: (1) #E = avg(|e i |), e i ∈ exp u , the average number of his/her successive explorations-i.e., the average number of consecutive self-transitions he/she made in the E state, and (2) #R = avg(|r i |), r i ∈ ret u the average number of self-transitions he/she made in the R state.

  and discuss them hereinafter.

	Dataset	Category Number of users Duration Frequency of sampling
	Macaco [26]	GPS	132	34 months	5 min
	Privamov [27]	GPS	100	15 months	few seconds
	Geolife [28-30]	GPS	182	64 months	1 to 5 seconds
	ChineseDB *	CDR	642K	2 weeks	1 hour

*

The collection was initiated by Shanghai University

[START_REF] Chen | Complete Trajectory Reconstruction from Sparse Mobile Phone Data[END_REF]

.

TABLE I :

 I Datasets description.

  1, with two possible states: exploring (E) and returning (R). Initially the individual u is in the exploring state (E) if his/her current location id t 0 is not present in the set of his/her known places L u (t) at t = t 0 , i.e. id t 0 / ∈ L u (t) and in the returning state (R) otherwise. Two possible inputs can affect an individual's state: return (T r or S r ) by going back to historically known locations, and explore by discovering new spots (T e or S e ). In the exploring state E, In the returning R state visits to usual places (S R ) does not change the state, however, a discovery of a new spot (T e ), shifts the state back to the E state.

	S e	E	R

discovering new areas (S e ) has no effect and keeps the individual in the state E. On the other hand, moving back to a known location (T r ), though recently explored, gives M an input and

February 3, 2021

DRAFT shifts the state from E to R.

February 3, 2021 DRAFT

The collection was initiated by Shanghai University[START_REF] Chen | Complete Trajectory Reconstruction from Sparse Mobile Phone Data[END_REF].February 3,

DRAFT

explore is less important than Scouters'. Scouters. This is unlike in the method suggested by Pappalardo et al. [START_REF] Pappalardo | Returners and explorers dichotomy in human mobility[END_REF], where some individuals can be wrongly clustered as explorers or as returners. Contrary to [START_REF] Scherrer | Travelers or locals? Identifying meaningful sub-populations from human movement data in the absence of ground truth[END_REF] our approach captures two major mobility features that fully describe the exploration phenomenon, i.e., intermittency between returns and explorations, and the ratio of explorations compared to returners, as well as accordingly splits the populations.

V. FINAL REMARKS AND OPEN ISSUES

Using real-world mobility traces, this paper proposes a new method for recognizing moments of novelty-seeking. Based on the exploratory tendencies of the population we revealed the existence of three groups of individuals with regard to their propensity to explore and discover new places, namely, Scouters (adventurous and prone to explore); (ii) Routiners, (steady and routinary), and (iii) Regulars (with medium behavior). This result has two major implications for the understanding of human mobility. First, in mobility modeling, individuals' propensity to explore i.e., degree of return metric, as well as the elapsed time before the occurrence of an exploration event i.e., intermittency metric are substantial concepts that should be further investigated, to assess the existence of new novelty-seeking related scaling laws per mobility profile, and hence provide more consistent and generative models able to reproduce human trajectories. Second, in mobility prediction the proposed profiling allows distinguishing hard to predict individuals due to their exploration activity from the rest of the population, and therefore propose more adequate predictors.