Keywords: Urban mobility, Spatio-temporal patterns, Predictive modeling

s , Pablo Jensen and Pierre Mercklé, for giving me guidance through my PhD. A PhD is a marathon with a fair amount of sprints and I am glad they have always been present to share their experience to me.

I would like to thank as well Professor Cecilia Mascolo and her team who welcomed me in Cambridge University. I have learnt so much from our collaboration, both personally and professionally, that words can hardly translate my gratitude to this amazing team.

Finally, I would like to thank my family, friends and colleagues for their constant

Introduction

The amount of available data has been continuously increasing for the past two decades. Due to the dramatic increase of computer power, storage capacity and the ubiquity of connected devices (smartphones, Internet Of Things) large datasets have emerged with a fine-grained description of complex systems. I will for the rest of this thesis use the definition of complex systems from [Barrat et al., 2008a]:

"complex systems consist of a large number of elements capable of interacting with each other and their environment in order to organize in specific emergent structures" Such systems have fascinating properties regarding their dynamics. One can think of systems where the overall dynamics is more than the dynamics of its units. Whereas other systems can exhibit a steady state architecture and properties despite the continuous changes of its units. These examples illustrate the need to develop different approaches to think the emergent dynamics of complex systems.

Complex systems can be found in very wide range of areas: [START_REF] Cambe | Modelling Cooperation and Competition in Urban Retail Ecosystems with Complex Network Metrics[END_REF] in biology (proteins and genes interact to form and regulate cells activities, see [START_REF] Barrat | Dynamical Processes on Complex Networks[END_REF], Kovács et al., 2019]); [START_REF] Cambe | Exploring and comparing temporal clustering methods[END_REF] in ecology (food webs can be represented as a complex network of species, see [START_REF] Caldarelli | Fo o d web structure and the evolution of complex networks[END_REF]); (3) in finance (the world financial market is a network of banks and institutions trading assets [START_REF] Schweitzer | Economic networks: The new challenges[END_REF], Caccioli et al., 2014]); and more closely related to the subject of this thesis in sociology and economics. We will take a deeper look at these in section 1. 1.3. In parallel with this increase in available data, methods and fields of research have been developing accordingly to process these data and help understand the complex nature of real-world problems with data, see [Donoho, 2017[START_REF] Liao | Data mining techniques and applications -a decade review from 2000 to 2011[END_REF], Sagiroglu and Sinanc, 2013].

It has been now around twenty years that the data journey has started leading to the relatively recent constitution of large longitudinal datasets taking into account one more dimension: time. Many systems have an inherent temporal component and there is nowadays a need for new tools in order to get an understanding of the temporal dynamics of such complex systems. In order to get a global understanding of complex systems problems, it is necessary to tackle them from different angles. Therefore, the necessity to accumulate methods from different fields of research and combine them is 1 critical. The aim of this thesis is to explore the plurality of approaches available and merge them into new methodologies.

The tools used in this thesis will focus on network science, machine learning, and statistical physics modeling. In the following paragraphs, I will present the fields of research I explored before developing my contributions.

1.1 An Overview of Network Science

Static Complex Networks

Let us first speak about what network science is and what are the motivations of this field of research. Network science aims to model interactions between different units of a system using graph theory. It was first used for information technology purposes -lik ethemappingtheW orldWideW eb(WWW)inordertooptimiz esearc hengines. Then, network sciences appeared to be efficient enough to model a huge amount of complex systems belonging to the field of biology, ecology, finance, and so on, as seen previously.

The principle of complex networks study is to understand the global system behavior by describing the interactions between its units. Formally a network can be represented as a graph G. This graph is composed of a set of nodes N and a set of edges E linking the nodes to each other. This formalism makes it easy to visualize and measure interactions between the units of the network as the interactions are coded in the topology of the graph. In order to understand the topology of the system, one can look at measures describing the state of connectivity of its units. Some of the most common measures are degree-related measures, clustering, centrality measures (e.g. closeness, betweenness, etc), modularity. We will come to a formal definition of most of these measures in the core of this thesis. More details on complex networks measures can be found in [Newman, 2010].

Temporal Complex Networks

As discussed earlier, the appearance of temporal data led to the evolution of network science to include the new area of temporal networks [START_REF] Holme | Temporal networks[END_REF]. Some real-world networks are by nature temporal, these are networks where nodes can (dis)appear over time or where edges are not continuously active. For example, communication networks (i.e. e-mails, text messages, and phone calls) are temporal networks. Cities are temporal networks as well and one can study and visualize the flow of people in them [START_REF] Roth | Structure of urban movements: Polycentric activity and entangled hierarchical flows[END_REF]. A temporal network is a union of static network snapshots at each time t.H e n c e ,t h et e m p o r a ln e t w o r kG T is composed of the set of nodes N T = S T t=1 N t and set of edges E T = S T t=1 E t . Considering a sequence of interactions, we can construct the corresponding temporal graph; or a static aggregated graph, where an edge between two nodes accounts for all the interactions which happened between the nodes during the time window of observation.

Using a temporal graph rather than an aggregated one can be useful when we need to take into account the order of interactions (like in the case of modeling spreading Figure 1.1 -Moreno's network of runaways, taken from [START_REF] Borgatti | Network analysis in the social sciences[END_REF]. Circles C12, C10, C5 and C3 represent the cottages in which the girls lived. Circles within the cottages represent girls and the 14 runaways are identified by their initials. Undirected edges between two girls represent feelings of mutual attraction, whereas directed edges represent one-way feelings of attraction. From this network, Moreno visualized the flow of social influence among the girls and argued that their location in the social network was determining when they ran away.

phenomena [START_REF] Karsai | Control strategies of contagion processes in time-varying networks[END_REF]). In this case the temporal path matters as it does not result in the same people being informed/infected.

In the next section, I give some historical context of social and urban systems.

Networks in Social Sciences

In social science, networks are used to model interactions between people and collective behaviors. The use of social networks started in the early twentieth century when J. Moreno and H. Jennings worked on the epidemic of runaways at the Hudson School for Girls, NY, USA. They, for the first time, used sociometry to model relationships between the runaway girls [Moreno, 1934]. Figure 1.1 shows one of the first sociograms published by Moreno in 1934. They represent interactions between girls in the case of the Hudson School runaways mentioned earlier in this paragraph. This work falls within the movement of social physics initiated by A. Comte [START_REF] Comte | Social physics: From the Positive philosophy of Auguste Comte[END_REF]. This movement envisioned a description of sociology following natural sciences paradigms. Hence terms such as 'social atoms' and 'social gravitation' have emerged during that period.

Following the work of Moreno, social networks research continued growing. In the fifties, M. Kochen and de Sola Pool [de Sola Pool and Kochen, 1978] formulated the small world problem, which would then become the subject of the well-known Milgram experiment in 1967 [Milgram, 1967] and finally was modeled by Watts andStrogatz in 1998 [Watts andStrogatz, 1998]. The small-world phenomenon is the observation that there exists a 'short path' connecting any two nodes in a network. Milgram, in his experiment, randomly sent packets to individuals living in two U.S. cities. Then these individuals needed to send the letter to a target person in Boston. If the randomly selected individuals did not know the target person, then they had to send the letter to someone who they thought would be more likely to know the target person. Every time a letter reached a new person, they must add their identity details to the letter, and repeat the process until reaching the target person. Over the 296 letters, 232 never reached destination [Milgram, 1967]. The remaining 64 letters eventually reached the target individual. The average path length, that is the number of intermediate people the letters went through, was around six. Later on, in 2008, small-world network properties were popularized in a Hollywood movie Connected: The Power of Six Degrees [Talas, 2008]. Nowadays, modern online social networks have usually smaller average path lengths: Facebook, 4.7 [START_REF] Backstrom | Four degrees of separation[END_REF]; Twitter, 5.4 [START_REF] Kwak | What is twitter, a social network or a news media[END_REF]; MSN, 6.6 [Leskovec and Horvitz, 2008]; Back to the history of social networks, in the 60-70's research developed around community structures and their role in socio-economic levels of individuals [START_REF] Bott | Family and Social Network[END_REF] -notably with the theory of the influential strength of weak ties [Granovetter, 1973] and later the theory of social capital [Bourdieu, 1986[START_REF] Putnam | Bowling Alone: The Collapse and Revival of American Community[END_REF], acknowledging the relationships of people as one of their main resources.

After this short overview of social networks evolution, it is worth noting that for a long time the dichotomy between social science and computer science has constrained social scientists to limit their analysis to relatively small networks [START_REF] Degenne | Les réseaux sociaux[END_REF]. Fortunately, the development of large online social networks and connected devices led computer scientists to develop tools to treat and visualize large amounts of data. Following the foundations of the twentieth century, the last twenty years have seen the emergence of new social systems. I will divide datasets into two groups: } Online social networks: like Facebook, Twitter and more generally mobile communications. These data allow to describe interactions between people and to study recurring structures in the society. For example in [START_REF] Leo | Socioeconomic correlations and stratification in social-communication networks[END_REF] the authors studied the socio-economic class structure of Mexican society using [START_REF] Cambe | Modelling Cooperation and Competition in Urban Retail Ecosystems with Complex Network Metrics[END_REF] mobile phone data, (2) credit and purchase data and (3) location data. In another work [START_REF] Kovanen | Temp oral motifs reveal homophily, gender-sp ecific patterns, and group talk in call sequences[END_REF], the authors studied the correlations between demographics (gender, age) and differences in communication patterns.

} mobility data: geolocalised social platforms such as foursquare, transportation systems (e.g. bike sharing systems [START_REF] Fishman | Bike share: A synthesis of the literature[END_REF], plane network [Neal, 2014], etc, enable to model the flow of people at various scales (city, country) and the interactions between flows and events, new policies and so on. For example, in [START_REF] Zhou | Cultural investment and urban socio-economic development: a geosocial network approach[END_REF] the authors study the impact of cultural investment policies in London neighborhoods using government data (socio-economic variables, cultural expenditures) and foursquare data. Another article, [START_REF] Faghih-Imani | How land-use and urban form impact bicycle flows: evidence from the bicycle-sharing system (bixi) in montreal[END_REF], explores the relationship between land use (restaurants, facilities, etc) and the flow of Montreal's bike sharing system.

After this overview on complex networks and social systems, I would like to introduce another story of research on social systems which was built in parallel with traditional social sciences.

Statistical Physics Models

Statistical mechanics is the art of turning the microscopic laws of physics into a description of Nature on a macroscopic scale. This definition is taken from [Tong, 2011]. Indeed the whole idea behind statistical physics is to find a way to describe from the microscopic properties of system components (atoms, particles, etc) the macroscopic evolution of the system itself. As its name suggests statistical physics uses methods from probability theory and statistics. More specifically, if one knows the states of atoms in a box, can one infer the state of the box content as a whole?

With this kind of framework, it is easy to understand why some statistical physicists went from the study of matter to describing complex systems from other fields of research such as biology [Peyrard, 2004], society [Castellano et al., 2009a] and economics [START_REF] Jovanovic | The Emergence of Econophysics: A New Approach in Modern Financial Theory[END_REF]. Therefore, over the past century, terms such as socio-physics and econophysics have emerged. Scientists have developed statistical models to understand concepts and model social phenomena.

For example, the Schelling mo del is an agent-based mo del develop ed by Nob el prize winner Thomas Schelling. In the model, each agent belongs to one of two groups (let us say 'green' and 'red') and aims to reside in a neighborhood with at least a small amount of agents with same color (not necessarily a majority). Schelling showed that when having this kind of personal (microscopic) rule, the system would converge to a segregated (macroscopic) state where red agents and green agents do not live in the same neighborhoods, despite their personal preferences. This model, which oversimplifies society does not aim to describe any real world phenomenon. This counterintuitive result illustrates the difficulty to infer microscopic states of system components (personal preferences, homophily, racism) from the macroscopic state of as y s t e m( s e g r e g a t i o n ) .

In chapter 2, we present a variant of the Schelling model studying the effect of mixing populations in such dynamical models and the resulting chaotic convergence tendency.

Finally, after the small social networks analysis and the mathematical toy models of the past century, the recent avalanche of data brings the hope of someday being able to model and predict social systems' evolution with an accuracy better than ever. In the next section, I give an overview of the more recent field of Machine Learning.

Machine Learning

Machine learning algorithms are being developed to analyze and make sense of large amounts of data. They have progressively conquered various fields of application, such as urban planning, natural language processing (text and speech), computer vision, market segmentation, to only name a few.

In the following, I describe only two subareas of machine learning, supervised and unsupervised learning. In this context, a machine learning model is implemented to predict the class of a data point (classification) or the value of a data point (regression). Developing such a model always requires to split the given data into two disjoint subsets: [START_REF] Cambe | Modelling Cooperation and Competition in Urban Retail Ecosystems with Complex Network Metrics[END_REF] the training data which are used for training the model and ( 2) the testing data which are used for testing that the model can actually predict the outcomes correctly.

In the case of supervised learning the classes/values that we try to predict are known. Hence, we can use this information during the training to learn the combinations of explanatory variables which 'explain' the class. For example, in the article [START_REF] Todorova | Exploiting population activity dynamics to predict urban epidemiological incidence[END_REF], the authors identify spatio-temporal patterns in ambulance call activity and assess the health risk of a geographic area. They, then, build a supervised learning model (Random Forest classifier) to predict for a given time which regions need an ambulance.

In unsupervised learning, the labels/values that we want to predict are not known. Therefore, unsupervised learning algorithms try to detect clusters in the data. In the case of customer segmentation, segments are constructed from customer data such as demographic characteristics, past purchase and product-use behaviors. See for example [Venkatesan, 2018], where the author uses K-means algorithm to discuss the importance of customer segmentation in marketing.

When implementing a machine learning model all the difficulty lies in being able to fit the training data with good accuracy (not underfitting) while still having a good generalization of outcomes (not overfitting), that is predicting accurately labels/values using test data. This is known as the Bias-Variance Tradeoff.

In chapter 3, we discuss the use of an unsupervised machine learning model to classify users of a bike sharing system using temporal data. In chapter 5, we implement abinaryclassificationsupervisedmachinelearningmodelinordertopredicttheimpact of a new business on other businesses in its neighborhood.

Contributions and Chapter Outline

The purpose of this thesis is to explore the dynamics of social systems. The rest of this thesis will start with a statistical model in chapter 2. This chapter will show the extreme sensitivity of Schelling-like models to population composition and discuss the importance of seeing such models as what they are: toy models that help shape concepts to better think our society. However, they should not be intended to model society.

In the first part of chapter 3, we study the behaviors evolution of the Vélo'v Lyon's bike sharing system (BSS) users over 5 years. We, then, discuss the results of an unsupervised machine learning model aiming to classify users based on their use profile. Using a methodology similar to a previous work [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF] analyzing a1 -y e a rd a t a s e t ,w es h o wt h i ss t u d yo v e r e s t i m a t e do n ec l a s sd e n s i t yd u et ot h el a c k of temporal component.

Chapter 4 explores temporal community detection using two scientometric networks. It describes the differences between local and global approaches. It also discusses ways to evaluate temporal community detection methods. More particularly, it compares Mutual Information measures to measures based on a bipartite graph representation of the partitions.

Chapter 5 merges complex network analysis and supervised machine learning in order to describe and predict interactions between new businesses and already established businesses in a neighborhood. This chapter combines practices from both complex networks modeling and machine learning. We show that using networks topology measures as explanatory variables increases the predictive power of the algorithm.

List of PhD Publications

During my PhD, I have worked on the following four papers, one has been published and three are currently under review. The chapters of this thesis are based on these articles.

Complex Dynamics From a Simple Social Model

Introduction

As mentioned earlier, simple social models can be useful to improve our intuitive, conceptualizations of social processes [Castellano et al., 2009b, Watts, 2011, Jensen, 2018]. For example, the segregation model proposed by Schelling [Schelling, 1971] helps understanding that the collective state reached by agents may well be different from what each of them seeks individually. Specifically, Schelling's model shows that even when all agents share a preference for a mixed city, the macroscopic stationary state may be segregated [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF]. In this thesis, we show that introducing av a n i s h i n g l ys m a l lc o n c e n t r a t i o no fa l t r u i s ta g e n t sg i v e sr i s et oas t r o n g l yn o nl i n e a r response.

Our model combines two important themes for many disciplines, including physics and economics: The large effects of small perturbations and the influence of altruistic behavior on coordination problems. On the first point, microscopic causes leading to macroscopic effects are well-known in physics. Chaos theory has shown that some dynamical systems are prone to an exponential increase of small perturbations [START_REF] Eckmann | Ergodic theory of chaos and strange attractors[END_REF], a topic of recurring interest in other fields, such as modeling of ecological competition [START_REF] Hébert-Dufresne | Strategic tradeoffs in competitor dynamics on adaptive networks[END_REF] or pattern formation [START_REF] Cross | Pattern formation outside of equilibrium[END_REF]. More related to this chapter, there are several examples of large effects arising from small changes in population composition. It has been shown that a small variation in the proportion of uninformed individuals may lead to strong changes in the way collective consensus is achieved by animal groups manipulated by an opinionated minority [START_REF] Couzin | Uninformed individuals promote democratic consensus in animal groups[END_REF]. In the minority game [START_REF] Challet | Emergence of cooperation and organization in an evolutionary game[END_REF], introducing a small proportion of fixed agents -i.e. agents that always choose the same option -induces a global change in the population behavior, leading to an increase of the overall gain [Liaw andLiu, 2005, Liaw, 2009]. In the voter model, a finite density of voters that never change opinion can prevent consensus to be reached [START_REF] Mobilia | On the role of zealotry in the voter model[END_REF].

On the second point, altruism is a major topic in evolutionary biology and economics [START_REF] Fehr | Altruistic punishment in humans[END_REF], Boyd et al., 2003[START_REF] Kirman | Selfish or selfless? the role of empathy in economics[END_REF]. Many models have shown that pair interactions between selfish players lead to stationary states of low utility. They have introduced various types of altruistic behavior to in-vestigate how it may lead to a better equilibrium: altruistic punishment [Fehr andGachter, 2002, Boyd et al., 2003], inequity aversion [START_REF] Hetzer | An evolutionary model of cooperation, fairness and altruistic punishment in public good games[END_REF], fraternal attitudes [START_REF] Szabo | Coexistence of fraternity and egoism for spatial social dilemmas[END_REF], agent mobility [START_REF] Cong | Individual mobility promotes punishment in evolutionary public goods games[END_REF] . . . Here, we use a simple definition of altruism (see below) and concentrate on the proportion of altruists needed to reach the social optimum. We show that, unexpectedly, an infinitesimal proportion of altruists can coordinate a large number of egoists and allow the whole system to reach the social optimum.

Description of the model

Our model represents the movement of a population of agents in a "city", which is divided into Q 1 non overlapping blocks, also called neighborhoods. Each block is divided into H sites and has the capacity to accommodate H agents (one per site). Initially, a number of agents N = QH⇢ 0 are distributed randomly over the blocks, leading to an average block density ⇢ 0 (⇢ 0 =0 .4 throughout the chapter). All agents share the same utility function u(⇢) that depends on the agents density ⇢ in the neighborhood where they are located. We choose a triangular utility (see Fig. 2.1): agents experience zero utility if they are alone (⇢ =0 )o ri nf u l lb l o c k s( ⇢ =1 ), and maximum utility u =1in half-filled blocks (⇢ =0 .5). The collective utility U is defined as the sum of all agents' utilities, U = H P Q q=1 ⇢ q u(⇢ q ) and the average utility ũ per agent is ũ = U/N.

Building upon past work on Schelling's segregation model [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF], we now mix two types of agents: "egoists", who act to improve their own, individual, utility, and a fraction p of "altruists", who act to improve the collective utility. Thus, egoists have as objective function the variation of their individual utility ∆u, while altruists consider the variation of the overall utility ∆U . The dynamics is the following: at each time step, an agent and a free site in another block are selected at random. The agent accepts to move to this new site only if its objective function strictly increases (note that the moving agent is taken into account to compute the density of the new block). Otherwise, it stays in its present block. Then, another agent and another empty site are chosen at random, and the same process is repeated until a stationary state is reached, i.e., until there are no possible moves for any agent.

Limiting cases: pure egoist or altruist populations

Authors in [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF] computed analytically the stationary states of a homogeneous population of egoist or altruist agents. Altruists always reach the optimal state, given by half filled (or empty) blocks and an average pure altruist utility ũA ' 1.

In contrast, a pure egoist population col lectively maximizes not U but an effective free energy that we have called the link L. The link is given by the sum over all blocks q of a potential l q : L = P q l q , where l q = P Nq nq=0 u(n q /H), with N q = H⇢ q is the total number of agents in block q.I nt h el a r g eH limit,

l(⇢ q ) ⇡ H Z ρq 0 u(⇢) d⇢.
(2.1) The link may be interpreted as the cumulative of the individual marginal utilities gained by agents, as they progressively enter the blocks from a reservoir of zero utility.

Its key property is that, for any move, ∆L =∆u. Since egoists move only when their individual ∆u is positive, the stationary state is given by maximizing L over all possible densities {⇢ q } of the blocks, from which no further ∆u>0 can be found. Analytical calculations [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF] show that this stationary state corresponds to crowded neighborhoods, far above the state of maximum average utility given by ⇢ q =1 /2.F o r t h e c a s e s t u d i e d i n t h i s c h a p t e r , t h e s t a t i o n a r y d e n s i t y i s g i v e n b y ⇢ E =1 / p 2,l e a d i n gt oap u r ee g o i s tu t i l i t yũ E =2 ( 1-⇢ E ) ' 0.586 ⌧ 1.N u m e r i c a l simulations have confirmed these results, though the existence of many metastable states around ⇢ E ' 0.7 leads to fluctuations in the simulated final densities.

Mixing populations: qualitative picture

We now investigate how adding a fraction of altruists drives the system away from the frustrated pure egoist case to the optimal configuration observed in the pure altruist case. We find that, instead of a linear response, the system reaches the optimal state even at very low altruist concentrations (p<0.01 in figure 2.2 a). To help understanding the origin of this strongly non-linear effect, the different panels of Fig. 2.3 illustrate the evolution of a small system (H =2 2 5 , Q =3 6and p =0 .04). Initially, altruists (yellow) and egoists (red) are distributed randomly in the blocks (a), which all have ad e n s i t y⇢ ' ⇢ 0 =0 .4. Then, blocks with the lowest densities are depleted by both altruists and egoists that prefer districts with higher densities. At some point, when the block density increases, the behavior of the two kinds of agents diverge. Altruists "sacrifice" themselves and leave these high density blocks, moving to blocks with lower densities, as this increases the utility of their many (former) neighbors, leading to an increase in global utility. On the other hand, egoists would loose individual utility by doing so, and therefore remain in these high density blocks which continue to feed on the remaining neighborhoods with ⇢<1/2.A f t e raf e wi t e r a t i o n s( F i g .2 . 3 b -c ) , selfish agents have gathered into "segregated" neighborhoods. This is the classical segregation observed in the pure egoist case [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF], arising from the well studied amplification of density fluctuations. Note that all altruists have left the egoist blocks and gather into few blocks with lower densities (Fig. 2.3c) and then into a single neighborhood, whose density increases until it becomes attractive for egoist agents who "invade" it (Fig. 2.3d-e), while altruists leave it for other lower density blocks (Fig. 2.3e). The density of some of these new blocks then increases, allowing for successive egoist invasions (Fig. 2.3f-g). These migrations of egoist agents reduce the density of the overcrowded egoist blocks, increasing the overall utility. Eventually, the system reaches a stationary state in which no agent can move to increase its objective function (Fig. 2.3h).

Quantitative description

We now give a quantitative explanation of the decrease of egoist blo ck densities and show that an altruist concentration p ' 1/Q is sufficient to drive the system towards the optimal state, ũ =1.T ou n d e r s t a n da l t r u i s t s 'd y n a m i c s ,i ti su s e f u lt or e p l a c et h e i r dynamics by an equivalent egoist dynamics with a utility u altr (⇢) that differs from the original utility u(⇢). An exact mapping can be done in the following way. As mentioned above, each altruist agent tries to maximize the global utility U = H P Q q=1 ⇢ q u(⇢ q ). In contrast, an egoist agent acts to maximize the link function L = P q `(⇢ q ), with `(⇢ q ) given in Eq. (2.1). As a result, an altruist agent exactly behaves as an equivalent egoist agent with a utility function u altr (⇢) satisfying the relation

⇢u(⇢)= Z ρ 0 u altr (⇢ 0 ) d⇢ 0 (2.2)
since the resulting function to be maximized is the same. Differentiating this last equation, one finds

u altr (⇢)= @ ⇢u(⇢) @⇢ = ( 4⇢, for ⇢  1 2 2(1 -2⇢), for ⇢> 1 2 (2.3)
This effective utility function for altruists is plotted on Fig. 2.4. Note that this effective utility is not the one used to compute average or global utilities, it only helps understanding altruists' moves, since an altruist moves to a new block only if u altr (⇢) increases. Fig. 2.4 shows that altruists have a clear preference for blocks with densities just below 1/2. The large discontinuity at ⇢ =1 /2 arises because at this density the original utility function u(⇢) changes slope and starts to decrease. Then, an altruist moving from a block with ⇢<1/2 to a slightly more populated one with ⇢>1/2 induces a large decrease of total utility, since all its former neighbors loose utility (as the density of the initial block decreases) and so do its new neighbors, as the density of their block increases. Fig. 2.2b suggests that the transition towards the optimal state is continuous and takes place at an altruist concentration p ' 1/Q for all values of Q. This Q dependence is important, since in the thermodynamic limit (Q !1 ), the transition would take place at p ! 0.W en o wd e r i v et h i sr e s u l ti nas i m p l ew a yb yc o m p u t i n ga n a l y t i c a l l y the evolution of the average utility as a function of the altruist concentration p.L e t ' s start with very low altruist concentrations and assume that the initial dynamics is dominated by egoists, which form the usual Schelling's overcrowded blocks, as observed above (Fig. 2.3c) and in previous work [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF]. Therefore, we take as starting point a city composed of n E egoist blocks with uniform density ⇢ e = ⇢ E > 1/2,s u c ht h a t⇢ E =( 1-p)Q⇢ 0 /n E .T a k i n g a u n i f o r m ⇢ e value is justified because any density fluctuation for ⇢ e > 1/2 is rapidly wiped out by the dynamics, as shown by the unique density of egoist blocks in Fig. 2.3i. Altruists can be initially somewhat scattered over the remaining blocks but, as their effective utility clearly shows (Fig. 2.4), they rapidly aggregate into a single block, leading to an altruist density ⇢ a = pQ⇢ 0 provided ⇢ a < 1/2,o re q u i v a l e n t l y

p<p high ⌘ 1 2⇢ 0 Q . (2.4)
The driving force for the transition are the relative values of agents' utilities in egoist and altruist blocks, respectively u e = u E =2-2⇢ E and u a =2 ⇢ a since ⇢ a < 1/2 and ⇢ E > 1/2.F o rv e r yl o wp values, ⇢ a is small, leading to u e >u a and the system remains in the usual frustrated Schelling egoist state ũ(p) ' ũE which is essentially constant. When p reaches a value p low such that u(⇢ a +1/H) >u(⇢ E ),afirstegoistcan improve its utility by moving into the altruist block, whose density becomes ⇢ a +1/H (Fig. 2.3d-f). This gives :

p low ⌘ 1 -⇢ E -1/H ⇢ 0 Q , (2.5)
The density of the invaded block rapidly increases (Fig. 2.3e) and eventually reaches 1/2. At this point, altruists' effective utility becomes negative, pushing them to leave for other lower density blocks (Fig. 2.3f). As previously, altruists gather in another single block of identical density ⇢ a = pQ⇢ 0 . The invasion has led to a slight decrease of the density of egoist blocks to ⇢ e <⇢ E ,a n dt h e r e f o r et oas l i g h ti n c r e a s eo fe g o i s t s ' utility, u e = u(⇢ e ) >u(⇢ E ).S u c c e s s i v ei n v a s i o n so ft h eb l o c kp a r t i a l l yfi l l e db ya l t r u i s t s are possible until ⇢ e decreases down to the value ⇢ ⇤ e such that u(⇢ ⇤ e )=u(⇢ a +1/H). This leads to ⇢ ⇤ e =1-pQ⇢ 0 -1/H (⇢ ⇤ e > 1/2 as long as p<p high ). The equality of utilities implies ũ(p)=u(⇢ a )=2pQ⇢ 0 +2/H.W h e np = p high ,thefinal(lo w est)egoistdensit y reaches the optimal value ⇢ ⇤ e =1 /2 and no further improvement in average utility is possible: ũ(p)=1(to simplify the discussion, we ignore here corrections of order 1/H that depend on the parity of H). This description remains valid for larger altruist concentrations, the only difference being that, at the end, the additional altruists form stable blocks with densities ⇢ a =1/2.

In summary, the evolution of the average utility ũ follows:

8 > < > : ũ(p)=2-2⇢ E for p  p low ũ(p)=2pQ⇢ 0 +2/H for p low  p  p high ũ(p)=1 for p ≥ p high (2.6)
Our analysis predicts that plotting ũ as a function of the rescaled altruist proportion p ⇤ = p/p high =2pQ⇢ 0 should lead to a universal transition starting at p ⇤ =2-2⇢ E ' 0.586 and ending at p ⇤ =1.S i m u l a t i o n sp e r f e c t l yc o n fi r mo u rc a l c u l a t i o n s( F i g .2 . 2 b ) .

Discussion

Our model illustrates the complexity of the dynamics produced by two types of agents, even when they follow simple rules. Introducing altruists into a population dominated by egoists increases the average utility much more rapidly than expected from a linear projection. The interplay between the different behaviors leads to complex "catalytic" phenomena. By catalytic, we mean that altruists are not "consumed" once they coordinate egoists, and can continue to help egoists finding the optimal configuration indefinitely. The global utility increase per altruist can be computed easily: δU altr ⌘ (U (p) -U (p =0))/N A ' (1 -0.56)⇢ 0 QH/(p⇢ 0 QH)=0.44/p.W h e np =1/Q, δU altr ' 0.44Q. Each altruist induces a utility change proportional to the system size, which becomes infinite for infinite systems. Interestingly, while the stationary state of a system composed of a single type of agents (either egoists or altruists) can be mapped to an equilibrium state, this is no longer the case when including two types of agents, except if some restrictive conditions are met [START_REF] Grauwin | Competition between collective and individual dynamics[END_REF]. In a thermodynamic analogy, the utility function can be mapped (in the zero temperature limit considered here) to a chemical potential, as shown in [START_REF] Lemoy | Socio-economic utility and chemical potential[END_REF], when a single type of agents is present. If a system with both egoist and altruist agents could be mapped to an equilibrium system, chemical potentials could be defined as µ e (⇢ a ,⇢ e )=u(⇢ a +⇢ e ) and µ a (⇢ a ,⇢ e )=u altr (⇢ a +⇢ e ).A s chemical potentials derive from a free energy, their cross derivatives would be equal, @µ e /@⇢ a = @µ a /@⇢ e ,l e a d i n gt ou 0 (⇢)=u 0 altr (⇢). This equality is not satisfied as seen from Figs. 2.1 and 2.4, showing that the system reaches a non equilibrium steady state.

We are well aware that simple mo dels do not allow to draw any rigorous conclusion about what is going on in the real world [START_REF] Venturini | Fill in the gap: A new alliance for social and natural sciences[END_REF], Ostrom, 2010, Jensen, 2018]. While Schelling's segregation model neatly shows that one cannot logically deduce individual racism from global segregation, it may well be that for some towns racism is one cause of segregation, for some others not; at any rate the reasons behind urban segregation are far more complex than those that any simple model can come up with. Simple models can be helpful to analyze some interesting phenomena, the origin of which may be obscured in more complicated realistic settings. Ours may help thinking about the effectiveness of coordination by an infinitesimal proportion of altruist agents, but it cannot be directly applied to real systems. Real agents do not behave like these virtual robots: they are able to put their actions into context, to anticipate the behavior of the others and moreover, they disagree about what is the social "optimum" [Jensen, 2018[START_REF] Latour | Politics of explanation[END_REF].

In this chapter we discussed the limitations of simple statistical physics models of society and the complex dynamics which can emerge from simple simulated models. In the next chapter, we explore the dynamics of a real world system using the dataset of Vélo'v users, a bike sharing system based in Lyon. We will illustrate the advantage of using temporal data and the difference between global evolution of the system and individual evolutions of its units.

Dynamics of Bike Sharing System Users

Introduction

Bike Sharing Systems (BSS) have been developing rapidly all over the world in the last decades, being now present in more than 500 cities. The number of studies of BSS has followed a similar pattern, focusing on 3 topics : quantifying BSS characteristics, describing users' socio-demographic profiles and evaluating its impacts on environment and public health.

The automatic recording of BSS activities has allowed a quantitative description of many BSS characteristics: Circadian and monthly activity patterns (see [START_REF] Borgnat | Shared bicycles in a city: a signal processing and data analysis perspective[END_REF], Côme et al., 2014]), average speed ( [START_REF] Jensen | Characterizing the speed and path of shared bicycle use in lyon[END_REF]), patterns of bicycle flows over the cities (see [Côme et al., 2014, Jensen et al., 2010, Borgnat et al., 2011, Borgnat et al., 2013]) and influence of weather conditions ( [START_REF] Borgnat | Shared bicycles in a city: a signal processing and data analysis perspective[END_REF]). The knowledge derived from these studies, especially on bicycle flows between stations (see [Côme et al., 2014, Tran et al., 2015]) and the prediction of bike reallocation schedules ( [START_REF] Zhang | Bicycle-sharing system analysis and trip prediction[END_REF]), can help the management of station balancing (see [START_REF] Singla | Incentivizing users for balancing bike sharing systems[END_REF], Côme et al., 2014, Côme and Oukhellou, 2014]), one of the main financial challenges of BSS [START_REF] Yang | Bike-sharing systems in beijing, shanghai, and hangzhou and their impact on travel behavior[END_REF]).

Socio-demographics profiles of BSS users differ generally from the overall cities demographics. Studies carried out in Europe and North America (see [START_REF] Beecham | Exploring gendered cycling behaviours within a large-scale behavioural data-set[END_REF], LDA-Consulting, 2012, Ogilvie and Goodman, 2012, Shaheen et al., 2012, Fuller et al., 2011, Raux et al., 2017]) have shown that users are more likely to be young, male, with a high level of education and living in the city center.

Finally, several studies have described the impact of BSS policies on environment and public health (see [START_REF] Pucher | City cycling[END_REF]). [START_REF] Shaheen | Bikesharing in europe, the americas, and asia: Past, present, and future[END_REF], Shaheen et al., 2011] have listed the benefits of BSS: Emission reductions, individual financial savings, physical activity benefits, reduced congestion and facilitation of multimodal transport connections. Yet, other studies question the real impact of BSS on some of the latter. Notably [START_REF] Shaheen | Public bikesharing in north america: Early operator and user understanding[END_REF] showed the relatively low impact on people favorite mode of transportation. In particular [START_REF] Fishman | Bike share: A synthesis of the literature[END_REF], Midgley, 2011, LDA-Consulting, 2012, Buttner et al., 2011] exhibited, for several cities in Europe and Canada the low substitution rates from car usage to BSS. Most BSS riders are indeed people who used to walk and take public transportation.

Among all the research axes cited, questions remain on the commitment of BSS subscribers in the long term. This is due to the lack of accurate trip datasets over long periods of time, as mentioned in [START_REF] Fishman | Bike share: A synthesis of the literature[END_REF]. Some articles have tried to characterize travel behaviors using surveys, such as [START_REF] Guo | Identifying the factors affecting bike-sharing usage and degree of satisfaction in ningbo, china[END_REF], Raux et al., 2017]. But the temporal evolution of users has never been deeply investigated. This is the reason why in this chapter we approach BSS travel behaviors and usage rates under the temporal angle. We address questions related to BSS sustainability, such as : how long do users remain active over the years ? Does their activity increase, decrease or remain stable? Do these trajectories depend on their level of activity? These questions are addressed using a five years long dataset covering about 150,000 long-term distinct users, among which 13,358 have stayed in the system for the whole period. We follow previous work on Lyon's BSS, Vélo'v, by [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF] which, using a single year dataset (2011), characterized users according to their intensity and frequency of uses at different time scales (day, week, month and year). This work found 9 classes of users, ranging from 'extreme users', that use Vélo'v twice a day on average to 'sunday cyclists', who only use the system a few week-ends per year. Using as i n g l ey e a rd a t a s e tt oc l a s s i f yu s e r sh a sh o w e v e rt w om a i nl i m i t a t i o n s . F i r s t l y ,t h e r e is no way to distinguish between two possible interpretations for a user that appears to be very active from September to December. This could correspond either to (a) someone arriving in town in September that remains very active for the months/years to come or (b) someone who for an unknown reason uses the system only in those months. The second limitation arises from the impossibility to test the stability of users' characteristics over years, which would allow to interpret them as real user properties. For example, do users classified in 2011 as 'sunday cyclists' retain this characteristic over the years? Have they only used Vélo'v in this way in 2011 or is this pattern a more personal -and stable -use of the system that lasts for longer periods?

The work presented in this chapter is one of the first giving a detailed description of how different segment of customers use Vélo'v over years. A recent article from [START_REF] Jain | Does the role of a bicycle share system in a city change over time? a longitudinal analysis of casual users and long-term subscribers[END_REF] highlighted the lack of temporal analysis on BSS' users and importance of tracing longitudinal usage trends. Our study could open the way to the establishment of a methodology to dynamically assess impact of BSS policies and other transportation facilities on different segment of users.

After presenting our 5-years dataset in Section 3.2, we start by describing the overall system stability. We, then, show the heterogeneous individual trajectories masked by this overall system stability in Section 3.4. Finally, we compute in section 3.5 user classes using a similar approach to [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF] and break down individual evolutions from section 3.4 using the classes we computed.

Dataset

The Vélo'v program started in 2005 in Lyon, France. The Vélo'v network now has 340 stations, where roughly 4000 bicycles are available. The stations are in the street and can be accessed at anytime (24/7) for rental or return. More information about the history of Vélo'v and the deployment of stations can be found in [START_REF] Borgnat | Shared bicycles in a city: a signal processing and data analysis perspective[END_REF]. The dataset used in this chapter records all bicycle trips from 2011/01 to 2015/12 for the Vélo'v system. It contains more than 38 million trips made by more than 3.8 million users. Each trip is documented with starting and ending times, duration, a user ID code and a tag describing the class of user (year-long subscriber, weekly or daily subscription, maintenance operation, etc). Data are filtered according to the process used in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], keeping only year-long users and eliminating any anomalies. This leads to a subset of the original population containing 147,354 longterm users. For each person, we count years from the first active day: For example, a user appearing in the records for the first time on March 16 th , 2011 will end the first adapted year on March 15 th ,2 0 1 2 . T oa v o i dbo u n d a r ya r t i f a c t sf o ru s e r st h a ta r e active over several years, we stop recording trips at the anniversary date in 2015, even if there are recorded trips later in 2015.

Note that our elementary unit of analysis is therefore the 'person-year', i.e. the vector of 21 features for each user and each year. One person can therefore appear several times (up to 5) and change group from year to year. One could adopt a different point of view, using persons as the entities and computing a single vector for each of them, averaged over their whole period of activity. This would have two drawbacks: masking the single user trajectories over the years and comparing vectors computed over different periods (from 1 to 5 years). Comparing the third and fourth columns of Table 3.3 shows that using the 'person-year' or the 'person' as the basic entity leads to roughly the same proportions for the different classes. We then retain the 'person-year' description, which allows studying users' trajectories.

Overall evolution

We first analyze the global system evolution over the 5 years. Table 3.1 shows that there is a steady increase in the number of users and trips. However, the average number of trips per user remains remarkably stable around 92 trips/year, despite the large variability (standard deviation larger that the average). A similar general temporal trend is found in [START_REF] Jain | Does the role of a bicycle share system in a city change over time? a longitudinal analysis of casual users and long-term subscribers[END_REF].

Individual evolutions

The overall system stationarity (slow increase of user numbers) hides a great variability at the individual level that can be uncovered only using long-term datasets at the individual level as ours. Every year, there is a strong user renewal, as the majority of users leave the system after their first year of activity and are replaced by a greater number of new users. Figure 3.1 shows that every year the new users represent around 35% of the total. Then, they progressively leave the system, in a quite predictable way: They represent 26-28% of users the year after and 11-12% two years later. The only exception is the 2011 cohort, which by lack of data over the previous years, also includes users that entered the system before 2011.

Most users leave the system after one year

Analyzing user activity over calendar years as in Figure 3.1 is confusing, since users enter the system at any time during the year. To follow individual evolutions, we have to shift the different starting dates to a common origin using 'adapted' years as explained above. Figure 3.2 shows that a large majority of users (60.8%, blue rectangle) quit after a single year of practice. These users are significantly younger than more loyal users (24 years old against 31), more likely women (51.1% of men compared to 59.1%) and less active: their median number of trips is 47, to be compared to 91. This low activity is mainly explained by a shorter time span of their activity (median close to 9 months instead of the whole year). This means that many of them stop using the system before the 12-month validity of their subscription, because they leave Lyon, buy a bike, change job. . . Almost 20% of users stay in the system for 2 years (yellow rectangles in figure 3.2). Note that their activity is significantly lower than that of more loyal users, that will stay in the system for 3 or 4 years (89 trips against 100, p-value < 2.2 ⇤ 10 -16 ). In this case, this reduced activity cannot be explained by a shorter activity time span. These users are consistently less active over the whole year, a feature that allows to predict a higher chance of quitting the system the following year as we will check below. When Figure 3.2 -Percentages of users leaving the system at the end of different adapted years. For each group of users is given the median number of trips per year, the median number of active months, the median age and the percentage of men. For example 'Blue users' stopped at the end of their first adapted year, after a median number of 8.9 months of activity. They represent 60.8% of first year users. They had a median number of trips during that year of 47, a median age of 24 years old and 51.1% were men. Yellow users stopped at the end of their second adapted year. They had a median number of trips during their first year of 89 and during their second year of 35. They stopped after a number of 7.7 active months during their second year. these users reach their second (and last) active year, their activity becomes quite similar to the blue users, as their time span is reduced to 7.7 months and their activity much lower than in their first year (35 trips instead of 89).

Almost 9% of users stay in the system for 3 years (orange rectangles in figure 3.2). Again, their activity, even two years before leaving the system, is significantly lower than that of more loyal users (100 trips against 104, p-value < 2.2 ⇤ 10 -16 ). This activity progressively diminishes over the years, reaching a very low value on the third and final year (36 trips over 6.3 months).

Finally, 12.7% of users stay in the system for at least 4 years (red rectangles in figure 3.2). Their activity is consistently higher than average, and these users are older and more often men. Their activity also progressively diminishes over the years, a feature that we study in more detail below.

The most striking result is the high proportion (60.8%) of users that quit after a single year of practice (called 'leavers' hereafter). To the best of our knowledge, this surprising figure was previously unknown. It is worth noting however that this figure might be slightly overestimated. The reason is that users are identified through the ID of different cards, the most common being Velo'v own card (30.3% of the users), public transportation card (Tecely, 59.7%) and train card (Oura, 5.2%). The point is that the Tecely cards have to be renewed every 5 years. In some (uncontrolled) cases, this leads to a change of ID, which our analysis interprets as if the user had left the system and another had entered it. To estimate the proportion of incorrectly labeled exits from the system, we note that only 46.6% of Velo'v cards users give up after one year, the corresponding figure being 61.3% for Tecely users. As Velo'v cards do not go through the yearly renewal process, this percentage could represent a lower bound on the 'leavers' proportion, if we assume that the proportion of leavers does not depend on the card used, which seems unlikely as using the specific Velo'v card suggests a higher loyalty. To obtain another estimation, we may assume that all renewed Tecely cards (20% per year) change their ID. This would mean that the 61.3% figure is an overestimation of the real figure (61.3 -20)/0.8 = 51.6%. These estimates converge to ap r o po r t i o no fl e a v e r sbe t w e e n5 0a n d5 5 % .

We noted ab ove that the loyalty of users was correlated to their activity. Figure 3.3 shows the general trend over all users. It confirms that the higher the intensity of use, the higher the probability P s to stay in the system. This result can help predicting users' loyalty.

Long-term users are older, more likely men and more urban than average

Let us now focus on the most loyal users, the 25,963 users that have been active for at least 3 years, which we now call 'long-term' users. Comparing them to those that leave after a single year reveals interesting facts about their specific characteristics. ) and live within the Lyon-Villeurbanne urban area (85.3% against 81.7%, p-value < 2.2 ⇤ 10 -16 ) Table 3.2 shows the proportions of long-term users for different 10-years slices. Clearly, loyalty steeply increases with age, from 25.2% for 13-22 years old users up to 64.7% for 63-72 years old users. Men are over-represented among the long-term users for all ages, but the difference is highly significant among younger users. It would be interesting to understand why there are (comparatively) so few young women among the most loyal BSS users.

Finally, we study how long-term users change their activity over the years. For each user, we computed the percentage of change in the number of trips per year from one year to another. Figure 3.4 shows that only one quarter (26.5%) maintain their number of trips within a ±20% range. Roughly two-thirds (61.8%) users lower their activity, almost halving it (median decrease 42.3%). The remaining third increases its activity (median increase 42.6%). The median evolution of long term users is a decrease of activity by 16.3%.

We now apply a k-mean algorithm to the set of p erson-years to describ e to finer level the evolution of users, we discuss the number of clusters and compare our findings to the results of [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], in which the authors used the same methodology on a 1-year dataset.

Classes of users

In this section, we compute users classes on our 5 years dataset, using a similar approach to [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], and offer a brief description of them. Computing these classes allows us to compare our results to the one found in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF]. This comparison illustrates the effect of temporality on users classification accuracy.

Computing users classes

From this dataset, we compute the same 21 normalized features characterizing the activity as in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF]. For each person, these features quantify the intensity and regularity of use over the year (14 features) and the week (7 features).

• trips week,a v e r a g e dn u m be ro ft r i p sm a d epe rw e e k ,c a l c u l a t e do v e rt h ew e e k s • trips year,totalnumberoftripsmadeovertheadaptedyear,normalizeddividing by 1.5 times the interquartile range of the distribution for all users (i.e. the difference between the lower and upper quartile of the distribution).

• trips month1 -12,n u m be ro ft r i p spe rm o n t h ,n o r m a l i z e dt oat o t a ls u mu n i t y , months are ranked from one to twelve, month 1 being the month with the highest number of trips and month 12 the month with the lowest number of trips.

As explained in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], there is some correlation and redundancy between intensity and regularity features. Nevertheless, a simple K-means clustering method (see, e.g., [MacKay, 2003]) is used, coupled with statistical appraisal and careful analysis of the results, as our main intent is to create and interpret a relevant typology, not to find well-defined, pre-existing, classes. Also, we prefer to use the original variables instead of PCA axes, because this makes the interpretation of the obtained classes straightforward.

To cho ose the numb er of clusters, we studied as [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF] the partitions obtained when choosing from three to twelve clusters. However, as shown on figure Figure 3.5 -Visualization of the users-year on the two main axis given by principal component analysis (PCA) 3.5, there is a continuum distribution of users-year and therefore no clear separation to split the clusters. Moreover we also computed the Akaike Information Criteria (AIC) for the different number of clusters k. The AIC is defined as follow:

AIC(k)=-2L(k)+2q(k) (3.1)
Where -L(k) is the negative maximum likelihood for k clusters and q(k) is the number of parameters of the model with k clusters. Hence, the AIC represents the trade-off between a model which clusters well the data (given by the likelihood) and the complexity of the model. The optimal number of clusters k is in theory

argmin k [-2L(k)+2q(k)].
However after plotting AIC(k) (Figure 3.6), we observe that there is no clear knee showing an optimal value. Hence, we chose nine clusters for two reasons. Firstly, we found that as in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], this number of clusters represents the best compromise between a reduced but rich enough description (differentiating for example week-end users from week users), without introducing uninformative clusters. Secondly, this number allows a simple comparison of our results with the study from 2014.

Ad e t a i l e dd e s c r i p t i o no ft h en i n ec l a s s e si sg i v e ni nT a b l e3 . 3a n dF i g u r e3 . 7 .

User Classes

The nine classes correspond to different profiles of use. There are 6% of 'one-off' users, who make on average only 3 trips per year, generally the same month and then disappear from the database. Another almost 12% of users are mainly active in week-ends, either for shopping (Saturdays) or leisure (Sundays) (second line of Table 3.3). The last 6 lines of Table 3.3 represent users that show a regular activity over the year and differ mainly by their intensity of use, from twice a month (regular0 class, gathering 27% of users) to nearly twice a day (regular5, 1% of users). The part-time class is quite peculiar: we will show below that it can be interpreted as the class where users end up for the last year of activity.

Evolution of user classes

This section answers to the question: what are the differences between stable users in terms of practice, i.e. what is the dynamics of stable users within the classes? These matrices give key informations about the evolution of stable users in the system, it shows:

• the overall stability of classes (diagonal terms). The high values found around the matrix diagonals (light colors in Figures 3.8b and 3.8a) show that many users remain in the same class over several years : the probability to stay in the same class is higher than any other probability (except leaving). As discussed briefly below, the second highest probability corresponds to a shift to the neighboring class with lower activity. The matrix also shows that this 'class fidelity' is correlated to the intensity of use: For example, on the first year P I5!I5 =3 0 .2% >P I4!I4 =2 2 .8% >P I3!I3 =1 7 .5% . . . This intensity is therefore a good predictor of future behavior : Staying in the same class or, as discovered earlier (Figure 3.3), leaving the system.

• the decrease of activity for users that remain active (asymmetry of the non diagonal terms). We observe the upper parts contain higher values than the lower parts. As the lines in the graph are ordered by intensity, this means that users have a high probability of reducing their activity from one year to another. This joins results from Figure 3.4.

• in each year, a high proportion of users leave the system (last column). However the probability to leave the system decreases continuously as the classes increase in intensity of use. Note that since the entity is a 'person-year', these counts do not directly represent proportions of individuals, because users that stay in the system for long periods are over-represented. However, the comparison with the proportions obtained for year one (third column), which correspond to real users, shows that this effect is relatively weak. #trips/year is the median number of trips in a year for each class.

Length of use and activity

Let us now break down the length use, first mentioned in 3.2. The increase of use from classes regular0 to regular5 arises from the combination of two factors: both the number of active weeks (figure 3.9) and the number of trips per active week increase. For example, regular5 users are almost 30 times more active over the year than regular0 users (695 instead of 25 trips, see Table 3.3), because they are at the same time more often active (50 active weeks instead of 12) and more active during these weeks (14 trips per week instead of 2). Note that the decrease of the number of active weeks is not due to a simple seasonal effect: Figure 3.10) shows that active weeks of regular0 users span a median period of nearly 40 weeks (between the first and the last trip of the year).

Comparing the 5-years and 1-year classes

When comparing the classification obtained here to that found over a single year [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], we note many similarities and a major difference. As in [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF], a 'one-off' and a 'week-end' class are found, with similar proportions, as well as six 'regular' classes differing mainly by their intensity of use. The major difference is the 'part-time' class, that represents 3.6% of users, instead of 29% for the single year classification (summing their 'intensive and part-time' and 'irregular' classes). This means that those two 1-year classes mostly gathered users that have in fact a regular behavior appearing to be 'part-time' because they are observed over a too short period of time. For example, a user starting in September 2011 will appear active only for (at most) 4 months, even if they keep the same activity over the subsequent (unobserved) year. Figures 3.8b and 3.8a show that the 'part-time' class gathers users that massively leave the system at the end of the year (nearly 90% the first year and 70% the second). Year after year, the 'part-time' class is filled again by users coming from all (previous year) classes, as shown by the numbers in the 'part-time' column in Figures 3.8b and 3.8a. Therefore, this class does not represent a stable behavior of a class of userspeople being active every year only 3 months -but the class where users end up for their last year of activity.

Discussion

As seen in the introduction, there was a lack of in-depth studies on the temporal evolution of long-term bicycle usage, mainly due to the lack of long-term datasets. Thus, we studied the temporal evolutions of year-long Vélo'v users thanks to a unique dataset spanning over 5 years. After adapting the data, we extended the method from [START_REF] Vogel | From bicycle sharing system movements to users: a typology of vélo'v cyclists in lyon based on large-scale behavioural dataset[END_REF] to characterize temporal patterns and we showed that using a5 -y e a rd a t a b a s ec o r r e c t st h e1 -y e a rc l a s s i fi c a t i o nb ya v o i d i n gt h eo v e r e s t i m a t i o no f part-time users (from 29% to 3.6%). This indicates that the seasonal effect in bike usage is much smaller than expected. Also, users' yearly activity was organized in three main classes: 6% of 'one-off' users, with only 3 trips per year; 12% of 'week-end' users and the rest presenting a regularly distributed activity over the year. We divided the latter class into 6 groups with considerable differences in numbers of trips (from twice a month to twice a day). From these classes, we studied the evolution of activity for longer times and found two main trajectories: About 60% of the users stay in the system for one year at most and show a low median activity (47 trips); the remaining 40% of users are more active (median activity of 96 trips in their first year) and remain continuously active for several years (mean time = 2.9 years).

This high proportion of leavers can be explained by many reasons : moving to other towns, buying one's own bike, finding the service unsatisfactory. . . It would be interesting to ascertain the relative proportions of each. Note that considering the number of trips (and not of users) leads to a more stable picture, as the 40% of stable users perform around 60% of the annual trips. Their activity is relatively stable, slightly decreasing over the years. We showed that this long-term behavior strongly depends on the user initial class, as fidelity rapidly increases with the number of trips observed the first year.

On the socio-demographic point of view, stable users are generally older than average users (30 to 40 years old) and live closer to the city center. This result agrees with previous articles socio-demographically characterizing BSS users population (see [START_REF] Beecham | Exploring gendered cycling behaviours within a large-scale behavioural data-set[END_REF], LDA-Consulting, 2012, Ogilvie and Goodman, 2012, Shaheen et al., 2012, Fuller et al., 2011, Raux et al., 2017]).

Acomprehensiveanalysisofthereasonofevolutionpatternswouldbeaninsightful extension of this study. Though data about the motivations of users are not yet available, a survey would help addressing questions on the motivations behind the patterns such as why users leave the system. Such answer would complement our description.

This analysis is a first step to understanding usage trends and monitoring the evolution of users' segments which could help authorities to design more adapted systems.

This chapter describes for the first time in great detail the evolution of customers of a large BSS and suggest further work on important policy issues which we cannot address for lack of appropriate data. So far, one study performed a similar analysis to ours. [START_REF] Jain | Does the role of a bicycle share system in a city change over time? a longitudinal analysis of casual users and long-term subscribers[END_REF] found similar demographic characteristics to long-term users and general system's usage (slowly increasing over years). The development of temporal study on the evolution of usage and commitment for other BSS in the world would be of high profitability, in order to compare the evolution of trends and socio-demographics in the world and releasing BSS more adapted to users' segments.

In this chapter, we studied individual dynamics of users using mobility data. Now, after individual dynamics, we would like to study collective dynamics. In the next chapter, we explore temporal community detection on scientometric networks. More particularly, we investigate the differences between two approaches for generating automatic history of scientific research.

Introduction

Networks are a convenient way to represent real-world complex systems, such as social interactions [Newman, 2003, Barabási et al., 2002, Onnela et al., 2007], metabolic interactions [Boccaletti et al., 2006, Barabási andOltvai, 2004], the Internet/world wide web [Pastor-Satorras andVespignani, 2001, Barabási and[START_REF] Barabási | [END_REF], transportation systems [START_REF] Dall'asta | Vulnerability of weighted networks[END_REF], Barthélemy, 2011], etc. For several systems it is interesting to find and describe areas of the network which are more densely connected, i.e. the communities of the network. In 20 years of complex networks history extensive work was conducted on community detection in static -non evolving-networks, see [Newman, 2006, Blondel et al., 2008, Fortunato and Barthélemy, 2007] and the review [START_REF] Fortunato | Community detection in networks: A user guide[END_REF] for an overview on community detection in static graphs.

However, many networks have a temporal dimension and need a dynamic mesoscopic description at risk of non-negligible information losses if studied as static networks. Therefore the description of large temporal graphs has been a hot topic of research for the last decade, see the excellent reviews [START_REF] Holme | Temporal networks[END_REF] and [Holme, 2015] for a complete description of temporal networks. Most recently the detection of dynamic communities, that is communities on temporal networks, has become one of the main interests in network science, as temporal networks require to adapt the methods of static community detection. So far no consensual method was found and around 60 methods have been proposed to try to detect dynamic communities evolving with temporal networks. A total of 4 published reviews try to classify and summarize them [START_REF] Aynaud | Communities in evolving networks: Definitions, detection, and analysis techniques[END_REF], [START_REF] Hartmann | Clustering evolving networks[END_REF], [START_REF] Masuda | AG u i d et o Temporal Networks[END_REF] and [START_REF] Rossetti | Community discovery in dynamic networks: A survey[END_REF].

In the most recent one ( [START_REF] Rossetti | Community discovery in dynamic networks: A survey[END_REF]), these methods are classified into 3 main categories: (a) instant optimal,( b )temporal trade-off and (c) cross-time.

In this chapter we propose a method inspired from [START_REF] Morini | Revealing evolutions in dynamical networks[END_REF], which falls into category (a). These methods aim to detect clusters at different times t, i.e. for many snapshots of the temporal network. As these clusters are only dependent on the state of the network at time t, it is then necessary to match the communities at different t with some similarity measures, e.g. Jaccard based [START_REF] Morini | Revealing evolutions in dynamical networks[END_REF], Lorenz et al., 2018, Greene et al., 2010], core-node [START_REF] Wang | Commtracker: A corebased algorithm of tracking community evolution[END_REF]. Methods in category (b) define clusters at t depending on current and past states of the network. Clusters are incrementally temporally smooth. However such methods are subject to drift as clusters are added up to each other locally. There is no compromise between temporal smoothness and 'optimal' partition at time t,seeforexample [Rossettietal., 2017, Guo et al., 2014, Görke et al., 2010, Görke et al., 2013]. Finally, in category (c) clusters at t depend on both past and future states of the network, see [START_REF] Duan | Community mining on dynamic weighted directed graphs[END_REF], Mucha et al., 2010, Matias and Miele, 2016, Ghasemian et al., 2016]. Clusters are completely temporally smooth and not subject to drift, but they do not respect causality as communities at t are determined using network's information at t + n, i.e. communities at time t can change depending on what comes next, which makes communities temporally unstable. This limitation also makes these methods difficult to use on-the-fly, as it requires full knowledge of the history.

This chapter has two goals : (1) present tools to describe community dynamics in history of science, such as : the description of the emergence and death of scientific disciplines, the description of merge and split of two disciplines; (2) illustrate the difference between global optimization (category (c) methods) and local temporal optimization (category (a) methods). We describe a method in-between which returns a mesoscopic description of the network, which we call: temporal streams. The main difficulties for meta-community detection methods are to find the right temporal smoothing and to quantify the 'stability' of communities. It is difficult to distinguish if changes between snapshots are due to structural evolution of the community or algorithm instability, as static community detection methods used at each time t can find different communities for a same topology (see [START_REF] Rossetti | Community discovery in dynamic networks: A survey[END_REF] for a complete description of pros and cons of each clustering category). In this chapter we propose an algorithm which aims to find balance between temporal inertia (smoothness) and 'optimal' community at particular time t.W ec o m p a r et h i sm e t h o dt ot h e most basic algorithm which runs a Louvain method on the aggregated network. The latter can be assimilated to a category (c) method in [START_REF] Rossetti | Community discovery in dynamic networks: A survey[END_REF]. We introduce the platform BiblioMaps that we used for visualizing dynamic communities. We then describe the methods we used to analyze differences between partitions: mutual information (MI) measures and bipartite network (BN) representation. We see that MI based measures are interesting but give a limited amount of information on how different two partitions are, whereas bipartite network representation allows to see how streams split between partitions. We used the methods on two bibliographic datasets: (1) the scientific publications of the ENS Lyon and ( 2) publications related to the field of wavelets. We find that the basic aggregated method finds partitions which present similarities with our method, but differs in cases where optimal partitioning at time t is preferred over smoothness of the history.

Methods

We start by presenting the two building blo cks used in the algorithms we want to compare: how we define and partition a Bibliographic Coupling (BC) network and how we match clusters from successive time period to create streams (meta-clusters).

Bibliographic Coupling partitioning

Given a set of publications on a given period, a Bibliographic Coupling (BC) network can be defined based on the relative overlap between the references of each pair of publications. More specifically, we compute Kessler's similarities

! ij = R ij / p R i R j
, where R ij is the number of shared references between publications i and j and R i is the number of references of publication i.I nt h eB Cn e t w o r k ,e a c hp u b l i c a t i o nc o rresponds to a node and two publications i and j share a link of weight ! ij .I ft h e y don't share any reference, they are not linked (! ij =0 ); if they have an identical set of references, their connexion has a maximal weight (! ij =1 ). In this chapter, we considered that the link between two publications is only meaningful if they share at least two references and we impose ! ij =0if they share only one reference.

We use weighted links to reinforce the dense (in terms of links p er publication) regions of the BC networks. This reinforcement facilitates the partition of the network into meaningful groups of cohesive publications, or communities. We measure the quality of the partition with the modularity Q( e q . 4 . 1 ) ,aq u a n t i t yt h a tr o u g h l y compares the weight of the edges inside the communities to the expected weight of these edges if the network were randomly produced:

Q = 1 2Ω X i,j h ! i,j - ! i ! j 2Ω i δ (c i ,c j ) , (4.1)
where ! i = P j ! ij is the sum of the weights of the edges linked to node i, c i and c j are the communities containing respectively nodes i and j, δ is the Kronecker function (δ(u, v) is 1 if u = v and 0 otherwise) and Ω= 1 2 P ij ! ij is the total weight of edges. We compute the graph partition using the efficient heuristic algorithm presented in [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF].

Matching communities from successive time periods

Given the sets of communities {C t 1 ,...C t kt } in each time windows t,theproblemathand is to identify a set of relevant historical communities, or streams, that correspond to a chain of communities from successive time periods (at most one per period). In order to decide which community of a given period should be added to a chain of communities from previous periods, we need to use some measure to assess the similarity between communities from different time periods. In the dynamical communities literature, one method often use is the Jaccard index, based on a proportion of shared nodes between clusters of successive and overlapping periods (see e.g. [Claveau andGingras, 2016, Morini et al., 2017]). One drawback from this method is that because of the use of overlapping periods, there is no bijection between the publications and the streams (a given publications can be part of several streams).

Here, we take advantage of the BC nature of our network, which ensures that links can exist between nodes from different time periods (publications from different periods can have common references). We can thus define a similarity measure between two clusters C a and C b from different periods either by the total sum of the links between pairs of publications from these clusters Ω a,b = P i2Ca,j2C b ! i,j or by a normalized version of this sum ! a,b =Ω a,b /|C a ||C b |, which is comprised between 0 and 1. While these two measures can appear quite intuitive, each of them has some drawbacks as well: using Ω a,b may sometime bias the construction of the streams by linking two "large" (in terms of publications) but dissimilar top clusters. On the opposite, using ! a,b may sometime put too much emphasis on one cluster (e.g. a strong similarity between clusters of very different size over a second-best similarity between cluster of similar sized).

To be coherent with our construction of clusters from each time period by maximizing the modularities within each time period, we propose here to use a modularitybased concept on the set of clusters from 2 successive time periods. We, thus, use as similarity measure the quantity δQ =Ω a,b -Ω a Ω b /2Ω A,B which corresponds to an increase in the modularity of the BC network built from the two periods A and B.

Matching Algorithm Only compare pairs of communities (a, b) with a minimum similarity ! a,b > Θ=10 -6 . Define the best match of each cluster by the one maximizing δQ. for each temporal window do Define the predecessor of each cluster as its best match from the previous time period. Define the successor of each cluster as its best match from the next time period. end Two clusters are said to b e paired if they are predecessors / successors of each other. If a cluster is not the successor of its predecessor, we have a split. If a cluster is not the predecessor of its successor, we have a merge. Streams are defined as chains of paired clusters.

Different algorithms used to define historical streams

We investigated the results of four algorithms to define historical communities, or streams, on a given dataset of publications over a long period, which we cut into successive periods of ∆T years. Two methods have a temporally global approach (GA, GPA), and two methods have a temporally local approach (BMLA, BCLA). In fact results between (GA and GPA) and (BMLA and BCLA) are very close (see Annex B). For this reason and for the sake of illustration, we only present the GA and BCLA methods. The two other methods (GPA, BMLA) and their results are shown in Annex B.

Global Algorithm (GA)

Building the global BC network by taking into account all the publications in the dataset, we simply define the streams as the communities maximizing the global mod-ularity found by running the Louvain algorithm. Since we are working in a single (large) time period, this approach does not yield any dynamical events such as splitting / merging of communities, but it provides a simple reference.

Best-Combination Local Algorithm (BCLA)

The BCLA is an incrementation of the work from [START_REF] Morini | Revealing evolutions in dynamical networks[END_REF]. On each time period, we run N independent runs (we used N =1 0 0 )o ft h eL o u v a i na l g o r i t h m . Because of the noise inherent to the Louvain algorithm, choosing the best-modularity partitions chosen in each time period are not necessarily the ones that best match each other across successive time periods. We propose the BCLA to optimize the inter-period combination.

BCLA Algorithm

Compute the Bibliographic Coupling Graph ; Split the dataset into temporal windows ∆t ; for each of the N =100partitions of the first period and each of the N =100 partitions of the second period do Run the matching algorithm to define the 2-periods streams; end Among the N ⇤ N defined streams, select the ones maximizing the modularity of the BC network on the first 2 periods. ; Define the "best combination" partitions of the first 2 periods as those corresponding to those streams; for each pair of successive temporal windows A and B,s t a r t i n gf r o mt h e second one do for each of the N =100partitions of the period B do Run the matching algorithm between these partition and the "best combination" partition of period A (known from a previous step) to define 2-periods streams; end Among the N defined streams, select the ones maximizing the modularity of the BC network on periods A and B; Define the "best combination" partition of period B as the one corresponding to those streams end Note that maximizing a global indicator over the T periods with N runs would take too long as there would be N T possibilities to explore. For this reason, we first choose the best combination between the first two periods (N 2 checks) and then we choose the "best match" one period at a time (N (T -2) checks). This algorithm returns temporal streams which we call BCLA-streams. These streams still maximize the modularity at each time t while using some cross-time information to improve the global modularity.

Choosing the value of the period T is a trade-off. It needs to be long enough so that communities within each period have enough articles to give meaning to the communities. But it also needs to be small enough compared to the total dataset duration Dataset Type Period N N BC ⇢ links <d> <w> Q GA Wavelets Thematic 1963-2012 6,582 5,568 0.0065 35.98 0.000719 0.677 ENS-Lyon Institution 1988-2017 16,679 14,389 0.0019 27.04 0.000175 0.919 Table 4.1 -Statistics on datasets investigated in the chapter. Type is the type of organization data come from. Period is the period over which spans the dataset. N is the number of publications in the dataset. N BC is the number of articles in the BC table. ⇢ links is the density of links in the BC network. <d> =( N BC -1) ⇤ ⇢ links , it indicates the average number of publications a given publication shares references with. <w>indicates the average link weight. Q is the modularity of the network using global partioning (GA). to see dynamics. After trying different periods, we chose, in the following, a period T =5years.

Akin to [START_REF] Claveau | Macrodynamics of Economics: A Bibliometric History[END_REF], these methods take advantage of local information to partition the data.

BiblioTools / BiblioMaps

All the datasets were extracted from the ISI Web of Knowledge Core Collection database1 . The bibliographic records were parsed and analyzed using Bibliotools, a Python-based open-source software and the historical streams figures were generated using the web-based visualisation platform BiblioMaps. Bibliotools and its extension BiblioMaps were developed by one of us and are available online2 . They were also used and presented in previous studies [START_REF] Grauwin | Mapping scientific institutions[END_REF], Lund et al., 2017[START_REF] Grauwin | Bibliomaps-a software to create web-based interactive maps of science: The case of ux map[END_REF].

Datasets

In this section, we present specificities of each dataset and the motivations to use them. Key informations are summarized in table 4.1.

ENS-Lyon Publications Dataset

The ENS-Lyon Publications Dataset contains all publications produced by researchers affiliated to the École Normale Supérieure de Lyon in natural science fields. It spans from 1988 to 2017 and contains 16,679 publications. The ENS-Lyon is an institution, hence this dataset exhibits publications well classified into academic departments with a relatively low level of interdisciplinarity, see [START_REF] Grauwin | Mapping scientific institutions[END_REF] for a first study on this dataset. In this chapter, we compare our temporal clustering methods to a temporal partition of articles following the laboratories of the ENS-Lyon. We call it our reference partition (P REF ).

(b) Historical streams computed from the ENS Lyon natural sciences publications. Streams were computed using our local method (BCLA).

Figure 4.1 -Labels on each stream correspond to the most frequent author name in that stream during a given period. Streams with the same color have close research topics (here the proximity of streams to each other is computed from the weight of BC network links between clusters of a same period). Bar height is proportional to the number of publications in a given year. Links between streams show the streams that are preceding/following each other.

Wavelets Publications Dataset

The Wavelets Publications Dataset contains all publications related to wavelets and spans from 1910 to 2012 (however the period before 1960 contains only a few publications). This dataset contains 6,582 publications, corresponding to all the publications of a list of 83 key actors in the field of wavelets selected by expert advice and bibliographic searches. See [START_REF] Morini | Revealing evolutions in dynamical networks[END_REF] where the dataset was initially presented.

The study of this dataset represents a difficult task because it emerged from the collaboration of several research fields, constituted by many entangled subfields. Based on the knowledge of field's expert, Patrick Flandrin from the physics laboratory of the ENS Lyon, we built manually a temporal partition drawing the history of wavelets.

We refer to this partition as P REF and compare our automatically generated partitions to this partition of reference. We acknowledge that this partition is not an absolute ground truth as it relies on the subjectivity of an expert. However, it gives an approximation of the field dynamics.

Results

As illustrated in Figures 4.1 and 4.2, the global method (a) does not include much dynamics in the historical streams it returns. GA-streams are flat in Figure 4.1a and have only a few splits/merges in 4.2a. On the opposite, BCLA-streams give a dynamical history of research for both datasets. In Figure 4.1b many streams remain flat due to the low multidisciplinarity of research between the different departments of the institution. However, we can see some splits corresponding to teams splitting to focus on different research topics (like streams 'Blichert-Toft/Lecuyer'). Similarly, many splits and merges occur in 4.1b.

As we observe these differences in dynamics, we compare the partitions for each dataset using two sets of measures to better describe their dynamics: (1) mutual information based measures and (2) measures from a bipartite network representation of the partitions. Then, we show some examples of major differences in partitioning that we spotted using bipartite network representation.

Normalized Mutual Information

The mutual information (MI) is a widely used measure for comparing community detection algorithms. It is defined as a measure of the statistical independence between two random variables (see eq. 4.2). In other words, if H(P X ) is the entropy associated with partition X and H(P Y ) is the entropy associated with partition Y -the entropy is a measure of how partitioned is our network, the more communities (here temporal streams), the higher the entropy-then MI(P X ,P Y ) represents the overlap of the two partitions. It gives an answer to the question: how much do I know about the partition P X when the partition P Y is given? Note that the mutual information is a symmetrical measure, that is MI(P X ,P Y )=MI(P Y ,P X ).S e e[ W a g n e ra n dW a g n e r , 2007, Kvålseth, 2017] for deeper description on mutual information.

MI(P

X ,P Y )=H(P Y ) -H(P Y |P X )=MI(P Y ,P X ) (4.2)
(c) Historical streams computed from the wavelets field of research publications. Streams are the reference streams determined manually.

Figure 4.2 -Labels on each stream correspond to the most frequent author name in that stream during a given period. Streams with the same color have close research topics (here the proximity of streams to each other is computed from the weight of BC network links between clusters of a same period). Bar height is proportional to the number of publications in a given year. Links between streams show the streams that are preceding/following each other.

MI is defined on [0, +1], therefore it is difficult to make sense of it without an upper-bound. There exists different ways to normalize the mutual information. The idea is to take into account the entropies of the partitions we consider, so that it is possible to gauge the proportion of mutual information between the partitions. Normalizing by the entropy of one of the partition, e.g. H(P X ) (see eq. 4.3) measures how much of the partition P X is included in the partition P Y .W ec a l lt h i sn o r m a l i z e d mutual information NMI X .I fi tr e a c h e si t sm a x i m u mv a l u e1 ,t h e ni ti sp o s s i b l et o retrieve all the information -all the partition-of P X from the partition P Y .H o w e v e r this measure does not take into account the size of the other partition, P Y .Ap a r t i t i o n P Y where each node would be its own community would make NMI X equals to 1 even though both partitions are very different. This measure then needs to be combined with at least another NMI which takes into account the relative size of both partitions (see eq. 4.4). Here the mutual information is normalized by p H(P X ) ⇤ H(P Y ), which shows how much of the two entropies overlap on a scale between 0 and 1. This expresses how similar are the partitions. It is equal to 1 when the partitions are the same. Moreover, this last NMI is symmetrical, so it takes into account both retrieval of P X from P Y and retrieval of P Y from P X .

NMI X (P X ,P Y )= MI(P X ,P Y ) H(P X ) (4.3) NMI(P X ,P Y )= MI(P X ,P Y ) p H(P X ) ⇤ H(P Y ) = NMI(P Y ,P X ) (4.4)
Entropies, MI and NMIs computed on the 3 datasets are given in table 4.2.

Mutual information based measures can give a value of similarity between two partitions. However, it is not straightforward to analyze and it does not allow to track where the (dis)similarity comes from. To allow in depth comparison, we represent pairs of partitions as bipartite networks. We present our results in the next section.

Bipartite Network of streams

To track and quantify differences between partitions X and Y ,w ecomputeabipartite network where the n i X 2 N X are the first kind of nodes. They represent the streams s

i X 2 P X (hence |N X | = |P X |). It follows that the second kind of nodes n j Y 2 N Y represent the streams s j Y 2 P Y .
A weighted directed edge is drawn between n i X and n j Y only if their corresponding streams s i GA and s j BCLA share articles. For a given pair of nodes (n i X ,n j Y )t h ew e i g h t so ft h et w oe d g e sb e t w e e nt h e m( o n ei ne a c hd i r e c t i o n ) are defined in eq.4.5. We quantify differences between streams of two partitions from this graph, quantities are given in table 4.3.

8 > > > < > > > : w n i X !n j Y = |s i X \ s j Y | |s i X | w n j Y !n i X = |s j Y \ s i X | |s j Y | (4.

Results on ENS-Lyon Dataset

From Table 4 The measures from Table 4.3 confirm the previous analysis. 1 st E(GA, REF ) shows that streams from P GA share on average 86 ± 17% of their articles with a stream from P REF and an average of 3.37 ± 1.76 streams from P GA are needed to retrieve 80% of streams from P REF .S i m i l a ro b s e r v a t i o n sc a nb em a d ef o rP BCLA . Moreover, Sum 80 (GA, BCLA) shows that it takes on average two streams from P BCLA to reach 80% of streams from P GA . This is illustrated in Figure 4. 3 These observations confirm that here streams from P REF are not mix of different streams parts from P GA (P BCLA ). But they are unions of (almost) entire streams. In this case, GA and BCLA yield almost the same partition, only different in scale.

Examples of major differences

Here, we illustrate our analysis with BN representations. We show the hierarchical subdivisions between P GA and P BCLA for the ENS Lyon dataset. In figure 4.3, we see that P GA streams (in red) can be almost entirely retrieved from the union of a few complete P BCLA streams (in blue). Sometimes P BCLA streams share articles with more than one P GA stream. However, for all P BCLA streams sharing articles with more than one P GA streams, the proportion of shared articles with the most similar article is more than five times higher on average than the other proportions of shared articles with the other P GA streams. This illustrates that P GA differs from P BCLA mostly by scale.

Results on Wavelets Dataset

Describing the history of the wavelet research field is a complicated task as it is born from the collaboration of multiple fields and sub-fields. The values from table 4.2 point that, even though partitions have closer number of streams (27 for P GA and 36 for P BCLA ) they are significant differences between our local and global method. In this case, NMI(BCLA, REF ) is significantly higher than NMI(GA, REF ) (0.82 vs. ferences (e.g. s_85, s_52).

It is also worth noting the difference between s_21 and s_53. The global method (GA) merges both into one stream g_7 (see Fig. 4.4a), However, P REF and P BCLA partitioned them separately (respectively (s_21, s_53) and (r_2 and r_24). If we look at Figure 4.2b, we see that these streams do not belong to the same time period. s_53 corresponds to one of the early works on wavelets, from 1963 to 1994. The second one, s_21 came after (1987 -2014) working on different problems.

(a) Part of the bipartite network representation of Wavelets dataset. This network shows the links between temporal communities from P GA (left in red) and P BCLA (right in blue). On each node is given the stream ID and the most frequent author name of the temporal community. Size of nodes accounts for the size of the streams, each stream contains at least 20 articles.

From these examples we saw that our BCLA method takes into account better the complexity in the dynamics than global methods which simply merged these streams into one in P GA .

Discussion

In our method, we first analyzed mutual information based measures. We saw that MI based measures are interesting to quantify how different two partitions are. But they are limited when it comes to describing these differences. For this reason it was necessary to visualize the partitions. The bipartite network representation allowed us to see how streams split between partitions. We saw with some examples that global methods could do as well as local methods to automatically generate history from datasets with a clear structure (high modularity), like in the case of ENS-Lyon data. But it reached limitations when working on datasets where streams are entangled as illustrated in Section 4.4.4. On the opposite, our BCLA could better take into account the complexity in the dynamics and led to a partition closer to the reference, manually drawn by the field expert. Now, for the last chapter of this thesis, in the fashion of a grand finale, we will combine complex networks, mobility data of customers, and supervised machine learning. More precisely, we will look at how mobility data can enable us to study the impact of new businesses on already established ones.

Introduction

Location is known to be highly influential in the success of a new business opening in a city. Where a business is positioned across the urban plane not only determines its reach by clienteles of relevant demographics, but more critically, it determines its exposure to a local ecosystem of businesses who strive to increase their own share in a local market. The types of businesses and brands that are present in an urban neighborhood in particular has been shown [Jensen, 2006] to play a vital role in determining whether a new retail facility will grow and blossom, or instead whether it will become a sterile investment and eventually close. Competition is nonetheless only one determinant in retail success. How a local business establishes a cooperative network with other places in its vicinity has been shown to also play a decisive role in its sales growth [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF]. Local businesses can complement each other by exchanging customer flows with regards to activities that succeed each other (e.g. going to a bar after dining at a restaurant), or through the formation of urban enclaves of similar local businesses that give rise to characteristic identities that then become recognisable by urban dwellers. A classic example of the latter is the presence of many Chinese restaurants in a Chinatown [Zhou, 2010].

It is therefore natural to hypothesize that the rise of a business lies on the complex interplay between cooperation and competition that manifests in a local area. Measuring these cooperative and competitive forces in a city remains, however, a major challenge. Today's cities change rapidly driven by urban migration and phenomena such as gentrification as well as large urban development projects, which can lead to shops opening and closing at increasing rates. Already in 2011, the fail rate of restaurants in certain cities, such as New York, was as high as 80% 1 with some businesses closing in only a matter of months. A similar picture has been reported recently for high street retailers in the United Kingdom with part of the crisis being also attributed to the increasing dominance of online retailers2 .

Data generated in location technology platforms by mobile users who navigate the city provides a unique opportunity to respond to the aforementioned challenges. In addition to providing quick updates, in almost real time, on the places that open (or close) in cities -thus accurately reflecting the set of local businesses in a given areathey offer a view on urban mobility flows between areas and places at fine spatial and temporal scales. The ability to describe these two dimensions of urban activity -places and mobility -paves the way for measuring the impact, either positive or negative, that retail facilities have on each another. In this chapter, we harness this opportunity, building on a longitudinal dataset by Foursquare that describes mobility interactions between places in 26 cities around the world. Our contribution are summarized in more detail in the following:

• Detecting patterns of cooperation in urban activity networks: We mo del businesses in a city as a connected network of nodes belonging to different activity types. We examine the properties of these networks spatially and temporally.

With respect to a null network model, we observe higher clustering coefficient, higher modularity and lower closeness centrality scores which are indicators of strong tendencies for local businesses to cluster and form collaborative communities that exchange customer flows. In numerical terms, the modularity of urban activity networks is ⇡ 0.6 relative to the corresponding null models with ⇡ 0.15.

• Measuring the impact of new businesses using spatio-temporal metrics: We next mo del the impact of a new business op ening in a given area.

Previous work [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF] conducted a preliminary analysis of homogeneous impact of new businesses. However, this work was limited as it did not isolate numerous contributing factors such as whether multiple new venues have opened when attributing the impact to a given business. We develop a methodology more robust to bias through the use of spatio-temporal filters. Moreover our approach generalizes to heterogeneous interactions between venue types present in an urban system by considering impact measurements between different venue categories (e.g. measuring the impact of a restaurant to a bar). Notably, we observe that the opening of a Fast Food Restaurant near other Fast Food Restaurants results in the most significant competition, with a median decline in customer flows of 21% over 6 months. We also show how this competitive ranking can be created for heterogeneous categories.

• Predicting optimal retail environment using urban dynamics and network topology measures: Lastly, we built a supervised learning model to predict the impact of multiple new venues on an existing venue. We incorporated additional network metrics into our model to consider the urban environment of a given venue and its capacity to operate cooperatively with other places in vicinity. We observe significant heterogeneity between categories where some have more predictable trends while others have greater variations. In light of this heterogeneity across venue types we tailor supervised learning models by training them in a manner that reflects the idiosyncrasies of its category. Despite the inherent difficulty of the prediction task, due to the multi-factorial nature of dynamic and complex interactions in retail ecosystems, our results suggest that incorporating complex signals in predictive machine learning frameworks can offer meaningful insight in real world application scenarios. For certain business categories, AUC scores above 0.7 are consistently attained, whereas complex network metrics consistently boost the performance of classifiers offering a clear advantage over baseline methods.

Our results are especially important in a digital age with shifting customer preferences as physical business are forced to adapt to remain competitive. Our methodology can enable a better understanding of interactions within local retail ecosystems. Modern data and methods, such as those employed in the present chapter, not only can allow for monitoring these phenomena at scale, but also offer novel opportunities for retail facility owners to assess the risk of opening a new venture through location-based analytics. Similar methods can be applied beyond the scope of the retail sector we study here, namely for urban planning and innovation e.g. by assessing the impact of opening transport hubs, leisure and social centers or health and sanitation facilities in city neighborhoods.

Related Work

Understanding retail ecosystems and determining the optimal location for a business to open have for long been questions in operations research and spatial economics [Ghosh andCraig, 1983, Eiselt andLaporte, 1989]. Compared to modern approaches, these methods were characterized by static datasets informing on population distribution across geographies, tracked through census surveys and the extraction of retail catchment areas through spatial optimization methods [Applebaum, 1966]. Gravity models on population location and mobility later became a common approach for site placement of new brands [START_REF] Gibson | Retail turnover in the east midlands: A regional application of a gravity model[END_REF].

The availability of spatio-temporally granular urban datasets and the popularization of spatial analysis methods in the past decade led to a new generation of approaches to quantify retail success in cities. In this line, network-based approaches have been proposed to understand the retail survival of local businesses through quality assessment on the interactions of urban activities locally [Jensen, 2006]. In addition to networks of places, street network analysis emerged as an alternative medium to understand customer flows in cities, with various network centrality being proposed as a proxy to understand urban economic activities [START_REF] Crucitti | Centrality measures in spatial networks of urban streets[END_REF], Porta et al., 2012].

More recently, machine learning and optimization methods have been introduced to solve location optimization problems in the urban domain, focusing not only on retail store optimization [START_REF] Karamshuk | Geo-spotting: mining online location-based services for optimal retail store placement[END_REF] but also real estate ranking [START_REF] Fu | Sparse real estate ranking with online user reviews and offline moving behaviors[END_REF] amongst other applications. Location technology platforms such as Foursquare opened the window of opportunity for customer mobility patterns to be studied at fine spatio-temporal scales [D' Silva et al., 2018b, D'Silva et al., 2018a] and moreover, semantic annotations on places presented direct knowledge on the types of urban activities that emerge geographically and led to works that allowed for the tracking and comparing of urban growth patterns at global scale [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF]. Closer to the spirit of the present chapter from a modelling perspective, the authors in [START_REF] Hidalgo | Do we need another coffee house? the amenity space and the evolution of neighborhoods[END_REF]] study co-location patterns of urban activities in Boston and subsequently recommend areas where certain types of activities may be missing.

Dataset Description

Within the last decade, Online Location-based Services have experienced a surge in popularity, attracting hundreds of millions of users worldwide. These systems have created troves of data which describe, at a fine spatio-temporal granularity, the ways in which users visit different businesses and areas of a city. We hypothesize these data can be used to build a predictive model of the impact of a new venue on the surrounding businesses. To this end, we utilize data from Foursquare, a location technology platform with a consumer application that allows users to check into different locations. As of August 2015, Foursquare had more than 50 million active users and more than 10 billion check-ins [VentureBeat, 2015].

The basis of our analysis is a longitudinal dataset from 26 cities that spans three years, from 2011 to 2013, and included over 80 million checkins. We aggregate data from the 10 most represented cities in North America3 and the 16 most represented cities in Europe4 .As u m m a r yo fo u rd a t ai sd e s c r i b e di nT a b l e5 . 1 .

For each venue, we have the following information: geographic coordinates, specific and general category, creation date, total number of check-ins, and number of unique visitors. The specific and general categories fall within Foursquare's API of hierarchical categories. A full list of the categories can be found by querying the Foursquare API [Foursquare, 2018]. The dataset also contains a list of transitions within a given city. A transition is defined as a pair of check-ins by an anonymous user to two different venues within the span of three hours. It is identified by a start time, end time, source venue, and destination venue. We consider the set of venues V in a city. A venue v 2 V is represented with a tuple < loc, date, category > where loc is the geographic coordinates of the venue, date is its creation date, and category is the specific category of the venue. The creation date, date,foragiv env en uereferstothedateitw asadded to the Foursquare platform. Prior work by [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF] showed that across all cities when examining the number of venues added per month, the last 20% of venues were new venues rather than existing venues added to the database for the first time. We apply this methodology to all cities and define new venues as those that fall within the last 20% of venues added to Foursquare for that city. [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. We see clusters of travel and transport (blue), nightlife (red), and shopping activities (green).

Urban Activity Networks

We begin by examining transitions between Foursquare venues of different category types that we refer to as urban activities. While we are considering a mix of categories users check in in the city, our focus from an analysis and modelling point of view will be focusing on urban activities corresponding to retail establishments (e.g. restaurants).

Visualizing Mobility Interactions

To visualize an urban activity network, we create a graph G i for each city i, where the set of nodes N cat is the set of business categories defined previously in Section 5.3. In this network, business categories are linked by weighted directed edges e s!d .Ad i r e c t e d link is created from the source category c s to the destination category c d if at least one transition happens during the time window we consider (e.g. weekend, weekday, or a period of hours during a day). Thus, the weight of each edge is proportional to the total number of transitions from the source category to the destination category for the particular time period of interest for each city. The weights are then normalized by the total number of check-ins that occurred at c d . Therefore, the weight can be interpreted as the percentage of customers of c d who come from c s .T o e l i m i n a t e insignificant links, we filter out edges that have less than 50 transitions total. We examine two time intervals of interest: morning AM (6am-12pm) and evening PM (6pm-12am).

In Figure 5.1 we visualize the network in the evening for two cities, London and Paris. The colors represent different communities, obtained using the Louvain community detection algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. Further, the size of nodes is proportional to their degree. This visualization, as one example, describes similarities and variations in the structure of urban activities in different cities. We observe an underlying common structure for the two cities, even though cultural distinctions can also be noted. We have observed a similar pattern across many cities. In terms of similarity in network structure, we see a shopping cluster (green) centered around Department Stores; a cluster for travel and transport (blue) centered around categories such as Train Stations and Subways; a leisure cluster (light brown) centered around Plazas and containing outdoor categories (e.g. Parks, Gardens, Soccer Stadiums). On the other hand, differences in network structure become also apparent. We note for instance how recreation activities in the evenings differs across the two cities. London has a considerably large nightlife cluster (red) centered around pubs from which a number of different nightlife categories unfold (e.g. Nightclubs, restaurants of different types, Theater). Paris is more segregated and contains two nightlife clusters: one Overall, these results suggest strong structural characteristics in urban activity networks where different categories of places form interaction patterns of cooperation, where mobile users move from one to the other. Competition on the other hand manifests in a more implicit manner in the network in two ways: first, retail facilities that are grouped in the same node (e.g. Bars) have to share customers that have been previously performing a different activity (e.g. going to a Restaurant) and second, through activities that do not share an edge in the network and as a result they do not interact with one another in terms of mobility patterns.

Network Properties

We next quantify the structure of these networks in terms of different network properties considering also different time intervals. For our two cities of comparison, we list the network metrics in Table 5.2 and enlist those next:

• the average clustering coefficient, <C> ,i st h et e n d e n c yo fc a t e g o r i e st of o r m triangles, that is to gather locally into fully connected groups. It varies between 0 and 1 with higher values implying a higher number of triangles in the network (see [Newman, 2010] for more details).

• the average closeness centrality, <C c >,i st h ea v e r a g el e n g t ho ft h es h o r t e s t path between the nodes and here accounts for the tendency of categories to be close to each in terms of shortest paths [Newman, 2010]. It varies between 0 and 1 where a higher closeness centrality score for a node suggests higher proximity to other nodes in the network. -12pm) and evening PM (6pm-12am). These metrics are compared to an Barabási-Albert model (Random).

• the modularity, Q,i saw e l le s t a b l i s h e dm e t r i ci n d i c a t i n gh o ww e l ld e fi n e dc o mmunities are within the network [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. Modularity values fall within the range [-1, 1], with greater positive values indicating greater presence of community structure.

We compare our network metrics to a random baseline which maintains the degree distribution, a Barabási-Albert network [Albert and Barabási, 2003], in Table 5.2. The comparison with the null model provides an indication of how significant empirical observations are with respect to the random case. First we note that for all three metrics the real networks are very different to the corresponding null models. In general, high clustering coefficient and modularity together with a lower closeness centrality scores point to the tendency of local businesses to form significantly tight clusters that are well isolated from one another. Furthermore, these networks properties vary for different period of the day and are subtly different from city to city. We see for instance closeness centrality being higher in the evening relative to morning hours whereas and the average clustering being lower in the evening. This means that categories are less locally connected to each other during evening hours. This could be due to the fact that users have more well planned series of movements in the morning following daily commuting routines. For instance, users are more likely to travel directly from a train station to an office in the morning on a weekday while they may instead wander from ap u bt oab a ri nt h ee v e n i n g s .

Looking closer at the network modularity scores presented in Table 5.2 we note a clear partitioning of different categories into communities with scores around 0.6 for both cities compared to much smaller values ⇡ 0.15 for the null model. Modularity values increase in the evening in both cities. This translates to a stronger community structure, suggesting customers may be less likely to experience activities in different category communities than in the morning and confirm the dichotomies from previous sections such as Coffee Shops vs. Pubs in London and Bars vs. French Restaurants in Paris). Finally, the similarity in terms of network properties values between the two cities, as well as the prominent community structure in both suggest that the hypothesis that the organization of the retail business ecosystem is similar across cities is a plausible one. This is true to a certain degree nonetheless, as variations are also noted due to apparent cultural differences.

Measuring Impact

In this section we examine the impact of new businesses on other establishments within their vicinity. Previous work [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF] has considered the homogeneous impact of a new business opening, that is the impact that venue categories have on categories of the same type (e.g. the impact of a new Coffee Shop on another Coffee Shop). In this section we generalize the impact metric to heterogeneous mixes of categories, and develop a methodology more robust to spatio-temporal bias effects.

Spatio-temporal Scope of Impact

To measure the impact of a new venue op ening in an area we need to define its geographic scope. We define the spatial neighborhood of a venue as the set of venues that are located within the radius r s .F o r m a l l y ,w ed e fi n et h es p a t i a ln e i g h b o u r h o o d of a venue v n as:

SN(v n ,r s )={v e 2 V : dist(v n ,v e ) <r s ^vn 6 = v e } (5.1)
where V is the set of venues in the city and dist(v n ,v e ) is the Euclidean distance between venue v n and v e . Further we intro duce a similar notion across the temp oral dimension. In particular, given a temporal radius r t , then two businesses opening within r t are considered to be temporal neighbors.F o r m a l l y ,w ed e fi n et h et e m p o r a ln e i g h b o r so fav e n u ev n as:

TN(v n ,r t )={v e 2 V : t_dist(v n ,v e ) <r t ^vn 6 = v e } (5.2)
where t_dist is the difference in the number of months between the creation date of v n and v e .F i n a l l y ,w ed e fi n eW T as the temporal window of observation, i.e. the total period in months over which we measure the number of check-ins at a given business.

Measuring Impact

Defining the impact formula

We base our impact metric I vn (v e ,t vn ) of a new venue v n on an existing venue v e on the metric introduced in [START_REF] Daggitt | Tracking urban activity growth globally with big location data[END_REF]. This is defined as the normalized number of transitions for an existing venue in a specific time period prior to and after a new venue opens in its spatial neighborhood. We define the number of check-ins during the posterior time interval as follows:

C post vn (v e ,t vn , ∆t)= tv n +∆t-1 X d=tv n n ve (d, d +1) (5.3)
This calculates the sum of check-ins at venue v e , n ve ,a f t e rt h eo p e n i n go fv n at t vn and over a period of ∆t = W T /2 months. We define the number of checkins during the prior time interval as follows:

C prior vn (v e ,t vn , ∆t)= tv n -∆t-1 X d=tv n n ve (d -1,d) (5.4)
Similarly, this calculates the number of check-ins over the period of ∆t months before the opening of v n . Formally, the impact metric is defined as follows:

I vn (v e ,

Impact metric interpretation

Above, we define N cat (t vn ,t vn +∆t) as the total number of check-ins to all businesses of a specific category. We define the market share of a given venue as the total number of check-ins to that venue as a percentage of N cat .U s i n gt h ei m p a c tm e t r i cd e fi n e d in Section 5.5.2 we can calculate the percentage of market share gained or lost by venue v e after the opening of venue v n .F o r e x a m p l e ,i f v n is a clothing store and v e is a sandwich shop I vn (v e ,t vn , ∆t)=1 .2 means the market share of venue v e (the sandwich shop) increased by 20% over the ∆t months following the opening of v n (the clothing store). Conversely, a number below 1 means the market share of the venue v e decreased after the opening of venue v n ,s u g g e s t i n gt h en e wv e n u ew a sac o m p e t i t o r .

For the example ab ove if I vn (v e ,t vn , ∆t)=0 .81 this would correspond to the market share of venue v e (the sandwich shop) decreasing by 19% over the ∆t months following the opening of v n (the clothing store).

Tuning Spatial and Temporal Windows

Am a j o rc h a l l e n g ei na n a l y z i n gc o r r e l a t i o ni nac o m p l e xs y s t e mi st oi m p l e m e n ta methodology which can limit the effect of potential hidden variables which may bias the observed correlation.

For our mo del, our metho dology must isolate the impact of one business in constantly changing neighborhoods. For this reason, as a first analysis, we set r t to ∆t = W T /2, that is half of the window of observation, and we only choose a pair (v n ,v e ) if the new business v n has no temporal neighbors (defined above in Equation 5.2). In other words, if we set ∆t = W T /2=3months, we only measure the impact of v n on v e if v e was open at least 3 months before v n and if no other business opened in the spatial neighborhood of v e during [t vn -∆t, t vn +∆t].W ea p p l yt h i s form of filtering to isolate the confounding effect of multiple businesses opening next to each other. This naturally introduces a trade-off with regards to the data points considered for our measurement.

The number of data points resulting from our approach depends on two parameters. The spatial radius r s and the temporal radius r t . As shown in Figure 5.2(a) where r t is fixed at 3 months, when the spatial radius is small the probability of a new business nearby opening is low. Hence the number of data points remains small as well. As the spatial radius increases so does the number of data points until a maximum is reached after which it decreases again. This likely due to the fact that after a certain distance threshold the probability of finding only one business opening within r s decreases as well. Based on these results we set parameter r s to 100 meters for our subsequent analysis. We apply the same reasoning for tuning the temporal radius r t setting r s to 100m. However, tuning r t is more challenging. Our hypothesis is that after a time period, t vn + r t , the positive (or negative) impact of a new business will become stable within the scope of a neighborhood. After this period of time, v n will be considered as part of the baseline of the neighborhood, when examining the impact of future new venues. Our hypothesis is that as r t increases, the less likely we are to be considering other new shops that are interfering with the impact we measure. Figure 5. 2(b) shows that the number of data points steadily decreases from r t =∆ t>1 month onwards. This implies that the optimal value for r t in terms of data points is smaller than The color varies according to the median impact value of the pair, dark blue corresponds to impact below 1 (representing competition), grey represents neutral median impact equal to 1, and dark red translates to high median impact (representing cooperation). Read: French Restaurants (9th row) have a median impact on Bars (2nd column) of 1.2 and less than 100 pairs were counted. one month. However, as suggested earlier increasing r t limits the risk to consider previously new venues that opened just before the time window of interest in the impact measure. For this reason we choose a value of r t longer than one month. For the analysis described below, we set r t to three months.

Measuring Impact on Retail Activity

We p erform the analysis using the aforementioned setup on the 16 most popular retail categories and aggregated data from the 26 cities listed above in Section 5.3. We aggregated data from these cities based on observed similarities in consumer trends as discussed in Section 5.4. This enabled us to build a set of 10, 238 businesses. The top 16 retail categories examined were as follows: Bakeries, Bars, Burger Joints, Clothing Stores, Cocktail Bars, Coffee Shops, Fast Food Restaurants, French Restaurants, Grocery Stores, Hotels, Italian Restaurants, Nightclubs, Pizza Places, Pubs, Sandwich Places, and Supermarkets.

Figure 5.3 shows the impact measured for each Burger Joint where a Coffee Shop opened within its spatial neighborhood. We observe a heterogeneous distribution of impact scores. However 66.1% of the 56 burger joints in this configuration were impacted negatively. The median impact is 0.85 which corresponds to a 15% decrease in demand to Burger Joint when a Coffee Shop opens within 100 meters.I n t h i s analysis, due to the skewness of the impact measures distribution, we use the median and the percentage of positively (or negatively) impacted businesses as key numbers to represent the directed impact of pairs of categories. Furthermore, we note the structure of Burger Joints in Figure 5.3. It is composed of two parts: a high impact peak followed by a linear decline. Interestingly, this structure is consistent across all pairs of categories, generalized with a peak of ⇠ 10% of high impacts shops (I>1.5), followed by a linear decline of impact (⇠ 80 -90% of shops), and succeeded with an optional ⇠ 10% discontinuously negatively impacted shops, representing competition in the area (0 <I<0.5).

In Figure 5.4 we show the matrix of median impact of our top 16 retail categories on each other. A few observations are worth noting. First, impact scores on the diagonal tend to be negative. This observation shows and quantifies the direct competitive effect of businesses belonging to the same category. Second, most impact scores are negative suggesting the general tendency for retail establishments to compete. Third, some cooperative pairs are noticeable (e.g. Hotels on Pizza Place: 70% of positive impact, median impact: 1.2; Nightclubs on French Restaurants: 67% of positive impact, median impact: 1.8). We also note that certain network links seen in Figure 5.1 between categories can be found as positive impact pairs in the matrix, such as Nightclubs and French Restaurants and Fast Food Restaurants and Bars.

Building a competitive ranking

Using the aforementioned results we list a ranking of homogeneous competition in Table 5.3. This ranking shows the top categories in terms of negative impact, when a business of the same category opens within 100 meters. The list suggests that fast food restaurants feature the strongest homogeneous negative impact (-21%), closely followed by other businesses where people may visit for food or a snack, namely Bakeries, Pizza Places, Coffee Shops, Sandwich places. Note also the high probability of negative impact for Bakeries with a 73.1% chance to be negatively impacted.

Our methodology can also be applied to heterogeneous pairs of businesses to determine which new business type would create the greatest competition or cooperation for an existing business. Using Coffee Shops as an example, we saw in Table 5.3 that a new Coffee Shop creates a median impact of I =0 .84.W es i m i l a r l ys e ei nF i g u r e 5.4 a competitive effect from new Burger Joints, which result in a median impact of I =0 .85.Ac o m p e t i t i v er a n k i n go ft h i st y p ec a nb ee s t a b l i s h e df o ra l lc a t e g o r i e st o better understand trends in the impact of new businesses.

To our knowledge the methodology described above is novel, and despite the limitations that we discuss in more detail in Section 6, it allows for the principled quantification of the impact that new businesses have in the retail ecosystem they operate. We exploit this formulation in the context of a prediction task in Section 5.6 where impact scores are modeled as target labels and the goal becomes to predict the impact of new businesses opening on their local environment. From an economic perspective these results highlight the most competitive types of business categories that operate in cities and moreover the highlight cases of categories where cooperation in terms of customer flows is more likely to emerge.

Takeaways

The methodology we have developed in Section 5.5.2 can enable one to quantify competitive and cooperative behaviors between pairs of categories. Further, it highlights general trends, such as competition between food-related categories and cooperation between certain clusters of categories. However, reducing the complexity has two limitations. It limits the number of data as it filters out neighborhoods with more than one business opening within W T .I t a l s o o v e r -s i m p l i fi e s t h e p r o b l e m .O f t e n ,f o r a given pair of categories, there is heterogeneity in the impact measure for those two categories (e.g. there is a range in the impact of a new Coffee Shop on a Bakery). This suggests there are complex interactions between a new venue and its environment and there may be additional factors to consider. In the following sections, we study the impact of combinations of multiple new businesses coupled with the network topology of their environment. This methodology leads to insights which can help determine the optimal location for a new venue.

In Section 5.6, we implicitly considered a more complex interaction setup by taking into account the combinations of multiple new businesses, modeled as features, and coupled those with network topological characteristics of the local environment. This methodology led to insights which can help determine the optimal location for a new venue of a particular category.

Predicting New Business Impact

In Section 5.5, we explored the impact of the opening of a single business on its neighborhood. Next, we investigate in the form of a prediction task the cumulative impact of multiple shops opening within the same spatial and temporal neighborhoods, as defined in the previous section. We model the impact of new venues as a binary classification task where the impact on the existing venue is the dependent variable and the features described below in Section 5.6.2 are independent variables. We further represent a positive impact label as 1 and a negative impact label with a 0. Considering a supervised learning methodogy, our goal then becomes to learn an association of the input feature vector x with ab i n a r yl a b e ly. We experiment with a number of supervised learning algorithms described in the following paragraphs. All network features were min-max normalised. We split our dataset into training and test sets with the training set consisting of 80% of the data and the test set consisting of the remaining 20%. We perform 5-fold cross-validation to pick the best performing model and report the subsequent accuracy of prediction. Finally, we also sub-sample our dataset performing our predictions on ab a l a n c e dd a t a s e to fpo s i t i v ea n dn e g a t i v ec l a s s e s .

Extracting features

Business features

When a new venue v n opens at time t vn within a given spatial neighborhood SN(v n ,r s ) we count all other businesses which opened within the temporal neighborhood TN(v n ,r t ) of v n and in the same spatial neighborhood SN(v n ,r s ).F o re a c he x i s t i n gv e n u ev e , the counts of each category of venue within its spatial and temporal neighborhood is encoded as a feature. We refer to these features as Business features.

Network features

As described above, we utilize network topology measures at the venue neighborhood level considering each venue v e 2 SN(v n ,r s ) where each venue is a node in the network. Edges in the network represent the number of transitions from the source venue to the destination venue. These features are described as follows. The in-degree of a venue v e is the number of edges coming from the other venues to v e . The out-degree of a venue v e is the number of edges coming from v e to the other venues. The degree of v e is the total number of edges between v e and the other venues. The closeness centrality of a venue v e is the average of its shortest paths to all the other venues of the network. The diversity of a venue v e is defined by the Shannon equitability index from information theory which calculates the variety of the neighbors of venue v e [Sheldon, 1969]. These features give a representation of how well a given venue is connected to the rest of the city network and also describe the distribution of its customers.

Evaluation

In this section, we report our findings on the predictive ability of the features as well as the supervised learning models we employ in the prediction task. We compare the predictions against different baselines:

• Network connectivity features, as described in section 5.6.2.

• Business features, as described in section 5.6.2.

We first discuss how our combined mo del outp erforms b oth baselines, then show the predictive capabilities of different categories, and lastly discuss the value of network metrics in our prediction task.

Model Selection: We explored a number of different models, including Logistic Regression, Gradient Boosting, Support Vector Machines, Random Forests, and Neural Networks. As described above, we train our models to predict the impact of new businesses on a given type of retail category. When aggregating our data across all categories and working to predict the impact of a new venue on any type of existing venue category, this resulted in models with low predictive power. As discussed previously in Section 5.5, this suggests there is significant heterogeneity of behavior across different category types and therefore a training strategy tailored for each category would be more effective. To take this into account, we segregated our data by category and built a separate model for each type of category. We individually modelled the ten retail categories with the largest total number of data points. These categories were as follows: Bars, Hotels, Coffee Shops, Italian Restaurants, French Restaurants, Bakeries, Clothing Stores, Pizza Places, Nightclubs, and Grocery Stores. To compare our supervised learning models, we calculated the average AUC scores across all ten categories using our different feature baselines.

Our combined models, using both business and network features, had a resulting AUC of 0.611 for Logistic Regression, 0.687 for Gradient Boosting, 0.631 for Support Vector Machines, 0.640 for Random Forest, and 0.667 for Neural Networks. These results suggest that venue-specific metrics can support the prediction of the impact of a new venue. Across all categories, we saw that Gradient Boosting was the most robust model for our task with the highest average AUC across all ten categories. As such, we use Gradient Boosting to further analyze our models below.

Variations across Categories We next examine the predictability of different category types. Table 5.4 shows the predictability of six of the ten categories trained using a Gradient Boosting model. The AUCs of the remaining categories are as follows: Clothing Stores (AUC: 0.664, train/test size: 1362/152), Pizza Places (AUC: ). We see a range in the predictability of different venue types: Bakeries have the highest AUC of 0.861 and Bars have the lowest AUC of 0.627. This suggests that certain activities adapt to a more heterogeneous set of environment, making them more challenging to predict. These more challenging categories tend to be those that are ubiquitous and general, such as Bars and Coffee Shops.

The Value of Network Metrics: To understand the influence of different feature classes on our results, we run our Gradient Boosting model on each class separately and in combination. We report our observations in Figure 5.5 and note that for Bakeries the category features alone reach AUC of ⇡ 0.77, the network features alone reach AUC of ⇡ 0.60 and combined model leads to a higher overall AUC of ⇡ 0.85. These results, which were consistent across all retail categories, suggest using network features in lieu of venue features alone supports our prediction task. We see that the two feature classes together have the best prediction results, suggesting that the impact of new venues is driven by a number of forces, including the network connectivity, which modulate the nature of their interactions within their neighborhood.

Discussion And Future Work

Our methodology highlights the power of complex networks measures in building machine learning prediction models. This is especially valuable for systems in which interactions between agents must be taken into account. We began in Section 5.4 of this chapter by detecting patterns of cooperation in urban networks and quantifying similarities and differences in network structure across cities. Next, in Section 5.5 we measured the impact of new businesses isolating cases in which exactly one new venue opened within a given region. Using urban network topology measures and our business impact metrics, we developed a machine learning model to predict the optimal location for a new business in Section 5.6. The novelty of our approach in methodological terms stems from the use of complex networks measures, combined with machine learning methods to tackle modern societal challenges. These results can support policy makers, business owners, and urban planners as they have the potential to pave the way for the development of sophisticated models describing urban neighborhoods and help determine the optimal conditions for establishing a new venue.

One of the limitations of the work presented here is that we only examine the impact of retail venues. However, this analysis can be more broadly applied to venues of other categories as well. The present study sets the frame for further general studies. As one example of future work, one could examine the impact of new bus stops or transport hubs on those venues within their proximity. Additionally, in this chapter we conduct a preliminary examination of the variations in network trends across cities worldwide. Future work could expand up on this to explore the duality b etween general network trends and cultural consumer idiosyncrasies across cities. Our analysis could also be further expanded by considering temporal network analysis, examining the variations in features across different time intervals of interest.

Conclusion

The explosion of connected devices all around the world has been changing the economical landscape by revolutionizing the way people interact, consume and move. These actions leave traces, footprints are left by some users for most of their actions and social dynamics emerge.

These traces are an opportunity to better understand collective behaviors. Nowadays, the plurality of data available is such that it requires adapting and combining a plurality of existing methods in order to enlarge the global vision one has on a given system. This thesis has been the opportunity for me to investigate some of the hottest topics in data analysis. From network science to machine learning, I have explored different ways to model and analyze data.

We illustrated the complexity of dynamics which can emerge from simple statistical models of society, even when models follow simplistic rules. We showed that simple models can be helpful to analyze social phenomena while keeping in mind that they do not allow for drawing any rigorous conclusion about the real world.

I, then, continued my exploration of complex systems modeling working on real world data -bike sharing system users data. We worked on describing temporal dynamics of long-term bike sharing system customers. We were the first to conduct such kind of analysis on individual dynamics. We highlighted a low seasonal effect in bike usage and two main trajectories of users: the majority of users (⇠ 60%) leaves the system after at most one year; and the minority (⇠ 40%)r e m a i n si nt h e system for several years (average ⇠ 3 years). We described the usage profile and sociodemographic profile of these two classes of users. Then, we used unsupervised learning (K-means algorithm) to generate segments of customers and we compared results to as t a t i cb a s e l i n ef r o m[ V o g e le ta l . ,2 0 1 4 ] .

Moving forward in the analysis of temporal data and collective dynamics, we explored tools to describe and visualize differences between temporal partitions. We used them to illustrate essential differences between global methods and local methods of temporal complex networks clustering.

Finally, using mobility data from Foursquare, we worked on describing business cooperation and competition in urban networks. This project enabled us to work on metrics to measure the impact of new businesses on their neighborhood and build supervised machine learning models aiming at predicting optimal location for new businesses. Further, we could illustrate the power of complex networks measures in building machine learning models.

In a context of smart cities emergence, where technology is used with the goal to make transportation and urban planning more efficient, the topics of research presented in this thesis are of particular interest. They aim at a better understanding of customer usages and mobility at different layers of a city (public transportation, people's customer profiles, etc). Such research can benefit policy makers, business owners, and urban planners as understanding customers segments and trends can help design more adapted systems.

The work presented in this thesis can be expanded in many regards. In particular on the dynamics of retail businesses, we have conducted preliminary work on business trajectories and the evolution of impact over months. It shows there exists some significant trends depending on business categories. Taking into account more temporality in the design of impact metrics and machine learning features (through temporal networks metrics, opening hours of businesses, etc) together with exploring the variations in cooperation networks across cities worldwide (i.e. impact of cultural trends vs. general consumer trends) could help refine our understanding of retail environments. These are research projects of interest and I hope to continue contributing to them in the future.

A

Résumé long

Au cours des deux dernières décennies les objets connectés ont révolutionné la traçabilité des phénomènes sociaux. Les trajectoires sociales laissent aujourd'hui des traces numériques, qui peuvent être analysées pour obtenir une compréhension plus profonde des comportements collectifs. L'essor de grands réseaux sociaux (comme Facebook, Twitter et plus généralement les réseaux de communication mobile) et d'infrastructures connectées (comme les réseaux de transports publiques et les plate-formes en ligne géolocalisées) ont permis la constitution de grands jeux de données temporelles. Ces nouveaux jeux de données nous donnent l'occasion de développer de nouvelles méthodes pour analyser les dynamiques temporelles de et dans ces systèmes.

De nos jours, la pluralité des données nécessite d'adapter et combiner une pluralité de méthodes déjà existantes pour élargir la vision globale que l'on a de ces systèmes complexes. Le but de cette thèse est d'explorer les dynamiques des systèmes sociaux au moyen de trois groupes d'outils : les réseaux complexes, la physique statistique et l'apprentissage automatique. Cette thèse commence par donner quelques définitions générales et un contexte historique des méthodes mentionnées ci-dessus.

Après quoi, nous montrons la dynamique complexe d'un modèle de Schelling suite àl'introductiond'unequantitéinfinitésimaledenouveauxagents,ditsaltruistes. Nous trouvons que cette quatité infinitésimale induit un effect catalytique sur l'utilité globale du système. Ces altruistes permettent au système d'échapper à l'état sous-optimal normalement atteint lorsqu'il est seulement constitué d'agents égoïstes. À partir de cet exemple, nous concluons le chapitre en discutant des limites des modèles statistiques de société.

Le troisième chapitre montre la valeur ajoutée de l'utilisation de jeux de données temporelles. Nous étudions l'évolution du comportement des utilisateurs d'un réseau de vélos en libre-service. Ces réseaux se sont développés rapidement à l'échelle mondiale et peu de données temporelles individuelles sont disponibles. Ce chapitre donne une première description détaillée de l'évolution temporelle de 120827 utilisateurs annuels répartis sur 5 ans. Nous montrons que l'apparente stabilité générale du système est constituée d'une distribution hétérogène de trajectoires individuelles. Les utilisateurs suivent principalement deux trajectoires : environ 50 à 55% quittent le système après au plus un an. Ces utilisateurs ont une activité médiane basse (env. 40 trajets) ; les autres 45% correspondent aux utilisateurs plus actifs (activité médiane de 91 trajets catégories de commerces. Notre approche souligne la puissance de l'utilisation de mesures de topologies de réseaux complexes dans le développement de modèle prédictifs d'apprentissage automatique. Cette méthodologie et resultats pourraient assister les autorités urbaines et les propriétaires de commerces dans le développement de modèles pour décrire et prédire des changement dans l'environnement urbain.

B

Dynamics of Scientific Research Communities

We investigated four temp oral community detection metho ds, two global and two lo cal methods. However, as measures from GA and GPA are very close and measures from BMLA and BCLA are also very close, we only presented the GA and BCLA methods in the core of this thesis (see Chapter 4). The two other methods (GPA and BMLA) and their measures are described below.

B.1 Global Projected Algorithm (GPA)

Here, we want to include some dynamics into our global algorithm. So, as for our global method, we first run the Louvain algorithm on the total BC network. It results a set of GA-streams. Then, we define successive BC networks by taking into account articles sharing at least two references with articles within their own publication period. We, now, have a subset of the total BC network (BC network articles minus the articles not sharing two references within their own period). This subset is on average 7.8% smaller than the total BC network. For each time period, we define local communities by grouping together the publications that are in the same GA-streams. We now have a set of lo cal pro jected communities in each p erio d. Finally, we compute historical streams by applying our matching algorithm to the projected communities. This approach allows the emergence of dynamical events.

B.2 Best-Modularity Local Algorithm (BMLA)

The BMLA is an incrementation of the work from [START_REF] Morini | Revealing evolutions in dynamical networks[END_REF]. On each time period, we run N independent runs (we used N =1 0 0 )o ft h eL o u v a i na l g o r i t h m . Because of the noise inherent to the Louvain algorithm, these partitions may be a bit different, while having close values of modularity. BMLA historical streams are defined by applying the matching algorithm to the partitions with the best modularity in each time period.

  a m i c so fS c i e n t i fi cR e s e a r c hC o m m u n i t i e s 8 B.1 Global Projected Algorithm (GPA) . . . . . . . . . . . . . . . . . . . . B.2 Best-Modularity Local Algorithm (BMLA) . . . . . . . . . . . . . . . . B.3 Comparing All Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . List of Figures 1.1 Moreno's network of runaways . . . . . . . . . . . . . . . . . . . . . . . 2.1 Agent utility function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Evolution of the average utility . . . . . . . . . . . . . . . . . . . . . . 2.3 Evolution of the city . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Effective utility function of altruistic agents . . . . . . . . . . . . . . . 3.1 Progressive renewal of users over the years . . . . . . . . . . . . . . . . 3.2 Percentages of users leaving the system at the end of each adapted years 3.3 Probability to stay in the system at the end of an adapted year . . . . 3.4 Density distribution of percentage of change in the number of trips per year from one year to another . . . . . . . . . . . . . . . . . . . . . . . 3.5 Visualization of the users-year on the two main axis given by principal component analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 AIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Boxplots of the behavioral patterns at different time scales of the 9 classes 3.8 Transfer matrices from year n (lines) to year n+1 (columns) . . . . . . 3.9 Number of active weeks per year for each class of regular users . . . . . 3.10 Length of use per adapted year for each class of regular users . . . . . . 4.1 Historical streams computed from the ENS Lyon natural sciences publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Historical streams computed from the wavelets field of research publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Bipartite network representation of ENS Lyon dataset between P GA and P BCLA .................................... 4.4 Bipartite network representation of Wavelets dataset . . . . . . . . . . 5.1 Network visualization of categories during the evening in Paris and London 5.2 Tuning the spatial and temporal parameters of our model . . . . . . . . 5.3 Plot of the impact measure of Coffee Shops on Burger Joints . . . . . . 5.4 Matrix of median impact of categories on each other . . . . . . . . . . . viii LIST OF FIGURES ix 5.5 ROC Curves of Bakeries for the performance of each class of features and for the combined model. . . . . . . . . . . . . . . . . . . . . . . . . 69 List of Tables 3.1 Number of trips per active user. . . . . . . . . . . . . . . . . . . . . . . 3.2 Description of long-term users characteristics . . . . . . . . . . . . . . . 3.3 Description of user classes found by the k-means for the 21 features . . 4.1 Statistics on datasets investigated . . . . . . . . . . . . . . . . . . . . . 4.2 Entropies and Mutual Information measures . . . . . . . . . . . . . . . 4.3 Bipartite graph measures . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Foursquare dataset description for 10 North American cities and 16 European cities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Network metrics for London and Paris for the morning and the evening 5.3 Ranking of the categories which have the strongest homogeneous negative impact. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 AUC Scores for a subset of categories using a Gradient Boosting model. B.1 Entropies and Mutual Information measures for all algorithms . . . . . B.2 Bipartite graph measures for all algorithms . . . . . . . . . . . . . . . . x

Figure 2 . 1 -

 21 Figure 2.1 -Agent utility function: u(⇢)=2 ⇢ for ⇢  0.5 and u(⇢)=2 ( 1-⇢) for ⇢>0.5.

Figure 2 . 2 -

 22 Figure 2.2 -Evolution of the average utility as a function of (a) the altruists' fraction p (note the log scale on the x-axis) and (b) the rescaled fraction p ⇤ =2 pQ⇢ 0 .W e take H =2 0 0and vary Q as shown. The fluctuations for low p ⇤ values (before the transition) arise from metastable states in the pure egoist regime.

Figure 2 . 3 -

 23 Figure 2.3 -Evolution of the city for p =0 .03,Q =3 6and H =2 2 5 .P a n e l s ( ah) show the occupation of the different neighborhoods at different times. Egoists are represented in red, altruists in yellow, empty sites in black. (a) initial; (b) first steps; (c) usual segregation; (d-e): first invasion and altruist escape from the block surrounded in blue; (f-g): final invasion of the block surrounded in blue; (h): stationary state. In panel (i), each continuous line represents the evolution of the density of a single neighborhood. Vertical dashed lines show the times corresponding to panels (a-h).

Figure 2 . 4 -

 24 Figure 2.4 -Effective utility function of altruistic agents.

Figure 3 . 1 -

 31 Figure 3.1 -Progressive renewal of users over the years.For each year, the box height represents the total number of users and the colors the year users have entered the system. For example, in 2015, 34.4% of users are new to the system, while 18% started in 2011.

Figure 3 . 3 -

 33 Figure 3.3 -Probability to stay in the system at the end of an adapted year (P s )a s af u n c t i o no ft h ea v e r a g en u m b e ro ft r i p sd u r i n gt h a ty e a r . W h e na c t i v i t yr e a c h e s 110-120 trips per year, users are more likely to stay (P s ≥ 0.5). Each point represents an average of P s over 2500 person-years.

Figure 3 . 4 -

 34 Figure 3.4 -Density distribution of percentage of change in the number of trips per year from one year to another. Percentages are computed for each user that remained active for at least 3 years.

Figure 3 .

 3 Figure 3.6 -AIC

Figure 3 .

 3 Figure 3.7 -Boxplots of the behavioral patterns at different time scales of the 9 classes. (a) number of uses per year (right) and per active week (left), for each class. A week is considered 'active' for a user whenever he/she takes a bicycle at least once. (b) normalized number of uses for each day of the week and for each class. Week days range from one to five in decreasing order of activity for each user. Saturday and Sunday are computed separately as users' activity is different on week-ends. (c) normalized number of uses for each month of the year and for each class.

Figure 3

 3 Figure 3.8 -Transfer matrices from year n (lines) to year n+1 (columns). (a) Absolute number of users. Reading: (first line, first table): 217 users that belonged to the regular-5 class in their first year became regular-4 users in their second year; 330 remained regular-5 and 349 were no longer active; (second line, third table): 411 users that belonged to the regular-4 class in their third year remained regular-4 users in their fourth year; 59 became regular-5 and 305 left the system. (b) Percentage of users. Reading : (first line, first table) : 19.9% users that belonged to the regular-5 class in their first year became regular-4 users in their second year; 30.2% remained regular-5 and 31.9% were no longer active; (second line, third table): 34.3% users that belonged to the regular-4 class in their third year remained regular-4 users in their fourth year; 4.9% became regular-5 and 25.5% left the system.

Figure 3 .

 3 Figure 3.9 -Number of active weeks per year for each class of regular users. An active week is defined as a week where at least a trip took place.

Figure 3 .

 3 Figure 3.10 -Length of use per adapted year for each class of regular users. The length of use is the time difference between the first active week and the last active week of the adapted year.

Figure 4 .

 4 Figure 4.3 shows a part of the bipartite network between P GA (left) and P BCLA (right) on the ENS Lyon publications dataset. The part of the network is centered on nine streams from P GA equivalent to 17 streams from P BCLA .

Figure 4 . 3 -

 43 Figure 4.3 -Part of the bipartite network representation of ENS Lyon dataset. This network shows the links between temporal communities from P GA (left in red) and P BCLA (right in blue). On each node is given the stream ID and the most frequent author name of the temporal community. Size of nodes accounts for the size of the streams, each stream contains at least 20 articles.

  (b) Part of the bipartite network representation of Wavelets dataset. This network shows the links between temporal communities from P BCLA (left in blue) and P REF (right in green). On each node is given the stream ID and the most frequent author name of the temporal community. Size of nodes accounts for the size of the streams, each stream contains at least 20 articles.

Figure 4 . 4 -

 44 Figure 4.4 -Part of the bipartite network representation of Wavelets dataset.

Figure 5 . 1 -

 51 Figure 5.1 -Network visualization of categories during the evening in Paris (a) and London (b). Different colors represent different Louvain communities[START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. We see clusters of travel and transport (blue), nightlife (red), and shopping activities (green).

  (a) Effect of the size of the spatial radius on the number of data points when r t is set to 3 months. An optimal value of r s is drawn for 100 m.(b) Effect of the size of the temporal radius on the number of data points when r s is set to 100m. The number of data points continues to decrease for r t > 1 months.

Figure 5 . 2 -

 52 Figure 5.2 -Tuning the spatial and temporal parameters of our model.

Figure 5 . 4 -

 54 Figure5.4 -Matrix of median impact of categories on each other. The size of the circles represent the number of pairs of businesses which were used (e.g. Coffee Shops -Coffee Shops is 200). The color varies according to the median impact value of the pair, dark blue corresponds to impact below 1 (representing competition), grey represents neutral median impact equal to 1, and dark red translates to high median impact (representing cooperation). Read: French Restaurants (9th row) have a median impact on Bars (2nd column) of 1.2 and less than 100 pairs were counted.

Figure 5

 5 Figure 5.5 -ROC Curves of Bakeries for the performance of each class of features and for the combined model.

Table 3 .

 3

	Year	2011	2012	2013	2014	2015
	Active Users	50,393	55,896	61,806	70,068	76,511
	Trips 4,702,498 5,138,971 5,576,973 6,625,090 7,044,707
	Trips p er user	93.3	91.9	90.2	94.5	92.0
	Median trips per user	45	46	45	49	46
	Standard Deviation	125.6	122.8	120.7	123.8	123.8

1 -Numb er of trips p er active user.

Table 3 .

 3 2 -Description of long-term users characteristics They are older (median age 35, against 24, p-value < 2.2 ⇤ 10 -16 ), more likely men (men proportion 62.9% against 49.9%, p-value < 2.2 ⇤ 10 -16

	Ages	N % men % long-term users % men in long-term users
	13-22 11,231	54.8	25.2	60.5
	23-32 18,081	54.5	31.6	59.3
	33-42 9,572	62.6	49.8	65.7
	43-52 6,413	57.6	57.3	58.8
	53-62 3,774	55.9	59.6	57.0
	63-72 1,194	65.1	64.7	67.4

Table 3 .

 3 3 -Description of user classes found by the k-means for the 21 features.

	Class # person-year freq 1 st -year freq #trips/year
	'one-off' users	12164 5.8	5.2	3.0
	Week-end cyclist	24313 11.6	11.8	17
	Part-time	7639 3.6	4.3	80
	Regular0	56849 27.1	27.1	25
	Regular1	51446 24.5	24.9	83
	Regular2	29225 13.9	14.2	175
	Regular3	17183 8.2	8.0	295
	Regular4	8444 4.0	3.6	454
	Regular5	2361 1.1	0.9	695

Table 4 . 2

 42

	5)

-|P X | is the number of streams in partition X. H(P X ) is the entropy of partition X. MI(P X ,P Y ) is the mutual information between the partitions X and Y . NMI X is the mutual information MI normalized by H(P X ). NMI(P X ,P Y ) is the symmetrical normalized mutual information (normalized by p H(X) ⇤ H(Y )).

  .2, the first thing to notice on this dataset is the very different number of streams of each partition. Our global method GA has 57 streams whereas our local method BCLA contains 97 streams. The reference partition contains 17 streams, which are the 17 laboratories of the ENS-lyon in natural sciences. The high values of NMI REF (GA, REF ) (0.82) and NMI REF (BCLA, REF ) (0.81) suggests that the extra streams in both P GA and P BCLA are mostly hierarchical subdivisions of the laboratory streams from P REF .Ap a r t i t i o nb e i n gas u b d i v i s i o no fa n o t h e rd o e sn o t result in a decrease of MI between them. The MI decreases only if communities of a partition need to be mixed to become communities of another. These results argue that P GA and P BCLA are both the same description as P REF at different scales. Similarly, the high value of NMI(GA, BCLA) (0.81) suggests that P BCLA and P GA share mostly the same information.

  Table5.1 -Foursquare dataset description for 10 North American cities and 16 European cities.cluster around French Restaurants (red) linked to Coffee Shops, Theaters, Nightclubs; and another cluster (gray) centered around Bars which contains Food Trucks, Fast Food Restaurants, and Music Venues. This dichotomy translates to the presence of two classes of customers each of which adheres to different types of activity sequences during nighttime. Another observation is regarding variations in network structure over time: the Coffee Shop category in London is separated from the nightlife cluster, which may indicate different kind of customer behaviors between daytime and evening. Interestingly, we also see associations emerging between types of businesses. Taking Paris as an example, French Restaurants interact a lot with Coffee Shops and Nightclubs and so do Bars with Food Trucks. In both cities, Coffee Shops are drawing crowds from Subways, Toy Stores with Electronics Stores and Sport Stores.

	Region	# venues # new venues # transitions
	North America	94,094	29,552	43,200,432
	Europe	101,101	40,275	44,600,446
	Total	195,195	69,827	87,800,878

Table 5 .

 5 2 -Network metrics for London and Paris for during the morning AM (6am

				London				Paris
		AM Random AM PM Random PM AM Random AM PM Random PM
	#o fn od e s 204	204	208	208	180	180	149	149
	#o fe d g e s 2271	2271	3055	3055	2160	2160	2184	2184
	<C>	0.657	0.304	0.645	0.301	0.744	0.134	0.645	0.173
	<C c >	0.313	0.552	0.402	0.541	0.352	0.513	0.434	0.551
	Q	0.583	0.150	0.608	0.131	0.588	0.148	0.641	0.161

Table 5 .

 5 t vn , ∆t)= C post vn (v e ,t vn , ∆t)/N cat (t vn ,t vn +∆t) C prior vn (v e ,t vn , ∆t)/N cat (t vn ,t vn -∆t) (5.5) N cat (t vn ,t vn +∆t) (and respectively N cat (t vn ,t vn -∆t))i st h et o t a ln u m b e ro fc h e c kins to all businesses of v e 's category during the period [t vn ,t vn +∆ t] (respectively [t vn ,t vn -∆t]). This normalizing factor takes into account both the background trend of the category and the potential season effect which can occur in the market. This factor is calculated at a per city level. 3 -Ranking of the categories which have the strongest homogeneous negative impact.

	Category	Median Impact % Businesses I<0 #B u s i n e s s e s
	Fast Fo o d Restaurants	0.79	67.9	28
	Bakeries	0.81	73.1	26
	Pizza Places	0.81	69.3	39
	Coffee Shops	0.84	66.4	202
	Sandwich Places	0.84	62.0	63

  To illustrate our metho dology, let us consider the example of French Restaurants. To understand the impact of new venues on French Restaurants in Europe and North America, we consider all new venues that opened within the spatial radius r s of a French restaurant within a given period r t .W e t h e n e x a m i n e h o w t h e d e m a n d o f that given French restaurant changed after the opening of the new venues. We aim to predict whether the opening of those new venues will have a positive or negative impact on the French restaurant given network features about the venue, and a count of the types of venues that opened within r t .W ec o n s i d e rt h i sp r e d i c t i o nt a s kf o ra l l retail categories aiming to understand how each category is impacted by new venues opening nearby.

	Category	Coffee Shops	Bars	Italian Restaurants	Hotels	French Restaurants Bakeries
	Train/test size	1956/218	2275/253	1629/181	2129/237	1631/1 81	1526/170
	AUC (Business Features Baseline)	0.611	0.603	0.618	0.621	0.701	0.771
	AUC (Network Features Baseline)	0.549	0.551	0.564	0.557	0.591	0.584
	AUC (All Features)	0.627	0.642	0.658	0.702	0.742	0.861
	Table 5.4 -AUC Scores for a subset of categories using a Gradient Bo osting mo del.
	5.6.1 Prediction Task

Table B .

 B 1 -Similarly to Table4.2, |P X | is the number of streams in partition X. H(P X ) is the entropy of partition X. MI(P X ,P Y ) is the mutual information between the partitions X and Y . NMI X is the mutual information MI normalized by H(P X ). NMI(P X ,P Y ) is the symmetrical normalized mutual information (normalized by p H(X) ⇤ H(Y )).

	Measures ENS-Lyon Wavelets
	|P GA | |P GP A | |P BCLA | |P BMLA | |P REF | H(P GA )	57 54 97 103 17 3.63	27 30 36 40 36 2.87
	H(P GP A )	3.63	2.94
	H(P BCLA )	4.05	3.04
	H(P BMLA )	4.04	3.17
	H(P REF )	2.37	3.18
	MI(GA, REF )	1.93	2.03
	MI(GP A, REF )	1.94	2.09
	MI(BCLA, REF )	1.93	2.49
	MI(BM LA, REF )	1.94	2.47
	MI(GA, BCLA)	3.10	1.90
	NMI GA (GA, REF )	0.53	0.73
	NMI REF (GA, REF )	0.82	0.64
	NMI(GA, REF )	0.66	0.68
	NMI GP A (GP A, REF )	0.54	0.74
	NMI REF (GP A, REF )	0.82	0.66
	NMI(GP A, REF )	0.67	0.70
	NMI BCLA (BCLA, REF )	0.48	0.84
	NMI REF (BCLA, REF )	0.81	0.80
	NMI(BCLA, REF )	0.63	0.82
	NMI BMLA (BM LA, REF )	0.48	0.78
	NMI REF (BM LA, REF )	0.82	0.80
	NMI(BM LA, REF )	0.63	0.79
	NMI GA (GA, BCLA)	0.86	0.67
	NMI BCLA (GA, BCLA)	0.77	0.62
	NMI(GA, BCLA)	0.81	0.64

http://apps.isiknowledge.com/

http://www.sebastian-grauwin.com/bibliomaps/

(a) Historical streams computed from the ENS Lyon natural sciences publications. Streams were determined using the global algorithm (GA).

(a) Historical streams computed from the wavelets field of research publications. Streams determined using the global algorithm (GA).

(b) Historical streams computed from the wavelets field of research publications. Streams were computed using our local method (BCLA).

https://www.businessinsider.com/new-york-restaurants-fail-rate-2011-8

https://www.theguardian.com/cities/ng-interactive/2019/jan/30/high-street-crisis-town-centreslose-8-of-shops-in-five-years

North American cities are: Austin, Boston, Dallas, San Francisco, New York City, Houston, Las Vegas, Los Angeles, Toronto, Washington.

European cities are: Amsterdam, Antwerpen,Barcelona, Berlin, Brussels, Budapest, Copenhagen, Gent, Helsinki, Kiev, Madrid, Milano, Paris, Prague, Riga, London

Acknowledgements

Measures ENS-Lyon Wavelets

1 st E(GA, REF ) 0.86 ± 0.17 0.75 ± 0.20 0.49 ± 0.20 0.81 ± 0.17 with n X ± its standard deviation. For instance, for the ENS-Lyon, this means that streams of P GA share on average 86% of their articles with their most similar stream in P REF , whereas streams from P REF only share on average 49% of their articles with their most similar stream in P GA . Sum 80 (X, Y ) is the average number of streams from P Y it takes to retrieve 80% of the streams' articles from P X .F o re x a m p l ei nt h ec a s e of the Wavelet Dataset, on average 1.88 ± 0.96 streams from P BCLA are needed to retrieve 80% of a stream from P GA . 0.68). Moreover NMI(GA, BCLA) is rather low (0.64) which suggests that differences here are not only due to the difference of scales. We visualize some of these differences in the section 4.4.4. From Table 4.3 we see that most similar streams b etween P GA and P REF share 75% ± 20% of articles on average, whereas it is 87% ± 17% of articles shared between P BCLA and P REF .

Examples of major differences

We now show some major differences between P GA and P BCLA for the wavelets dataset. From Figure 4.4a, we can see two kind of differences between partitions: scale differences (e.g. g_9 with s_42 and s_9) like in the ENS Lyon case; and differences where P GA streams are mixed to retrieve P BCLA streams, such as the group of streams around g_5 and g_31. Interestingly, g_7 cumulates scale and mixing differences.

If we now look at the BN representation of the same P BCLA streams with corresponding P REF streams (Figure 4.4b), we see that our P BCLA description is closer to the description in P REF . There are more 'stream-to-stream' equivalences, represented by the double arrow on each side of the edge linking streams. Note that, though P BCLA is closer to P REF , there are still scale differences (e.g. s_21, s_111) and mixing dif-Figure 5.3 -Plot of the impact measure of Coffee Shops on Burger Joints. Each column is a Burger Joint for which only a Coffee Shop opened in its neighborhood during a period ∆t =3months. We see that 37/56 joints are over I =1,t h a ti s6 6 %o fB u r g e r Joints have been impacted negatively by the opening of a Coffee Shop.

BMLA Algorithm

Compute the Bibliographic Coupling Graph ; Split the dataset into temporal windows ∆t ; for each temporal window do run N =100Louvain algorithm on the instant network; select the instant partition with the highest modularity Q; end Match the most similar communities between successive temporal windows ; Link the paired communities along time; This algorithm returns temporal streams which we call BMLA-streams. These streams maximize the modularity at each time t without considering the global modularity of the whole system. shares with n Y ± its standard deviation. The second row is the average proportion of articles n Y shares with n X ± its standard deviation. For instance, for the ENS-Lyon, this means that streams of P GA share on average 86% of their articles with their most similar stream in P REF , whereas streams from P REF only share on average 49% of their articles with their most similar stream in P GA . Sum 80 (X, Y ) is the average number of streams from P Y it takes to retrieve 80% of the streams' articles from P X .F o re x a m p l e in the case of the Wavelet Dataset, on average 1.88 ± 0.96 streams from P BCLA are needed to retrieve 80% of a stream from P GA .

B.3 Comparing All Algorithms