Maxime, Mélanie, Cyril, Botch, Cauchy David

Mael, Crevette, Elsa Mariette Simon

Doat, Pinoges, Elsa Doralice

Marine, Yoann Paul

Aurélie Pauline Laureen

Bébou, MP, Leïla, Nina&Maé, Mouss Anna Simon

Baptiste, Gemma Sarah V Robin

Rémy

Vadim Pietro Hannah

Giacomo Andres

Sebin, Thibault, Thibaud, Martin, Julie, Bassel, Umar, Denis, Liudmila, Ujjwal, Diego Tianyi Baptiste

Keywords: Partitionning algorithm, scale-free network, network reduction

Je tiens à remercier sincèrement celles et ceux qui directement ou indirectement ont permis la réalisation de ce travail. Une thèse c'est une douce tempête que l'on traverse et qu'il est difficile de décrire sans l'avoir vécu. Aujourd'hui, au crépuscule de cette épreuve, nombreux sont ceux que je veux citer ici, pour leur accompagnement, leur amitié, leur soutien durant cette thèse d'une part, mais également au long du chemin qui m'a mené jusqu'ici.

Et puisqu'ils sont à l'origine de tout, tout d'abord merci Papa et Maman pour votre amour inconditionnel. Je comprends mieux aujourd'hui les sacrifices que vous avez fait pour nous donner à Manon et moi toutes les chances dans la vie. Chaque page de cette thèse vous est due puisque je n'aurais rien fait sans vous. Manon, chère soeur, ma thèse t'intrigue autant qu'elle te parait douteuse, je te remercie aussi de me l'avoir fait remarquer. Tu as raison, c'est probablement pas normal de rester 3 ans devant un ordinateur à chercher d'obscures algorithmes. Tu te pares de toutes les couleurs du monde, laisse aux autres le choix de trouver celle qui leur plaît. Merci au reste de ma famille, oncles et tantes, cousines et cousins, grand-parents, los de qui cau. Si ma thèse m'a confié aux Alpes bienveillantes, mon coeur est toujours dans les Pyrénées.

Puisqu'ils sont ma seconde famille, ou ma famille de second degré, merci aux Chevaliers. Vous seuls comprenez qu'une vanne peut durer trois ans. Nos retrouvailles, à califourchon sur le grand sud ou en amazone dans les Balkans, à aiguiser nos vannes, à griffer la route et à assécher nos écuelles sont toujours un grand ressourcement, à défaut d'être d'un quelconque repos. Après tant de temps en exil, ma lame reviendra très vite s'aligner aux vôtres.

Résumé

L'analyse, l'estimation et le contrôle de systèmes dynamiques évoluant sur des réseaux se confronte à des problèmes de complexité lorsque le système considéré devient trop grand. Pour faire face à ces problèmes d'échelles des méthodes de réduction de modèle sont utilisées. Cette thèse s'intéresse particulièrement à une méthode de réduction de réseaux en particulier : le partitionnement. Cette méthode consiste à trouver une partition des noeuds du réseaux induisant un réseau de dimension réduite ayant certaines caractéristiques. Afin d'utiliser le réseau réduit comme modèle du système initial, toute méthode de réduction vise à préserver certaines propriétés du réseaux initial. La particularité de notre travail est d'imposer en plus au réseau réduit certaines propriétés de notre choix. Cette approche permet de bénéficier des propriétés du réseau réduit pour l'application qui en sera faite par la suite en particulier l' observation, l'estimation ou le contrôle du système. En particulier une propriété d'intérêt est appelée scale-free 1 . Un réseau est dit scale-free si il possède quelques noeuds, appelés hub, avec un très grand nombre de connexions mais que la plupart de ces noeuds ont très peu de connexions. Précisément un réseau est dit scale-free si sa distribution de degrés suit une loi de puissance. Cette thèse s'articule autour de cette problématique et est composée de six parties principales détaillés ci-dessous: Tout d'abord une introduction permet de définir un cadre formel à ce travail, de le recontextualiser et d'apporter certains préliminaires sur les propriétés du réseaux que l'on veut préserver ou imposer et notamment la propriété scale-free. Dans le premier chapitre nous étudions l'impact d'une contrainte de connexité dans un problème de partitionnement. Le deuxième chapitre explore le problème de partitionnement assurant que le réseau réduit soit scale-free. Dans le troisième chapitre nous proposons d'imposer au réseau réduit une certaine propriété assurant que l'évolution du système peut être reconstruite dans une certaine mesure. Enfin les quatrième et cinquième chapitres sont des applications des résultats précédents respectivement au réseau de trafic et au réseau d'épidémie. La thèse se termine sur une conclusion revenant sur les principales contributions et offre quelques perspectives.

Le premier chapitre concerne un problème que nous avons dénommé le prix de la connexité. Lorsqu'on considère un problème de partitionnement de réseau où la meilleur partition doit être trouvée afin d'optimiser un certain objectif il est possible d'y ajouter une contrainte de connexité. Dans ce cas, les noeuds au sein d'une même partie de la partition doivent être connectée entre eux. Cette contrainte est pertinente par exemple lorsqu'on considère un réseau de trafic (ou n'importe quel réseau avec une géographie sous-jacente) et que l'on souhaite que chaque partie de la partition corresponde à une zone géographique. Ajouter cette contrainte va nécessairement diminuer la qualité de la réduction au regard de l'objectif fixé. La dégradation de la solution est ce que l'on appelle le prix de la connexité. Nous proposons ensuite d'estimer sa valeur pour un réseau donné et pour n'importe quel problème de partitionnement. Pour ce faire, on compare la taille des ensembles de recherche du problème et du problème contraint qui sont respectivement l'ensemble des partitions du réseau et l'ensemble des partitions connexes du réseaux. Le rapport entre la cardinal de ces deux ensembles est appelé rapport de connexité. La suite du chapitre vise à estimer cette valeur et en particulier nous obtenons une borne supérieure dans le cas de réseau Erdős-Rényi. Finalement, nous montrons expérimentalement que cette borne est très proche de la vraie valeur du rapport de connexité calculée expérimentalement.

Le second chapitre pose le problème de partitionnement de réseau induisant une structure scale-free. Comme dit précédemment, il est nécessaire de préserver également des caractéristiques du réseau initiale. Étant donné un réseau initial, nous proposons donc un méta-problème consistant à trouver la meilleure partition en terme de scale-free sous les contraintes de préservations de propriété. Nous proposons ensuite un méta-algorithme donnant le squelette d'une méthode pour obtenir une solution suboptimal à ce type de problème. Nous résolvons ensuite un premier cas simple de ce type de problème pour des raisons essentiellement didactiques. Puis nous nous intéressons un problème plus complexe préservant certaines propriétés dynamiques du réseau initial à savoir: la conservation de masse, la centralité de vecteur propre et la masse totale du système. Des résultats mathématiques sont établis permettant d'établir un algorithme sub-optimal pour ce problème. Le troisième chapitre s'intéresse à la possibilité de reconstruire l'évolution d'un état agrégé d'un réseau. En considérant un système linéaire invariant dans le temps, on défini la notion de détectabilité moyenne comme la possibilité de pouvoir reconstruire la valeur moyenne de certaines zones du réseau à partir de quelques mesures. Le problème qui nous intéresse est donc de trouver une partition du réseau entre une partie observée et d'autres parties non-observées assurant la détectabilité moyenne. Un premier résultat montre que pour un type de système particulier une condition suffisante à la détectabilité est la régularité des parties non-observées ce qui signifie qu'au sein de chacune de ces parties les noeuds doivent tous avoir le même degrés sortant. Un algorithme est ensuite proposé pour trouver une telle partition. Cependant ce problème de détection de sous-graphes réguliers est fondamentalement complexe entre autre parce que c'est un problème NP, que les meilleurs solutions sont souvent des réseaux trop petits et que les hypothèses sur le système de départ sont très contraignante. Ceci étant dit, nous proposons ensuite une version relaxée du problème où l'on ne cherche plus la régularité exacte du sous-graphe mais une certaine forme de quasi-régularité. En effet, nous montrons que l'erreur de reconstruction de la moyenne de chaque sous-graphe peut être borné par une fonction de l'erreur de la régularité. A partir de ce résultat nous proposons un algorithme fournissant une partition en sous-graphe quasi-régulier.

Les deux derniers chapitres sont des applications des résultats théoriques présentés dans les trois premiers chapitres. Le quatrième chapitre s'intéresse au trafic routier de l'agglomération grenobloise. Nous montrons qu'à partir du grand réseau initial (environ 19000 noeuds), les résultats du chapitre deux permettent d'obtenir un réseau réduit avec une structure scale-free.

Des simulations montrent ensuite qu'il est possible d'utiliser ce réseau réduit pour reconstituer efficacement la dynamique du système initial. Le cinquième chapitre propose deux applications en lien avec l'épidémiologie, la science qui étudie la propagation de maladie dans une population et que nous présentons dans une première partie du chapitre. La première application s'intéresse à la question de stratégie de vaccination. Étant donnés un réseau représentant une population et un nombre limité de vaccin, on cherche les individus les plus intéressant à vacciner (et donc retirer du réseau) afin d'enrayer la propagation de la maladie. Des résultats bien connus pour les réseau scale-free propose de vacciner les hubs c'est à dire les individus fortement connectés. Pour les raisons plus homogènes, nous proposons d'utiliser l'algorithme du deuxième chapitre pour obtenir un réseau réduit scale-free et ainsi identifié certaines zone ayant un rôle de hub au sein du réseau initiale. Cette stratégie est comparé à d'autres stratégies et nous montrons qu'elle est jusqu'à deux fois plus efficace pour une large plage de paramètre du modèle. Enfin la dernière application considère la propagation d'une maladie au sein d'un large réseau d'individu recouvrant le territoire français. En utilisant les résultats du troisième chapitre, on montre qu'il est possible de diviser la population en plusieurs zones dont l'évolution moyenne peut être estimée efficacement à partir de l'observation d'une petite partie des individus.

Contents

The world as a network

A network is a system composed of elements interacting together. This definition is not precise as the terms system, elements and interacting are in a certain way blurry. However, it seems to be a good definition and if the terms are not clear it is because networks include a very vast range of systems. Networks are everywhere. This statement is so used in literature that it has almost lost its sense, but, literally, networks are everywhere: Humans are connected within societies forming networks where the links may be friendships, family ties or work relationships. The brains of these humans are composed of billions of connected neurons, and each of these neurons are composed by molecules interacting together via chemical reactions. Besides the brain, the human body contains several other networks such as circulatory, nervous and lymphatic systems. Thanks to their brains, humans build road networks, electrical networks and telecommunication networks. In addition to humanity, animal interactions and physical phenomenon can also be interpreted as networks. Networks are everywhere, inside and around us.

While it includes a large variety of different systems, networks can be modeled and studied (a) The brain network is composed of billions of interconnected neurons (b) The cosmic web describes the distribution of matter in the universe Figure 1: From the hidden recesses of our brain to the structure of the space, a large variety of systems can be viewed as networks.

within a same mathematical formalism. The parenthood of this formalism is often attributed to the Swiss mathematician Leonard Euler and its problem of the seven bridges of Königsberg in 1736. This problem asks us to find a route in the city of Königsberg which crosses once and only each of the seven bridges. While at first view the problem seems far from the network theory, Euler used mathematics to bring a solution leading to the foundation of the graph theory 3 . However, this primary work remained isolated and confined to recreational mathematics. In 1878, this formalism found an application in chemistry when the English mathematician J.J. Sylvester introduced the chemicograph. But it is especially during the twentieth century that network found an application in sociology, with the introduction of sociogram. In the second part of the twentieth century several models aimed to explain the recurrent structure found in networks. In particular, Paul Erdős and Alfred Rényi introduced in 1958 a model bearing their name. This model will be detailed further as it is still commonly used in network theory. In 1998, Duncan Watts and Steven Strogatz proposed their smallworld model explaining the result of the experiment proposed by the psychologist Stanley Milgram in 1960 4 . Finally, in 1999 Albert-Lazlo Barabási and Réka Albert introduced the scale-free model which explains the structure of a large variety of networks. This last model will be widely used throughout the thesis and extensively presented in Section 0.3. Today, network theory is ubiquitous in many different areas of research. We give hereafter some examples of works using this formalism:

Biology and medicine Biology is probably one of the fields which has benefited the most from the network theory. We can cite for example the protein/protein interaction networks which help to empower our knowledge about the biochemical events between proteins within a cell; the metabolic networks describes more generally all the physical interactions in a biological system (from a cell to an organism); in a macroscopic point of view food webs are also represented as networks and help to better understand ecological interconnections; finally networks are widely used to model the propagation of a disease within a population. Throughout this thesis, we will precisely present applications in this last field.

Linguistic and art Semantic networks represent the semantic relations between different words in a language. They help to better understand the structure of a language, to implement high-level interfaces on computers or to design efficient translation engines. Narrative networks link together different concepts of a story which can be fictions, historic events, or even personal stories. In the same idea, there are networks linking the characters of fictional universes such as the Marvel Cinematic Universe 5 , Game of Thrones 6 or the Shakespeare's tragedies 7 .

Computer and information science Obviously networks are ubiquitous in computer sci- 3 We will say a word further on the difference between graphs and networks 4 In this experiment Stanley Milgram aimed to show that any individual is connected to any other through few intermediates. This groundbreaking work emphasized that the human society is a small-world and is commonly associated with the idea of the six-degrees of separation. 5 See https://studentwork.prattsi.org/infovis/projects/marvel-universe-visualization/ 6 See https://networkofthrones.wordpress.com/ 7 See http://www.martingrandjean.ch/network-visualization-shakespeare/ ence at different levels. From the physical layer with the design of computer networks to the application layer with the structure of the internet in which websites are connected via hyperlinks. From the algorithmic point of view, the functioning of a web engine is also based on network theory. For example, Google uses, among other tools, the PageRank metric to find the most relevant website within the network. From a more theoretical point of view, bayesian networks are used in information theory to understand the relations between different pieces of information.

Sociology As said, sociology is the application which partly encouraged the development of network theory. Today, the research in this area studies social networks online (Facebook, Twitter,...) and offline (work, school, friendship), to understand, for example, how an information spreads in a population or how communities emerge. In criminalitics (also named forensic science), network theory is also used to gather information and detect fraud.

This list is far from exhaustive and aims only to give an overview on the wide range of applications of network theory. One could have also evoked power distribution networks, neural networks, applications in climatology, in risk-assessment, in economics and in traffic modelisation. This last application will be considered and discussed in the thesis. [START_REF] Da | Analyzing and modeling real-world phenomena with complex networks: a survey of applications[END_REF] draws up a vast review of the applications and research areas concerned by network theory. Figure 2 illustrates this variety of utilization.

In particular, a network may be used to represent the evolution of a dynamical system. In this case a state is associated to any element of the network and equation governs the evolution of the state of each element in function of the state of its neighborhood. Along this thesis, we will consider such evolution occurring on networks. We will present further the details of the dynamical equations in which we are interested. While the study of networks is abundant, in some instances the size of the network makes it more challenging to analyze. From this issue flows the question of the reduction of networks which is the guideline of this work.

Reduction of complexity

Large networks (with thousands of nodes) are common in several fields like transportation, power grid or biology among others. The Stanford Large Network Dataset [START_REF] Leskovec | SNAP Datasets: Stanford Large Network Dataset Collection[END_REF] lists such large systems and can give an order of magnitude: Internet peer-to-peer networks have around 10 4 nodes, traffic networks have around 10 6 nodes and social networks have between 10 4 and 10 7 nodes. At these scales, the analysis of these large networks becomes very costly or even impossible. This complexity motivates network reduction methods also known as coarsegraining or summarization methods. Works on the network reduction are profuse (see [START_REF] Liu | Graph Summarization Methods and Applications: A Survey[END_REF] for an extensive survey) and the ERC-granted project Scale-Freeback8 , in which this thesis takes place, aims precisely, among other things, to reduce the complexity of large-scale networks. The objectives of the network reduction are different depending on the application. However, the different purposes of network reduction methods have the following form: cutting the complexity (e.g. volume of data, redundancy, visualization) of a network while preserving some properties (e.g. topological, dynamical, patterns). The techniques used differ but essentially there are four categories: partitioning (merging nodes in super-node and/or edges in superedges), compression (exploiting redundancy in the patterns of the network) and simplification (removing unimportant nodes and/or edges). In this thesis, we consider only partitioning approaches as it is the most common and the most rich method. This terminology, as well as the approaches, may differ according to the fields of study. This thesis falls in the scope of a dynamical system vision which aims to reduce networks by preserving a consistency, in particular, in the dynamical behavior. Precisely, besides the preservation of dynamical characteristics, our work proposes to endow the reduced network with a particular shape known as scale-free. The two following sections aims to introduce a variety of network-related notions, among them the scale-free property, allowing to introduce more formally the objectives of the thesis.

Introduction to network theory

This section provides a partial introduction to the network theory and to the notions used along the thesis and necessary for the formulation of the objective of our work.

Generalities on networks and network partitioning

We introduce formally in this section some generalities and notations related to network and network partitioning. A network G is a pair (V, E), where V is a set of nodes 9 and E is a set of edges verifying E ⊂ V × V. The graph is said undirected if for all edges (v, w) in E, the edge (w, v) is also in E, which means that the edges has no direction. In the other case, the graph is said directed and the direction of the edges matters. In this thesis, we consider directed 10 networks G, represented by the triple (A, V, E) where A ∈ R |V|×|V| is the adjacency matrix, whose non-zeros values indicate the edges: A i,j = 0 implies (i, j) ∈ E. In particular if the non-zero values of A are different, the graph is said weighted. In this case, A i,j = w = 0 indicated that a weight w is assigned to the edge (i, j). We may denote G = ( • , V, E) if only the structure of G (and not the weights) is relevant. A visual representation is associated to any network. In such representation, dots represent the nodes of the network and links between the dots represent the edges. In the case of a directed network, an arrow is added to the link to represent the direction of the edge and in the case of a weighted network the weight of each edges may be displayed. We present now some definitions related to networks. Definition 0.1 (Degree) In general, the degree of a node is the number of connections the node has. When considering directed network we distinguish indegree and outdegree:

• The indegree of a node v, denoted deg in (v), is the number of nodes preceding v (these nodes are called the predecessors of v) which is:

deg in (v) = |{w ∈ V, (w, v) ∈ E}| (1)
where | • | gives the cardinality of a set. The set of predecessors is denoted N in :

N in (v) = {w ∈ V, (w, v) ∈ E} (2)
• The outdegree of a node v, denoted deg out (v), is the number of nodes following v (these nodes are called the successors of v) which is:

deg in (v) = |{w ∈ V, (v, w) ∈ E}| (3)
The set of successors is denoted N out :

N out (v) = {w ∈ V, (v, w) ∈ E} (4)
In the following, when there is no need to precise if we consider indegree or outdegree, we will use the general term degree.

Definition 0.2 (Degree distribution)

The degree distribution of a network G, denoted by Π G , is a vector giving the distribution of the degree over the whole network which is:

Π G,k = |{v ∈ V, deg(v) = k}|

Definition 0.3 (Network partition)

A partition S = {S 1 , S 2 , ..., S n } of a network is a partition of the set of vertices V which is:

i S i = V (5) ∀ i, j ∈ [1, n] i = j =⇒ S i ∩ S j = ∅ (6)
Each element S i is named a part11 of the partition S. Let us remark that this definition does not imply that the nodes inside a part have to be somehow connected. From a partition of a network, we obtain a new network defined hereafter. has degree 1, one node (v 4 ) has degree 2 and one node (v 1 ) has degree 3.

v 1 v 2 v 3 v 4 v 5 (a)
Definition 0.4 (Network coming out of a partition) Let G 0 = ( • , V 0 , E 0 ) be a network, let S be a partition of this network. We denote

G 1 = ( • , V 1 , E 1 ) the network coming out the partition S of G 0 . Which is: V 1 = {1, . . . , |S|} (i, j) ∈ E 1 ⇔ (S i × S j ) E 0 = ∅ (7)
If G 1 is a network obtained from a partition of G 0 we denote G 0 G 1 or G 0 S G 1 to emphasize the partition. Let us remark that since this relation only determines the structure of the reduced network and not its weights, there is an infinite number of weighted networks coming out of the partition S of G 0 . Finally, we also define a particular type of partition that we will need throughout our development: the merging12 . Definition 0.5 (Merging) A merging is a partition in which only two nodes are merged. Let {1, ..., n} be the set of vertices, the merging of the vertices v and w is denoted by S v,w and:

S v,w ={{1}, {2}, . . . , {v -1}, {v + 1}, . . . . . . , {w -1}, {w + 1}, . . . {n}, {v, w}}

Network properties

This section aims to define a list of network properties that will be used throughout the thesis. These properties are roughly divided into three parts to help readability. This section is not expected to be thoroughly examined at the first read but to be used as a glossary to which the reader can refer all along the thesis. A particularly interesting property for us is the scale-freeness and Section 0.3 is fully dedicated to present it.

Remark 0.1 (Terminology). The terms used in this thesis are not always uniquely employed in the literature, and due to the wide range of areas concerned by the network theory it is common that several terms coexist for a same concept. We will try to give these different terms and indicate the one we will use. First of all, we say a word on the difference between graph and network : basically, these terms correspond to the same object but with a different connotation following the authors. Intuitively, graph refers to the mathematical object while network refers to the physical object. Said otherwise, a network is a graph endowed with a physical model. It is in this sense that the graph theory and network theory are often divided. For the sake of simplicity, in this thesis we do not make a real difference between these two terms, and we use mainly the term network to remain consistent. However in some cases, the term graph may be chosen if it appeared more natural and it should not preoccupy the reader. In the same way, the couples of terms node/vertex and edge/arc coexist in the literature and we will mainly use here node and edge.

Structural properties

In this part, we define notion regarding only the structure and the weights of the network without considering any dynamics. We first define connectedness, also known as connectivity.

To introduce properly the different notions of connectedness we first introduce the notions of walk and path.

Definition 0.6 (Walk and path) A walk is a sequence of edges of the form

(v i 0 , v i 1 ), (v i 1 , v i 2 ), (v i 2 , v i 3 ), . . . (v i m-1 , v im ).
A path is a walk in which all nodes are distinct. An undirected walk is a sequence of couples of the form

(v i 0 , v i 1 ), (v i 1 , v i 2 ), . . . (v i m-1 , v im ) verifying (v i k , v i k+1 ) ∈ E or (v i k+1 , v i k ) ∈ E.
An undirected path is an undirected walk in which all nodes are distinct.

Definition 0.7 (Strongly connected network) A network is said to be strongly connected if it exists a path from any node to any other node.

Definition 0.8 (Weakly connected network) A network is said to be weakly connected if it exists a an undirected path from any node to any other node.

Roughly, a directed network is strongly connected if any node can be connected to any other node following the edges and it is weakly connected if the network forms an unique island. If the network is not weakly connected then it is disconnected. Figure 5 illustrates the three different cases: strongly connected, weakly connected and disconnected.

We now define the characteristics lengths of a network. In general two metrics are referred as the characteristics lengths: the diameter and the radius. Both aims to measure how much the nodes are close together. To define these two concepts, we first define eccentricity. Definition 0.9 (Eccentricity) In a network, the eccentricity of a node v, denoted v , is the greatest distance between v and any other node:

v = max w∈V δ(v, w) (8)
where δ(v, w) is the length of the shortest path between v and w.

Definition 0.10 (Radius)

The radius r is the minimal eccentricity:

r = min v∈V v v 1 v 2 v 3 v 4 v 5
(a) Strongly connected network: it is possible to go from any node to any other node following the edges

v 1 v 2 v 3 v 4 v 5
(b) Weakly connected network: it is not possible to go from node v 3 to any other node, the network is not strongly connected. However, the network forms an unique island.

v 1 v 2 v 3 v 4 v 5
(c) Disconnected network: node v 5 is not linked to the rest of the network. The diameter is then the longest distance between any two nodes of the graph. The radius is somehow the distance between the most central node and the node, which is the furthest from it. Note that if the graph is not strongly connected the diameter is infinite and if it is disconnected the radius and all the eccentricities are also infinite. Table 1 presents the eccentricities, radius and diameter for the three networks in fig. 5.

The clustering coefficient measures how

c v = |{i, j ∈ N out (v), (i, j) ∈ E}| n out (n out -1) (11)
where

n out = |N out (v)|
The local clustering coefficient measures the tendency of the successors of a node to be connected together.

Definition 0.13 (Cluster coefficient)

The clustering coefficient of a network, denoted C is the average value of the local clustering coefficients:

C = 1 |V| v∈V c v (12)
By considering only few parts of the network we can extract a new network. This refers to the notion of subgraph defined hereafter.

Definition 0.14 (Subgraph) Given G 0 = ( • , V 0 , E 0 ), a subgraph G 1 = ( • , V 1 , E 1 ) of G 0 is a graph verifying V 1 ⊂ V 0 ( 13
)
E 1 ⊂ E 0 (14)
Therefore, a subgraph G 1 of a given graph G 0 is obtained by considering only a part of the nodes and edges of G 0 . An induced subgraph is a specific case of subgraph:

Definition 0.15 (Induced subgraph) Given G 0 = ( • , V 0 , E 0 )
, the subgraph induced by the subset I ⊂ V 0 , denoted G I , is the graph consisting of the nodes in I and all the edges between nodes of I. Therefore, we have G I = ( • , I, E I ) with:

E I = (I × I) ∩ E 0 (15)
Figure 6 illustrates the difference between the two notions.

Definition 0.16 (Regular network)

A network is said regular if all its nodes have the same degree:

∃ d ∈ N, ∀ v ∈ V, deg(v) = d (16)
d is called the degree of regularity.

When the degree of regularity is equal to 0 the network is said empty (or null) and when its equal to n -1, where n is the number of nodes, the network is said complete. Figure 7 illustrates this. Definition 0.17 (Mass conservation) A weighted network is said to have the mass conservation property if, for each node, the sum of the weights coming in equals the sum of the weights coming out:

∀ i ∈ [1, ..., |V|], |V| j=1 A i,j = |V| j=1 A j,i (17)
v 1 v 2 v 3 v 4 v 5 (a) Initial graph G 0 v 1 v 2 v 3 v 4
(b) Subgraph of G 0 : the nodes {1, 2, 3, 4} and some edges between them are considered

v 1 v 2 v 3 v 4 (c) The induced subgraph G {1,2,3,4} :
the nodes {1, 2, 3, 4} and all edges between them are considered Figure 6: Subgraph and induced subgraph

v 1 v 2 v 3 v 4 v 5
(a) An empty network is regular with a degree of regularity equal to 0.

v 1 v 2 v 3 v 4 v 5
(b) Regular network both for indegree and outdegree with a degree of regularity equal to 2

v 1 v 2 v 3 v 4 v 5
(c) Network regular for outdegree (degree of regularity equal to 1) and not regular for indegree The term flow network is also used for networks having this property. In this thesis, for such a network we will say that it is mass conserving, it has the mass conservation property or it is a flow network. Figure 8 illustrates this property.

Definition 0.18 (Total mass)

The total mass of a weighted network, denoted M , is the sum of all the weights in the network:

M = |V| i=1 |V| j=1 A i,j (18)
In fig. 8 the total mass is 16.

Dynamical properties of networks : a control systems perspective

This second part presents more specifically notions related to the dynamical evolution of a network. Through the thesis, we will use linear equations governing the evolution of networks defined hereafter 13 . For that we associate to the network G = (A, V, E) a state vector x ∈ R |V | assigning a value to each node of the network. The equation governing its evolution is:

ẋ(t) = Ax(t) + Bu(t) ẏ(t) = Cx(t) ( 19
)
where A is the weighted adjacency of the network G, u(t) ∈ R p is a control (or input) vector, B ∈ R |V|×p is the input matrix pointing the nodes to control, y(t) ∈ R m is the output vector and C ∈ R m×|V| is the output matrix. If, all along this thesis, we consider dynamical system evolving network, the notions defined below remain true for any system with or without an underlying network structure. Notions related to controllability and observability will be evoked throughout the thesis. Basically, they refer, respectively, to the possibility to steer the state of the network towards a desired state and the possibility to determine the state of the network through only few measurements. We define properly these properties hereafter. The bulk of this section is inspired from the book Linear Systems Theory of João Hespanha [START_REF] Hespanha | Linear systems theory[END_REF] to which the reader is invited to refer for further information on the subject.

System [START_REF] Anna | Scale-free networks are rare[END_REF] drives the state x(0) = x 0 at time t 0 to the state x(T ) = X 1 at time T given by:

x 1 = e AT x 0 + T 0 e A(T -τ ) Bu(τ )dτ (20)
The notion of controllability refers to the possibility to transfer the state between two states. The following definition allows to express the range of accessible state.

Definition 0.19 (Controllable subspace)

The controllable subspace C of the system (19) consists of all states x 0 for which, for all T > 0, there exists an input u : [0, T ] -→ R p that drives the state from x 0 at time 0 to the origin at time T , which is:

C = x 0 ∈ R |V| , ∀ T > 0, ∃ u, e AT x 0 + T 0 e A(T -τ ) Bu(τ )dτ = 0 (21)
The matrix C of [START_REF] Anna | Scale-free networks are rare[END_REF] play no role in this definition. Therefore one talk about the controllable subspace of the pair (A, B) and thus, when considering the underlying network, one may talk about the controllable subspace associated to a weighted network and a set of controlled node.

Definition 0.20 (Controllable system) The system [START_REF] Anna | Scale-free networks are rare[END_REF]

is controllable if C = R |V| ,
which is if any state can be driven to the origin.

Note that targeting the origin is not a special case: if we can go from any state in finite time to the origin, then we can go from that state to any other state in finite time as well. To any control input u : [0, T ] -→ R p we associate the following measure of the energy:

T 0 u(τ ) 2 2 dτ (22)
The controllability Gramian is a matrix associated to control and used, among other things, to measure how much energy is needed to control a given system.

Definition 0.21 (Controllability Gramian)

The controllability Gramian14 of system [START_REF] Anna | Scale-free networks are rare[END_REF] is defined by:

W C = +∞ 0 e Aτ BB e A (τ ) dτ (23)
Observability is a notion dual to controlability. It refers to the possibility to determine x(0) from the future inputs and outputs u(t) and y(t) for t ≤ 0. When considering system [START_REF] Anna | Scale-free networks are rare[END_REF], the evolution of the output is described by:

y(t) = Ce At x 0 + t 0 Ce A(t-τ ) Bu(τ )dτ ∀ t ≤ 0 (24)
To study the system's observability, we need to determine under which condition we can solve

Ce At x 0 = y(t) - t 0 Ce A(t-τ ) Bu(τ )dτ ∀ t ≤ 0 (25)
for the unknown x 0 ∈ R |V| . This lead to the following definition:

Definition 0.22 (Unobservable subspace)
The unobservable subspace UO consists of all states x 0 ∈ R |V| for which

Ce At x 0 = 0∀t > 0 (26)
This leads to the the following definition Definition 0.23 (Observable system)

The system [START_REF] Anna | Scale-free networks are rare[END_REF] is observable if the unobservable subspace is reduced to the zero vector which is UO = 0. This implies that the initial state x 0 can be uniquely determined.

The matrix B of [START_REF] Anna | Scale-free networks are rare[END_REF] play no role in this definition. Therefore one talk about the observability of the pair (A, C).

A weaker notion than the observability is the detectability and will be considered in the thesis. Basically, a system is said detectable if the components of unobservable subspace are all asymptotically stable and therefore it is possible to determine asymptotically the state of the system. To define it properly we introduce first the following decomposition. Theorem 0.1 (Observable decomposition -Theorem 16.2 in [START_REF] Hespanha | Linear systems theory[END_REF]) For every system [START_REF] Anna | Scale-free networks are rare[END_REF], there is a similarity transformation that takes the system to the form

       ẋo ẋu = A o 0 A 21 A u x o x u + B o B u u y = [C o 0] x o x u (27)
for which:

• The pair (A o , C o ) is observable
• The unobservable subspace of (0.24) is given by

ŪO = Im 0 I n×n ( 28
)
where Im is the image of a vector and n is the dimension of the unobservable subspace of the original system.

Based on this decomposition, the detectability is defined as follows:

Definition 0.24 (Detectable system)

The system [START_REF] Anna | Scale-free networks are rare[END_REF] is detectable if its decomposition verifies n = n (the system is observable) or if A u is a stability matrix These notions of control theory will be used along the thesis both in the development of our work and in the motivation for our interest in scale-free networks presented in the following section.

Scale-free networks

We pay particular attention to a special type of networks: scale-free networks. These mathematical objects have been extensively studied at the beginning of this century and have aroused a lot of interest. In one hand because it appeared that a lot of systems are well captured by the definition of scale-free networks, and in the other hand because these networks exhibit properties and behavior differing from other networks and potentially beneficial for some applications. In this section we propose a presentation of scale-free networks from different point of view: first we give a mathematical definition, then a historical approach and finally a non-exhaustive list of properties and applications.

Definition

While it exists a wide range of networks, it is possibly to classify them according to different criteria. In particular, a property of interest is the degree distribution of the network. The degree distribution says a lot about the structure of the network and it is often used to classify networks. Based on this distribution, it is interesting to distinguish two different structures: the first one is when the degree distribution is homogeneous: all nodes have a degree close to the average degree. This type of degree distribution is obtained, for example, with random Erdős-Rényi networks [START_REF] Erdős | On the evolution of random graphs[END_REF]. The second noteworthy structure is the heavy-tailed distribution: in this case few nodes have a very large degree while most of the nodes have a small degree. In the case where the distribution is a power-law we refer to it as a scale-free network. Figure 9 gives a representation of this two types of network and their respective degree distributions. Definition 0.25 (Scale-free network) Let G be a network and Π G its degree distribution. G is said to be scale-free if it exists α > 0 such that: The international air transportation network has a scale-free structure. The smallworld property (see Section 0.3.3) of the scale-free networks ensures that it is possible to travel the world relatively quickly. This image comes from [START_REF] Grandjean | Connected World: Untangling the Air Traffic Network[END_REF].

∀ k ∈ N, Π G (k) ∝ k -α (29)
α is called the scale-free coefficient of G.

In practice G is called scale-free if its degree distribution is relatively close to a power law.

For a directed network, the definition is the same but it is necessary to precise if we consider indegree, outdegree, or both. In the latter case, one may have two different scale-free coefficients, α in and α out . Figure 10 shows a famous example of scale-free network: the international air transportation network. Indeed some airports are huge platforms and are highly connected while there is a majority of national or local airport with few connections.

Historic of scale-free networks

The studies of these networks started with Derek Price in 1965 [START_REF] De | Statistical studies of networks of scientific papers[END_REF] when he looked at the network of citation between scientific papers. Since the most a paper is cited the most he tends to be cited again, he discovered that there are few papers with a very large degree. In [START_REF] De | Statistical studies of networks of scientific papers[END_REF], Derek Price exhibited the heavy-tailed degree distribution of the citation networks and proposed a model capturing its properties. This was the first-time that a scale-free network is noticed, but the name was not coined yet. Beyond this network, it is common, in a lot of different contexts, that the most connected item attracts more connections. This mechanism has been discovered in different fields and at different time, hence it is known by different names: preferential attachment in network theory, Yule effect in evolution, cumulative advantage or again Matthew effect in sociology. This is almost always this mechanism which leads to real-world scale-free networks. As an example, the World Wide Web network, constituted of the webpages connected via hyperlink, is subject to preferential attachment. Indeed, when a new web-page is created, it will probably propose links towards some websites which are already highly-connected. In 1999, it is precisely by studying the topology of the World Wild Web that Albert-László Barabási and its collaborators rediscovered scale-free networks forgotten since Derek Price [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. In their work, they proposed a model of scale-free network, the Barabási-Albert model, based on the preferential attachment mechanism. This model is explained hereafter. Since their rediscovery it has been shown that scale-freeness is ubiquitous in a wide range of fields such as biological networks [START_REF] Jeong | The large-scale organization of metabolic networks[END_REF], social networks [START_REF] Liljeros | The web of human sexual contacts[END_REF] and internet network [START_REF] Yook | Modeling the Internet's large-scale topology[END_REF] among others. Above the highlighting of the scalefree nature of a variety networks, a lot of works has been done to study the properties of scale-free networks. We will detail further some of these properties.

The Barabási-Albert model To explain scale-free structure of the World Wild Web, Albert-László Barabási and Réka Albert proposed a model allowing to generate networks with a power-law degree distribution, which was not possible with the classical Erdős-Rényi model. The iterative algorithm they proposed relies on the preferential attachment mechanism. Hereafter is an explannation of the algorithm for the undirected case.

• At the beginning a small network, the seed, is considered:

G 0 = ( • , V 0 , E 0 ) (30)
• At each step k a new node is added to the network G k :

V k = V k-1 ∪ {v k } (31)
• The new node is then connected to m nodes. These nodes are chosen via preferential attachment a : the most connected is a node, the most likely it is to be chosen:

E k = E k-1 ∪ {(v k , v i 1 ), . . . (v k , v im )} (32)
where i 1 , . . . , i m ≤ k and the probability that nodes v i is selected is propor-

tional to deg G k-1 (v i ).
No matter the value of m, if the number of iteration is large enough, the model leads to a network with a degree distribution P (k) ∝ k -3 which corresponds to a scale-free network. This model is the most commonly used to generate scale-free network. A version for directed network can be used. In this case, at each step links are created from m in nodes to the new node, and from the new node to m out nodes with a preferential attachment depending respectively on the indegree and outdegree of the nodes.

to several outcomes in scientific press. These works actually success to prove clearly something: there is almost no networks with a power-law degree distribution. This is true and noteworthy, the power-law is an idealized case for infinite-size network. As said before, two phenomena are used to explain the heavy-tailed degree distribution of some networks: preferential attachment and growing. These phenomena are used in the Barabási-Albert leading to a power law degree distribution: P (k) ∝ k -3 . In real-world a lot more different processes may occur such as disappearance of nodes, disappearance of edges, attraction due to other factors, noise... Since then, these other mechanism has been incorporate in another scale-free generating model [START_REF] Sergey N Dorogovtsev | Structure of growing networks with preferential linking[END_REF]. Therefore, results based on the power-law degree distribution and the Barabási-Albert model are not straightforwardly applicable to real-world network. However, they often furnish a very good approximation. This is a textbook case of the famous aphorism of Georges Box: "All models are wrong, but some are useful ". The two articles [START_REF] Al Barabási | Love is all you need: Clauset's fruitless search for scale-free networks[END_REF][START_REF] Holme | Rare and everywhere: Perspectives on scale-free networks[END_REF] comes back on this controversy and explains that indeed power-law is never reached but this does not disqualify scale-free as a very powerful model. That being said, the omnipresence of scale-free networks in natural and technological systems encourages a better understanding of their properties and the potential advantages, inconvenient and opportunities that they present. We propose in the next section to present some properties flowing naturally from Definition 0.25. Some applications taking advantage of these properties are presented in Appendix 0.3.4. In order to structure the discussion we decided to distinguish roughly properties and applications in the following but sometimes these notions are closed and the distinction can be fuzzy.

Properties of scale-free network

While some properties of scale-free networks depends on the model used to generate them, like the Barabási-Albert model or other models [START_REF] Dangalchev | Generation models for scale-free networks[END_REF][START_REF] Kamrul Hassan | Degree distribution, ranksize distribution, and leadership persistence in mediation-driven attachment networks[END_REF][START_REF] Krioukov | Hyperbolic geometry of complex networks[END_REF], some properties flows naturally from the power-law degree distribution. Here we present some of the most common properties of scale-free network.

Presence of hubs

The main feature of the scale-free network is the presence of highlyconnected nodes the so-called hubs. The other properties flow more or less directly from this fundamental property. On the contrary, in a random network, the presence of nodes with a large number of connection is very unlikely. Thus, before the emergence of the scale-free models, the models based on random networks struggled to capture the effect of the presence of hubs. Taking the World Wide Web as an example, it appears that more than 80 percent of the webpages are referenced by 4 links or less, these are the poorly-connected nodes, and 0.01 percent are referenced by 1000 links or more, these are the hubs [START_REF] Barabási | Scale-free networks[END_REF].

Robustness to random failure A common concern when studying network is the robustness, or resilience, of the system. Does a computer network still works if a part of the equipment crashed ? How longer would be the route from place A to place B if some roads are closed ? How the brain would react if some neurons are inhibited ? Of course each of (a) Random network with 4 random failures: the resulting network is fragmented in three components (b) Scale-free network with 4 random failures: a large component remains wellconnected along with two isolated nodes Figure 11: We compare here the robustness to random failure between random and scale-free networks. As most of their nodes are unimportant, the connectedness resists better to failure in scale-free networks.

this question depends on the interaction between the nodes and are specific to the different problems. However, knowing if the network remains connected or if it is fragmented depends only on the structure of the network. It appears that scale-free networks are very resilient to accidental failures. An accidental failure, by opposition with targeted attacks, developed further, concerns the case where a node is randomly shut down for any reason. Noticing that a large majority of nodes in a scale-free networks are poorly-connected nodes, it appears that if a random fraction of the system fails, it will touch very likely these poorly-connected nodes, and so it will not impact so much the structure of the network. See fig. 11 for a comparison of the robustness of a random and a scale-free network.

Vulnerability to targeted attack The counterpart of the previous property is that scalefree networks can easily be broken apart if the nodes shutting down are aimed to the hub. As the hubs maintain the structure of the network, the removal of the hub would cause an important fragmentation of the network. Figure 12 illustrates this. The consequences of this phenomenon are double: in some cases this represents a threat for the sustainability of the system, in other cases it is a chance to prevent a danger. Indeed, if a network describes a flow of interest, such as information on internet, persons on a traffic network or goods on a delivery network, the presence of such weak spot is a major risk for the durability of the system. On the contrary, if what flows over the network is harmful, such as a disease through a social network or a virus through a computer network, the hubs are strategic points to remove to prevent the spreading.

Small-world Intuitively, the small-world property says that you can go from any node to any other node in few steps in a scale-free network. In a scale-free network, by passing through (a) Random network after removing the three most connected nodes. The resulting network is composed of two big components and an isolated nodes.

(b) Scale-free networks after removing the three most connected nodes. The network is fragmented in 11 parts.

Figure 12: Scale-free networks are sensitive to targeted attack: the hubs are the Achille's heel of this network. Random networks do not have such weakness and the vulnerability is distributed through the whole network.

the hubs you can connect quickly any part of the network. The Barabási-Albert model (and other models leading to scale-free network) is said to be small-world because the characteristic lengths (radius and diameter) of the generated network grow no faster than the logarithm of the number of nodes 15 . This explains, for example, that the air transportation network, exhibiting a scale-free structure [START_REF] Guimera | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF] (as shown in fig. 10), allows to travel anywhere with few connections.

These properties among others (hyperbolic embedding, clustering distribution) flows directly from the definition of scale-free network. In some applications, it is possible to take advantage of these properties and gain efficiency with respect to other networks. In the next section, we present three different applications of scale-fee networks.

Applications of scale-free network

In this section, we present three applications taking advantage of the scale-free properties presented in Section 0.3.3. Actually, these are not direct applications to real-world but computations or approaches benefiting from scale-freeness.

Network navigation

The problem to find the shortest path between two nodes in a network is solved, in particular, thanks tothe Dijkstra algorithm [START_REF] Edsger | A note on two problems in connexion with graphs[END_REF]. However another problem, known as network navigation, is to go from a node to another using only local information: the geographical position of the neighbors and the position of the destination [START_REF] Boguna | Navigability of complex networks[END_REF]. The most obvious strategy is to go at each step as close as possible to the destination. In random network, the navigation performs badly since it is not possible to see distant shortcuts. By contrast, in scale-free networks when the nodes are arranged with the right method, the network navigation performs almost as well as the shortest path method [START_REF] Boguná | Navigating ultrasmall worlds in ultrashort time[END_REF]. This is due to the hyperbolic nature of scale-free networks and the best method to arrange nodes follows a hyperbolic metric 16 . Figure 13 illustrates this propensity of scale-free network for navigation. In this example, the local navigation gives a path as short as the optimal path (computed with the Djikstra algorithm) in a majority of cases: 88% of success. Moreover, in average the path found is 5% longer than the shortest path. By contrast, in a random network the results are way lower: 44.5% of success and 24% longer in average. In spite of the non-optimality, the local navigation presents two advantages in comparison with the Djikstra algorithm which ensures optimality. First, in some cases, the knowledge of the whole network is either impossible or too costly to obtain. Secondly and most important, the time complexity in the case of the Djikstra algorithm is O(n log(n)) where n is the number of nodes in the network while for local navigation it is O(log(log(n)). As an example, for a network with a million nodes the local navigation is about five millions time faster. Thus, when designing the architecture of a network, this feature is a good argument to design with a scale-free structure if a lot of transmission has to been done between nodes (as communications networks).

Strategy of vaccination

To study the evolution of a disease in a population a wide range of model uses network to model the connection among the population. These models form a field of research called network epidemiology presented in Chapter 5. These models can also be used to model the spreading of a computer virus [START_REF] Roberto | A modified epidemiological model for computer viruses[END_REF] or to model information diffusion in a population [START_REF] Guille | Information diffusion in online social networks: A survey[END_REF]. A question of interest is the influence of the structure of the social network on the propagation of the disease. In scale-free networks, the presence of hubs is detrimental as their highconnectivity make them very susceptible to infection, and once infected they can contaminate a lot of individuals: hubs act as epidemic relay. For example, it is shown that, within a particular model (Susceptible-Infected-Susceptible), a disease may eventually disappear totally of a random network [START_REF] Norman | The mathematical theory of infectious diseases and its applications[END_REF], while it always survives in a scale-free network [START_REF] Boguná | Absence of epidemic threshold in scale-free networks with degree correlations[END_REF] for any value of the model's parameters. This sounds like a bad news for scale-free networks: if a social network has a scale-free structure it will be difficult to eradicate a disease, and if a computer network is scale-free, as Internet is [START_REF] Cohen | Breakdown of the Internet under Intentional Attack[END_REF], a virus will easily survive. However, it is possible to take advantage of the sensitive position of the hubs by eliminating them. As seen in fig. 12 (a) We compared shortest path and local navigation on a scale-free network where the nodes are arranged with a hyperbolic metric. The local navigation performs in this case as good as the shortest path computed with the Djikstra algorithm (although the two routes are different).

(b) Over 200 tests, the local navigation performs as the shortest path in 88% of cases and in average the path found is 5% longer. in Introduction when the hubs are removed, a scale-free network is quite fragmented and restrains the diffusion which is not the case in a random network. By chance, with vaccine (or an antivirus in the computer case), it is actually possible to remove a node from the epidemic network. As expected in scale-free network it is very efficient to vaccinate the hubs (which is the persons with the most acquaintances), in priority [START_REF] Pastor | Immunization of complex networks[END_REF]. Of course, this question arises if the number of vaccine is limited or in the case of voluntary vaccination [START_REF] Zhang | Hub nodes inhibit the outbreak of epidemic under voluntary vaccination[END_REF], and raises ethical dimension making it essentially academic. Figure 14 proposes a simulation illustrating this result. This phenomenon may be an incentive when the structure of a network has to be chosen (for a computer network for example). If it is possible to protect few nodes, then a scale-free structure is preferable. Whereas if there is no protection, a random network is a better choice to restrain the propagation. When the structure of the network is already fixed (as social networks), an abstracting network with a scale-free structure can still be used to determine a good vaccination strategy. This point is developed in Section 5.2

Network controllability

The notion of network controllability refers to the ability to steer the state of the network endowed with a dynamical equation as 19 towards a desired state using some inputs. Several notions of controllability can be considered according to the problem. The question of the controllability of scale-free network has divided the opinion of researchers in particular because of these different notions of controllability. We propose here a brief review of these discussions. Network controllability has first been introduced by Lin in 1974 [START_REF] Lin | Structural controllability[END_REF] where he defined structural controllability. A system is structurally controllable if the placement of the inputs (which is matrix B in [START_REF] Anna | Scale-free networks are rare[END_REF]) and the configuration of the network (which is the placement of the non-zeros value of A in [START_REF] Anna | Scale-free networks are rare[END_REF]) allow the inputs to reach any node of the system. As an example we consider a very basic model of information transmission. In this model, nodes represent individuals, edges are communication channels between individuals, and the inputs are information media (a newspaper for example). In this case, the system is said structurally controllable if the information coming from the inputs (newspaper) can reach any node (individuals). Figure 15 illustrates this example. Some results [START_REF] Glover | Characterization of structural controllability[END_REF][START_REF] Shields | Structural controllability of multiinput linear systems[END_REF] have been obtained about structural controllability especially on how to determine if a network is structurally controllable and where to place the inputs to make a given network structurally controllable. However this notion of controllability does not take into account the intensity of the connection between the nodes, which is the weights in the matrix A in [START_REF] Anna | Scale-free networks are rare[END_REF]. The structural controllability only refers to the structure and not to the weighted network. In practice most networks have weighted edges which can represent a strength, a capacity or an intensity for example. To emphasize why this is essential, let us reconsider the network model introduced previously and add a weight on the edges. We consider that these weights correspond to the probability of transmition of the piece of information. Figure 16 presents two scenarios for this model. The two networks are structurally controllable as the information can reach everyone. However, one can feel that the transmission of the signal is much more difficult in the first scenario. If Bill consults only once the information of the input and if the individuals talk only once, the probabilities that (e) Evolution of the percentage of infected people in the four networks. Initially 20% of people are infected and the evolution is driven by the SIS model. The scale-free network performs worse than the random networks. But after the vaccination of the hubs, the epidemic disappears totally in the scale-free network faster than in the random network. In (a) the system is structurally controllable: every node is reached by the input. In (b) the system is not structurally controllable: a node can not be reach by the input.

(a) Bill read the paper with a probability of 0.1. Then the information is transmitted to Anne and to Chloé with probability 0.1.

(b) Bill read the paper with a probability of 0.9. Then the information is transmitted to Anne and to Chloé with probability 0.9. Chloé accepts the information are respectively 0.1% and 72.9%. This example emphasizes a fundamental notion in network control which is not captured by the structural controllability: the energy required as defined in [START_REF] Cheng | Model Reduction of Multiagent Systems Using Dissimilarity-Based Clustering[END_REF]. Indeed, it may be theoretically possible to steer a system towards any desired state while the amount of energy needed make it impossible. It is particularly the case in large-scale network for which the structural controllability is not sufficient in practice. A lot of studies in this domain focus on the placement of the input in view to reduce the energy needed for control. As said before the controllability Gramian defined in [START_REF] Boguná | Models of social networks based on social distance attachment[END_REF] allow to estimate the energy needed to control a given system. There is, at least, three ways to quantify the energy needed to control a system [START_REF] Pc Müller | Analysis and optimization of certain qualities of controllability and observability for linear dynamical systems[END_REF] based on this matrix.

• The energy needed to steer the system from the origin along the most energy-consuming direction. This energy corresponds to the inverse of the smallest eigenvalue of the Gramian 1/λ min (W)

• The average energy needed to steer the system from the origin to any direction. It is proportional to the trace of the inverse of the Gramian T r(W -1 ). If the system is not controllable, the Gramian is singular and W -1 is not computable.

• The volume of the space-state reachable from the origin with a fixed amount of energy. This volume is proportional to the determinant of the Gramian det(W)

Figure 17 shows the value of these energy measure for the model presented in fig. 16 with values of the probability of transmission varying from 0.05 to 1. The three metrics confirm that the highest are the weights in the network the less energy is needed to control the system.

We can now raise the question of the effect of scale-freeness in the controllability of network. Intuitively, it seems that by controlling the hubs which are highly-connected it is easy to steer the state of the whole node. If the information propagation model proposed before is applied on a scale-free network, then it seems that if the individuals with a lot of relation are targeted by the input, then the information would easily spread in the population. However scale-free networks also imply that a large number of nodes are poorly-connected and so are difficult to reach. Liu, Slotline and Barabási proposed in [START_REF] Liu | Controllability of complex networks[END_REF] a major and one of the first contribution on this question. They proposed an algorithm to find a minimal number of input to control to reach controllability. In their study, they consider the structural controllability and not the notion of control energy which has been developed later. They showed that in scale-free network the number of nodes to control is relatively high and their algorithm seems to avoid to place input on hubs. This result has been received with surprise by the community engendering, in particular, two answering papers: The first one [START_REF] Müller | Few inputs can reprogram biological networks[END_REF] written by Müller and Schuppert, two biologists, argued that from their empirical result, it appears that scale-free biological networks can be reprogrammed with few inputs (0.02% of controlled nodes against 80% according to the algorithm of Liu et al.). The second article [START_REF] Noah J Cowan | Nodal dynamics, not degree distributions, determine the structural controllability of complex networks[END_REF] explain why the result of [START_REF] Liu | Controllability of complex networks[END_REF] contradicts the intuition and the empirical results: in the model they proposed, nodes evolves as a function of their neighborhood and do not have a proper dynamic. In most practical cases, though, the evolution of a node is influenced by its current state. It is clear that the link between controllability and scale-freeness is not clear. We propose hereafter several factors which may affect this relation:

• The measure of the controllability: As seen before some consider structural controllability which is a binary measure giving sometimes unrealistic result due to energy requirement. Other measures consider the energy required but several metrics co-exist.

Other measures can also be considered: the minimum dominating set, for example, which also conceals the notion of energy. With this measure, scale-free network appears to be easily controllable as concluded in [START_REF] Jose | Dominating scale-free networks with variable scaling exponent: heterogeneous networks are not difficult to control[END_REF] and [START_REF] Molnár | Minimum dominating sets in scale-free network ensembles[END_REF].

• The system considered: The system may have a linear or non-linear dynamics, and as said before the nodes may have, or not, a proper dynamics. Several generating models leading to scale-free networks can be used and leads to slightly different properties. [START_REF] Doostmohammadian | On the controllability of clustered Scale-Free networks[END_REF] presents the difference of controllability between two models of scale-free networks.

• Type of control: Several question appears: where is the control applied ? It may be on the nodes, or on edges. How is it applied ? It may be open-loop or closed-loop controller. What is the objective of the control ? It may be the whole state of the system, a unique state (single output control) or an aggregated value of the states (output control). Is the control constrained or unconstrained ?

It appears therefore that the question of the controllability of scale-freeness is not unique and indissociable from the scenario, the network system, and the control strategy considered which explains the dissensus on this question. All that being said, we present now briefly an approach developed in [START_REF] Casadei | Scale Free Controllability of Large-Scale Networks: an Output Controllability Approach[END_REF] which is particularly interesting in our case. It shows that scale-freeness is somehow a good feature for an abstracting network used to design a control input of a large-scale network. The objective of the article is to control an aggregation (e.g. the average) of the uncontrolled nodes. Based on In the first scenario, the whole system is considered. A control design can be found to reach a desired state with low energy. However, for large-scale network the computation needed to find this control may be tremendous. The second and third scenarios uses then an abstraction of the large-scale network to reduce the computation requirements and preserve a good approximation of the desired state. Moreover, in the third scenario it is emphasized that if the controlled nodes are the hubs of the network, the energy needed is much lower than for random controlled node.

the observation that for large-scale networks the computation of the controllability Gramian and the optimal control is very time-consuming, the authors propose to considers a smaller network abstracting the large one. They show that using this abstraction, the computation of the optimal control is much faster and preserves a good performance as the output is close to the desired state. Finally, and essentially for us, they show that the control energy needed decreases if the degree of the measured nodes increases. Figure 18 illustrates the main result of this article. Therefore, the abstracting network allows to design a low-computation control directed on few nodes and driving the average state of other nodes close to a desired state. By providing the abstracting network a scale-free structure, the control is moreover low energy-consuming.

Synthesis

Through this presentation of scale-free networks we have seen that it is useful to group together networks with a heavy-tail degree distribution. Indeed, a lot of real-world systems have this tendency and share common properties. We have highlighted some properties flowing from the definition, and some applications taking advantages of these properties. Therefore, when Control, Observability, Estimation, Prediction, Shortest path, Visualization, ...

Initial network not scale-free

Scale-free reduction

Take advantage of scale-free assets Complex, time consuming, computationally intensive, ... designing a new network it may be useful to endow it with a scale-free architecture if these properties may benefit to the applications. In contrast, when considering a pre-existing system, the properties of the network are already fixed and there is no benefit to consider the network as scale-free. However, when a large-scale network is reduced it is possible to impose a scalefree structure to the reduced network in order to benefit from the assets of the scale-freeness by using a reduced network with a scale-free structure. This idea is the very essence of our work and will be developed in particular in Chapter 2. Figure 19 illustrates this principle. Of course, in order to use the reduced system it is essential to preserve the behavior and properties of the initial system. Some properties which are particularly interesting to preserve through the reduction have been presented in Section 0.2.2. In the next section we discuss more precisely the problems we want to tackle and how they are arranged within the thesis.

Problematics and contributions

In order to reduce the complexity or large-scale network we aim through this thesis to develop tools and algorithms to partition a network with the following criteria: i) preserve some properties (dynamical behavior, structural characteristics, ...) of the original network ii) impose some properties (scale-freeness) to the reduced network.

The design of such network partitioning algorithms is the cornerstone of our work to which we graft different related problematics. As evoked, the major one is the design of a partitioning algorithm inducing a scale-free network which will be treated in Chapter 2. Within this chapter we will also think about which properties of the initial network have to be preserved in order to preserve the characteristics of the initial network and how to do so. Before that, we raise a more theoretical question on the structure of the partition itself: as the parts may gather disconnected nodes, what are the drawbacks of imposing the nodes inside each part to be connected ? This question will be explored in Chapter 1. The third major work, treated in Chapter 3, concerns a reconstruction issue. We will investigate how to partition a network between measured and unmeasured nodes in order to ensure that the average of the unmeasured nodes can be efficiently reconstructed. Then, three applications are presented: in Chapter 4, we apply the partitioning algorithm towards scale-freeness to a large-scale urban traffic network. We show then that, thanks to the properties preserved through the partition, the reduced network can be used as an abstraction of the initial network. Finally, Chapter 5 will propose two independent applications in epidemiology. In the first one, we show that the scale-freeness of the abstracting network can be used to build a cure-allocation strategy. In the second application, we take advantage of the result on average reconstruction to estimate the evolution of a disease on a large-scale network. Figure 20 gives an overview of the structure of the thesis.

Publications

Here is a list of the works published or under review by the author.

Conferences

Nicolas Martin, Paolo Frasca, and Carlos Canudas-de Wit. "Network reduction towards a scale-free structure preserving physical properties". In: If the main purpose of the thesis is to investigate partitioning problems, we study in this first chapter a preliminary question. This question concerns the structure of the partition itself and can be formulated as follows: how much adding a connectedness constraint in a partition problem degrades the solution ? Said otherwise, we will compare two classes of problems of optimal network partitioning: in the first class of problem one impose the nodes belonging to a same part of the partition to be connected. In the second class of problem, no constraint of connectedness is imposed. Obviously, this constraint worsens the result of the optimization problem. However, it may be interesting to add this constraint in some applications. Therefore, it is useful to estimate how much this connectedness constraint degrades the optimal solution of the partitioning problem. The estimation of this degradation is the objective of this chapter. The work presented throughout this chapter has been published in [START_REF] Martin | The price of connectedness in graph partitioning problems[END_REF] and presented at the European Control Conference 2019. This work has been carried out partially during my stay in Imura Laboratory in Tokyo Technology institute alongside with the team of Pr. Imura and within the JSPS summer program. Here the nodes are the pupils and the edges represent the friendship between them which can be one-sided (yes it may be sad, but it is for the sake of the example). To constitute working groups, should the teacher consider this friendship network ? This image is from "Les Choristes" of Christophe Barratier.

The price of connectedness and problem formulation

Introducing problem: a textbook case

We present first a short scenario in order to familiarize the reader with the problem before introducing a more formal framework. We consider a class in which some pupils are friends and some are not as shown in fig. 1.1. For an activity, the class has to be divided in some groups of different sizes: for example, 20 pupils have to be divided in 4 groups of sizes: 4, 7, 6 and 3. The teacher wants to optimize the groups regarding a precise metric: he wants to be the groups to be as homogeneous as possible. Therefore he wants to minimize the average standard deviation of level within the groups. Before addressing the grouping problem, the teacher wonders if he should add a constraint of friendship within the groups. By adding such a constraint, the best grouping he can find would be always worse or equal than in the unconstrained case. Indeed, the unconstrained case includes all the constrained grouping. However, the teacher wonders how much this constraint would damage the quality of the solution which is the homogeneity inside each group. When looking at the network of friendship, adding this constraint means that each group have to form a weakly connected subgraph. If the teacher want to please the kids, he has to pay in counterpart a deterioration of the quality of the grouping. He has to pay the price of connectedness.

The price of connectedness

Generalizing the previous example, any partitioning problem can be solved with or without the connectedness constraint. Of course, adding a constraint to a problem can only reduce the quality of the optimal solution. But, as discussed later, in some circumstances this constraint is necessary. In this chapter, we consider network partitioning problems which can be seen as optimization problems. A large number of works have treated partitioning problems with different objective function and constraints. For example, [START_REF] Monshizadeh | Stability and synchronization preserving model reduction of multi-agent systems[END_REF] aims to preserve stability and synchronization of the system, [START_REF] Cheng | Reduction of secondorder network systems with structure preservation[END_REF] and [START_REF] Cheng | Model Reduction of Multiagent Systems Using Dissimilarity-Based Clustering[END_REF] preserves the network structure, [START_REF] Umar | Scale-free estimation of the average state in large-scale systems[END_REF] looks for the best reduced system in order to estimate an aggregated state of the initial network and [START_REF] Ishizaki | Model Reduction and Clusterization of Large-Scale Bidirectional Networks[END_REF] provides a reduced system with a dynamical behavior close to the initial system while preserving several properties for control purpose. This last work will be presented in this chapter as a motivating example. A partition respecting the connectedness constrained is named here connected partition. In some cases, it is relevant to prefer connected partitions: as in the introducing example, when consider social network one may want to find a partition ensuring that in each part the individuals are related. When studying epidemic spreading through a population, it is interesting to detect communities1 in order to apply a control or to observe the evolution at the borders [START_REF] Martin | MergeToCure: a New Strategy to Allocate Cure in an Epidemic over a Grid-like network Using a Scale-Free Abstraction[END_REF]. In another register, when considering networks with a geographical nature such as urban traffic networks, transportation networks or power grids one may want to preserve the geographical nature of the system and so imposing each part to be connected. In urban traffic network, if the reduced network is used for estimating the traffic state [START_REF] Ladino | Traffic state estimation and prediction in freeways and urban networks[END_REF], we want that each part of the partition corresponds to a geographical area. Since we consider directed networks, connectedness may have different definitions as explained in the introduction. We will consider here weak connectedness as it is enough to ensures the preservation of the geographical nature of the network. When the connectedness constraint is considered, it is clear that the optimal solution is always worse or equal to the optimal solution without the constraint. In this chapter, we investigate how much the connectedness constraint degrades the solution regarding to the structure of the network. The difference between the two optimal solutions is named the price of connectedness2 and denoted by ∆. It is clear that the price of connectedness actually depends mainly on the optimization problem. For example, if the metric to minimize favors connected partitions, adding the constraint will not affect too much the result. As an example, we formalize a similar problem as in the introducing case. We consider a network where a value is given to every node. We pose now the following problem: Find a partition of size n minimizing the average variance within the parts. If in the system of interest it turns out that adjacent nodes tend to have close values then the price of connectedness will be relatively small. Figure 1.2 illustrates such a case. The approach proposed here aims to estimate the price of connectedness without solving the two optimization problems. Even more, we actually do not consider any particular partitioning problem and we want to estimate the price of connectedness in a network for any problem. As the partitioning problem is an optimization problem, adding the connectedness constraint amounts to reduce the feasible set of the problem. Therefore, we propose to estimate the price of connectedness with the ratio of the cardinalities of the two feasible sets: the set of partitions and the set of connected partitions. It is clear that this approximation is somehow coarse since we do not consider any particular problem. In the other hand, it allows to have an estimation of the price of connectedness of a given network for any partitionning problem. See fig. 1.3 for an illustration of this approach. This ratio is named hereafter ratio of connectedness and is denoted by ρ. To motivate this approach we will first present some simulations on a partitioning problem from the literature: the cluster model reduction [START_REF] Ishizaki | Clustered model reduction of positive directed networks[END_REF]. We focus then on the estimation of the ratio of connectedness ρ. Note that this ratio can also be viewed as the probability that a given partition is a connected partition. We consider in this article random directed network obtained via the directed Erdős-Rényi model detailed later. We will show then that the value of ρ in an Erdős-Rényi graph is directly linked with ρ the probability that an Erdős-Rényi graph is connected. The value of this latter probability has been investigated by a broad literature providing asymptotic estimations. See [START_REF] Matthew | Social and economic networks[END_REF] for a discussion on these results. These asymptotic estimations are valid for very large networks. We propose here an upper bound on ρ valid for networks of any size. From this result we derive an upper bound on the ratio of connectedness ρ. Let us reconsider the introducing problem to explain approach. For any problem of pupils partition for which the sizes of the part are known, we propose to estimate the deterioration of the optimal solution caused by the friendship constraint by comparing the number of ways to partition the pupils with and without the constraint. Intuitively, if almost all pupils are friends, almost every partition will be a friendly partition and so the price of connectedness is low. At the contrary, if the number of friendship is low, there are few friendly partitions compared to the number of partition, and so the price of connectedness is high. The main contributions of this chapter are:

(i) Highlighting the relation between the price of connectedness ∆ and the ratio of connectedness ρ via a numerical example (ii) The link between ρ in an Erdős-Rényi graph and the probability ρ that an Erdős-Rényi graph is connected; and finally (iii) the derivation of a tight upper bound on ρ leading to a tight upper bound on ρ, both for Erdős-Rényi graphs

The chapter is composed as follows: in Section 1.2 an example illustrates the price of connectedness in a concrete problem and the link between ∆ and ρ, Section 1.3 contains the main results, namely the estimation of ∆. Section 1.4 presents some simulations showing the validity and the tightness of the estimation. A last section concludes the chapter.

Illustrative example: The clustered model reduction

In this section, we will present an example of partitioning problem from the literature. Within this example we will emphasize the price of connectedness which is the gap between the solutions of the constrained and unconstrained problems.

The clustered model reduction problem

Consider the following discrete-time linear system:

Σ : x(t + 1) = Ax(t) + Bu(t) (1.1)
where x(t) ∈ R n is the state of the system. Given n the desired size of the reduced system. We define the reduced system as follows:

ΣP : ξ(t + 1) = P AP ξ(t) + P Bu(t) x(t) = P ξ(t) (1.2)
where P ∈ R n×n is the reduction matrix. The problem is to find the matrix P making the dynamics of ΣP the closest to the dynamics of Σ. More precisely, we want to minimize g -ĝP H 2 , where g is the transfer function from control u to state x and ĝP is the transfer function from control u to state x and where • H 2 which is the H 2 norm is the root-meansquare of the impulse responses of the system defined as follows:

g H 2 = 1 2π ∞ -∞ T r (g(e jω ) g(e jω )) dω (1.3)
The H 2 norm measures the energy of the impulse response and imposing g -ĝP H 2 to be small implies that the responses of system Σ and ΣP are close. Thus, the system ΣP can be used as an abstraction of the system Σ for control purposes since they have a similar behavior.

A continuous-time version of the problem was first presented in [START_REF] Ishizaki | Clustering-based H 2 -state aggregation of positive networks and its application to reduction of chemical master equations[END_REF] followed by different extensions in [START_REF] Ishizaki | Clustered model reduction of positive directed networks[END_REF][START_REF] Ishizaki | Model Reduction and Clusterization of Large-Scale Bidirectional Networks[END_REF] and [START_REF] Ishizaki | Model reduction of multi-input dynamical networks based on clusterwise controllability[END_REF]. The unconstrained problem can be written as follows: To formulate the constrained problem associated to (1.4) we introduce I(P ) the partition associated to the reduction matrix P . We have I(P ) := {I 1 , I 2 , . . . , I n} where I l is a part of the partition defined as:

min P ∈R n×n g -ĝP H 2 , (1.4)
I l := {j ∈ {1, . . . , n}, P l,j = 0} (1.5)
As an example, let P be the following partition matrix:

P =   0 0 0 0 0 0 0 0 0 0 0 0   (1.6)
where represents any non-zero real number, then I(P ) = {{1, 2, 4}, {3}, {5, 6}}.

min P ∈R n×n I(P )∈Ic(G) g -ĝP H 2 (1.7)
In [START_REF] Ishizaki | Clustered model reduction of positive directed networks[END_REF] the authors propose an algorithm to solve the problem defined in (1.4). In appendix A, we present this algorithm and its adaptation allowing to solve the constrained problem (1.7).

In the next section, some simulations illustrate the price of connectedness in this case.

From the price of connectedness to the ratio of connectedness

We propose here to show the price of connectedness in the clustered model reduction via numerical simulations. Then we present an estimator of interest: the ratio of connectedness.

Simulation 1.1. Let us first introduce properly the directed Erdős-Rényi model that we will use.

The directed Erdős-Rényi model The model first introduced in [START_REF] Erdos | On the evolution of random graphs[END_REF] allows to generate random directed networks as follows:

We consider n vertices and each of the n 2 potential edges (self-loop are allowed) exists with a probability p. The expected value of number of edges is then pn 2 and the mean degree is pn. The degree distribution is known to be a Poisson law.

We consider a collection of 500 Erdős-Rényi graphs with p = 0.2 and n = 100 denoted G 1 , . . . , G 500 . Thanks to the algorithms presented in Appendix A, we solve the partitioning problems (1.4) and (1.7) for each network G i and for different size of the reduced network n. We denote by u the mean error in the unconstrained problem and by c the mean error in the constrained problem which is: The difference between the two results is the price of connectedness.

The relative difference between the two errors represented by an arrow in fig. 1.5 is the price of connectedness denoted by ∆ and defined as:

∆ := c -u u (1.10)
To estimate the value of this difference by only knowing the structure of the network, we propose to use the ratio of connectedness presented hereafter.

The ratio of connectedness: a counting-based estimation

Beyond this example, the loss due to the connectedness constraint always exists in any partitioning problem. We propose here to tackle this question at a high level: we propose to estimate the price of connectedness for any couple of problems which can be formulated as an optimization problem.

min

I∈I(G 0 ,M ) J G 0 (I)
and min

I∈Ic(G 0 ,M ) J G 0 (I) (1.11)
where J G 0 is any cost function of the following form:

J G 0 : I(G 0 , M ) -→ R (1.12)
and where I(G 0 , M ) is the set of partition of G 0 such that the part i has a size m i ; and

I c (G 0 , M ) ⊂ I(G 0 , M ) is the set of connected partition. M = (m 1 , m 2 , . . . , m |I|
) is called the size vector and verifies m i = |V 0 | The two problems of (1.11) are respectively the Unconstrained Problem and the Constrained Problem. The approach presented here consists in comparing the cardinalities of I and I c which are respectively the set of partition and the set of connected partition of G 0 . More precisely, given a network G having n nodes, and a vector M we want to estimate the ratio of connectedness defined as follows:

ρ(G, M ) := |I c (G, M )| |I(G, M )| (1.13)
This serves as a proxy to estimate the price of connectedness. Note that I(G, M ) actually does not depend on G as the connections between nodes do not matter 3 . Before going deeper into the estimation of ρ, we will present in the next section some evidences on the link between the ratio of connectedness ρ and the price of connectedness ∆.

Relation between ρ and ∆ in the clustered model reduction

A way to emphasize and make more precise the relation between ρ and ∆ is to observe simulations on the clustered model reduction presented in the previous section. Precisely, we want to observe how the price of connectedness ∆ evolves when simulations are done with networks having a different ratio of connectedness ρ. For this purpose we consider 100 Erdős-Rényi graphs with n = 100 vertices and an edge probability p varying between 0 and 14 . Figure 1.6 shows the relation between ρ and ∆. By inspection it seems that, in this case, ∆ can be approximately related to ρ via the following equation:

∆(ρ) = -γ log(ρ) (1.14)
with γ ≈ 0.17. Moreover, this function verifies ∆(ρ) -→ ∞ as ρ → 0 and ∆(1) = 0 which is what we expect from the relation5 between ∆ and ρ. While the relation (1.14) is intrinsically linked to the particular couple of problems (1.4)-(1.7) considered here, it is clear that ∆ and ρ are generally related. This relation is intuitive when formulated as follows: the smaller the feasible set of the constrained problem, the larger the gap between the solutions of the constrained and unconstrained problems. Motivated by this example, we propose, in the next section, a tight upper bound on ρ in a (n, p)-Erdős-Rényi graph for a given partition size vector M .

Value of the ratio of connectedness in a (n, p)-Erdős-Rényi graph

In this section we develop the calculations leading to an estimation the ratio of connectedness in a directed (n, p)-Erdős-Rényi graph for a given partition size vector M .

Factorization formula

As we consider Erdős-Rényi graph, we denote by ρ(n, p, M ) the expected value of the ratio of connectedness of a (n, p) Erdős-Rényi graph. Noticing that drawing randomly m nodes in a (n, p) Erdős-Rényi graph is equivalent to generate a (m, p) Erdős-Rényi graph, we can decompose the price of connectedness as follows:

ρ(n, p, M ) = n i=1 ρ(m i , p) (1.15)
where ρ(m i , p) is the probability that a (m, p) Erdős-Rényi graph is weakly connected. We focus now on ρ(m, p) the probability of connectedness of a (m, p)-Erdős-Rényi graph. This question has been investigated in several works. Already the seminal paper of Erdős and Rényi [START_REF] Erdos | On the evolution of random graphs[END_REF] described a phase transition behavior for the value of this probability in the case of undirected graph. Several works [START_REF] Boguná | Generalized percolation in random directed networks[END_REF][START_REF] Alasdair | A note on thresholds and connectivity in random directed graphs[END_REF] investigate the phase transition behavior in Erdős-Rényi directed graph. However only results for strong connectedness are provided while we look here for weak connectedness. In particular, if we denote by G n,p a random (n, p)-Erdős-Rényi graph and S the set of strongly connected networks it is shown that:

P(G n,p ∈ S) -→ n→∞ 1 if p > ln n n P(G n,p ∈ S) -→ n→∞ 0 if p < ln n n (1.16)
Where P(χ) is the probability of χ. From our knowledge there is not such result for weak connectedness. However, it is clear that if such a threshold exists it should be smaller or equal to ln n n , because weak connectedness is a milder property than strong connectedness, and we presume that it is equal. Phase transitions results are pertinent for large-scale networks. However in the case of network partitioning the size of the parts are relatively small (which is m i in (1.15) is small) and so these results can not be used. In the next section we propose an upper bound on ρ: the probability of weak connectedness for a directed Erdős-Rényi graph.

Upper-bound on ρ

To estimate the probability ρ(m, p), we propose to consider an upper bounding probability ρ0 (m, p) which is the probability that in a (m, p)-Erdős-Rényi graph there is no isolated node (node with zero indegree and outdegree). The set of connected networks is included in the set of networks without isolated nodes, which implies that ρ0 (m, p) > ρ(m, p) (1.17) Some works have emphasized a phase transition behavior for the probability of presence of isolated nodes [START_REF] Galli | On the distribution of the number of isolated vertices in random undirected graphs[END_REF][START_REF] Hopcroft | Advanced Design and Analysis of Algorithms -Lecture 7: More on Graph Connectivity[END_REF]. These results are only for undirected networks and are valid for large-scale networks. The following proposition gives an exact expression for ρ0 :

Proposition 1.1
Let ρ0 (m, p) be the probability that a directed (m, p)-Erdős-Rényi graph has no isolated nodes. We have

ρ0 (m, p) = 1 - m 2 -2 k=0 θ(m, k)p k (1 -p) m 2 -k (1.18)
where θ(m, k) is the number of directed networks with m nodes and k edges and with (at least) one isolated node.

Proof of Proposition 1.1 Let us denote Γ m the set of networks with m nodes having isolated nodes and Γm its complement which is the set of network with m nodes and no isolated nodes. Let G m,p be a random Erdős-Rényi graph

ρ0 (m, p) = P(G m,p ∈ Γm ) (1.19) = 1 -P(G m,p ∈ Γ m ) (1.20)
Now if we denote Γ k m the set of networks of size m with isolated nodes and k edges we have:

ρ0 (m, p) = 1 - m 2 k=1 P(G m,p ∈ Γ k m ) (1.21)
Every network in Γ k m has the same probability to appear which is the probability that a (m, p)-Erdős-Rényi graph has k edges. Hence we have

P(G m,p ∈ Γ k m ) = |Γ k m |p k (1 -p) m 2 -k . Let us denote θ(m, k) := |Γ k m |. Noting that θ(m, m 2 ) = θ(m, m 2 -1) = 0 leads to the result.
Therefore, we obtain a value for ρ0 depending on the value of θ(m, k). By reusing the factorization formula in (1.15) we deduce ρ 0 an upper bound on ρ which is:

ρ 0 (n, p, M ) = n i=1 ρ0 (m i , p) (1.22)
To complete the calculations, the next result specifies the value of θ(m, k) Proposition 1.2 Let θ(m, k) be the number of networks with m nodes, k edges and (at least) one isolated node. We have

θ(m, k) =            m 2 k if k < m 2 m- √ k s=1 m s (m-s) 2 k -θ(m-s, k) if k ≥ m 2 (1.23) Proof of Proposition 1.2
When k the number of edges of a network is strictly smaller than m 2 it is impossible that the k edges cover the m nodes. Thus, any network with m nodes and k < m 2 edges contains (at least) one isolated node. The number of such network is equal to the number of way to arrange k edges among the m 2 possible edges. This number is equal to m 2 k . Let's denote θ s (n, k) the number of networks with n nodes, k edges and exactly s isolated nodes. We have:

θ(m, k) = m s=1 θ s (m, k) (1.24) Let us remark that s > m - √ k =⇒ θ s (m, k) = 0 because it is not possible to have k edges in less than √ k nodes.
Hence we can rewrite the previous equation as:

θ(m, k) = m- √ k s=1 θ s (m, k) (1.25)
Moreover, θ s can be rewritten as follows:

θ s (m, k) = m s σ(m -s, k), (1.26)
where σ(m -s, k) is the number of networks with m -s nodes, k edges and no isolated node. This value is multiplied by the number of ways to choose the s isolated nodes within the m nodes, which is m s . We have then:

θ(m, k) = m- √ k s=1 m s σ(m -s, k) (1.27)
Finally, σ the number of networks without isolated nodes is equal to the total number of networks minus the number of networks with at least one isolated node, and so:

σ(m -s, k) = (m-s) 2 k -θ(m -s, k).
Leading to the result.

The same reasoning can be used to solve the problem for a directed network without selfloops or for an undirected network with or without self-loops. In these cases the m 2 -2 in the limit of the sum in (1.18) Considering that there are relatively few networks which are not connected while having no isolated nodes, the two probabilities ρ(m, p) and ρ0 (m, p) appears to be really close. Actually, the inital work from Erdős and Rényi [START_REF] Erdős | On the evolution of random graphs[END_REF] implies that the two probabilities tend towards each other for large m: Proposition 1.3 Let ρ(m, p) be the probability that a random (m, p)-Erdős-Rényi graph is connected and ρ0 (m, p) be the probability that a random (m, p)-Erdős-Rényi graph has no isolated nodes, then:

lim m→∞ ρ(m, p) ρ0 (m, p) = 1 (1.28)
This result straightforwardly leads to this second result:

lim n→∞ ρ(n, p, M ) ρ 0 (n, p, M ) = 1 (1.29)
In the next section we present some simulations to validate the closeness of the upper bound proposed. Before this, fig. 1.7 sums up the approach developed throughout this chapter.

Validation of the upper bound

To illustrate the relevance of the upper bound used for the probability of weak connectedness in an Erdős-Rényi graph, we compare an experimental value of ρ(m, p) and the theoretical value of ρ0 (m, p) given in (1.18). To find the experimental value we generate 1000 (m, p)-Erdős-Rényi graphs for each value of of m = {6, 8, 10, 12} and p = {0, 0.02, 0.04, . . . , 1}. An approximation of ρ(m, p) consists in counting the proportion of the 1000 networks that are connected. The results are presented in fig. 1.8. We notice that i) the inequation ρ0 ≥ ρ is well verified and ii) the upper bound ρ0 is relatively close to ρ and the difference seems to vanish when m grows as predicted by Proposition 1.3. Let us note that the formula given in Proposition 1.2 does not allow to compute θ(m, k) for large value of m. Indeed the recursive call to the function θ is computationally heavy and the value of the binomial coefficient grows quickly. Now that we have seen that ρ0 is tightly upper bounding ρ we want to come one step back and verifying that the upper bound ρ 0 derived from ρ0 by way of (1.22) is also tightly upper bounding ρ. To compute an experimental value of ρ(n, p, M ), as before, we generate 1000 Erdős-Rényi with n = 100 nodes for each value of p varying between 0 and 1. For each network we generate a random partition with the part sizes m 1 = m 2 = . . . = m 20 = 5. An approximation of ρ consists in counting the proportion of the 1000 networks whose partition is connected. The results are presented in fig. 1.9. We verify that the upper bound is indeed very close to the real value. Though for few value of p it seems that ρ(n, p, M ) > ρ 0 (n, p, M ), it is only due to statistical noise.

Conclusion

When looking at network partitioning problems, it is clear that imposing a connectedness constraint deteriorates the quality of the solution. However, this constraint is essential for some applications (in particular when the network has an underlying geographical nature).

We presented here an approach based on probability and counting allowing to estimate the price of connectedness which is the degradation due to the connectedness constraint. This is a high-level approach in the sense that it does not focus on the particular optimization problem, only on the cardinalities of the feasible sets in the constrained and unconstrained cases. The drawback of this high-level approach is that, the results are not precise when considering a particular problem. the ratio of connectedness influences the price of connectedness. In other words, the study of the function ∆(ρ) which depends on the particular problem considered. Another extension of this work would be the simplification of the recursive formula given in Proposition 1.2 allowing to make it computable for large-scale networks. This chapter and in particular the last results shows us the effect of the connectedness con-straint with respect to the the topology. The price of connectedness is negatively correlated to the density of the network. In the scenario considered in fig. 1.9 if p < 0.3 (which means that each nodes has less than 30 connections in average), the ratio of connectedness is almost null which means that the number of connected partitions is negligible compared to the number of partitions and the difference between the constrained and unconstrained problems will be considerable. At the contrary, when p > 0.7 (which means that each nodes has more than 70 connections in average), the ratio of connectedness is almost equal to one which means that almost any partition is a connected partition and the difference between the constrained and unconstrained problems is negligible.

Throughout the thesis we will apply results about partitioning to urban traffic networks and epidemic networks. As discussed in the introduction, both of these applications gain to be partitioned with the connectedness constraint. This preliminary analysis enlighten us regarding the loss due to this physical constraint.

Chapter 2

Network partitioning algorithm towards scale-free structure As seen in Introduction, scale-free networks endow interesting properties which are helpful in different contexts. Moreover, if a network does not have this particular structure, we claim that it is interesting to consider a scale-free network abstracting the initial one. To this end, this chapter presents the results we obtained regarding the problem of network partitioning inducing scale-freeness. Further in this thesis, Section 5.2 and Chapter 4 present practical implementations of this approach are proposed. A primary version of the result introduced in this chapter has been presented at the 2018 European Control Conference in Limassol, Cyprus [START_REF] Martin | A network reduction method inducing scale-free degree distribution[END_REF] and a more complete version has been published in Transaction on Network Science and Engineering [START_REF] Martin | Large-scale network reduction towards scale-free structure[END_REF]. A video popularizing this approach has also been produced1 .

Introduction

The approach proposed in this chapter combines several objectives: starting with a large-scale initial network, we aim to reduce it into a scale-free network while preserving characteristics of the initial network. As seen in the introduction, interesting properties emerge naturally from the definition of scale-free networks [START_REF] Mark Ej Newman | The structure and function of complex networks[END_REF]. We recall here some of those properties: small distances between nodes [START_REF] Cohen | Structural properties of scale-free networks[END_REF], robustness to random failures, easiness to disconnect, hyperbolic space embedding [START_REF] Boguná | Sustaining the internet with hyperbolic mapping[END_REF]. These properties allow to gain efficiency in some applications such as network navigation, vaccination in epidemiology, or control design as developed in Appendix 0.3.4. In order to reap these advantages, we propose in this chapter to find a network abstracting an arbitrary large-scale network and exhibiting a scale-free structure. However, we do not investigate here to what extent the scale-freeness of the reduced network may be meaningful for the initial network. We focus only on the design of a reduction method whose output is a scale-free network. In Section 5.2 though, we will present an application where the scale-freeness of the abstracting network is useful. The main contributions of this chapter are as follows:

(i) The introduction of a framework to treat a class of network partitioning problem along with a meta-algorithm to solve such problems.

(ii) The analysis of two particular problems falling in the scope of the framework. In particular, the second problem requires the analysis of several properties of network.

(iii) The analysis of the performance of the algorithm and the tuning of the parameters studied on synthetic networks.

The chapter is organized as follows: Section 2.2 introduces a class of problem and gives a general approach to solve them, Sections 2.3 and 2.4 presents two particular problems of this class: the first one is rather simple and has a pedagogic and illustrative purpose. The second one implies the analysis of the preservation of different network-related properties. Section 2.5 gives some results on the algorithm proposed in 2.4 and a simulation of this algorithm applied on an academic case. Finally, Section 2.6 concludes the chapter.

Framework for a class of problems

This section is devoted to the introduction of a class problems of network partitioning inducing scale-freeness while preserving features of the initial network. This type of problem can be seen as an optimization problem with some constraints. We propose then a general method to solve this type of problem. The problem formulation along with the solving method form a framework that we will use to treat two particular problems in the two following sections.

Targeting scale-freeness as an optimization problem

The problem treated in this chapter is to find a partition S of an initial large network G 0 , such that the network G 1 coming out of the partition S has a degree distribution close to a given scale-free distribution. We also want G 1 to preserve some physical properties of G 0 and guarantee a certain similarity between G 0 and G 1 . Therefore, this problem can be formally stated as follows:

Problem 2.1
Given an initial network G 0 ∈ Ψ, and a desired scale-free coefficient α, find a network G 1 , solution of the following minimization problem.

min G J SFα (G), subject to G 0 G G ∈ Ψ G 0 ≡ G (2.1)
where:

• J SFα is a α-scale-free cost function (J SFα (G) = 0 meaning that G is perfectly scale-free with a coefficient equal to α)

• Ψ is the set of networks respecting the physical properties imposed.

• ≡ is a binary relation translating a certain similarity between the initial and final network.

The physical constraint (G ∈ Ψ) and the similarity constraint (G 0 ≡ G) does not have any mathematical difference and one could have gather them. We separate them in the formulation to emphasize that the underlying motivations for both is different. This formulation includes a large number of partitioning problems depending on Ψ the properties to preserve and ≡ the binary relation considered. Note also that any scale-free cost function can be used to steer the reduce network towards this type of network. We present hereafter a simple scale-free cost function that we will use.

Scale-free cost function

We present here an intuitive measure of scale-freeness that we will use throughout this chapter. We first define what is the ideal scale-free distribution and then we explain how we measure the distance to this ideal case.

Definition 2.1 (Scale-free target distribution)

The α-scale-free target distribution of range n, denoted Π SF α,n corresponds to the most scale-free distribution that a network of size n could have. It is defined as follows:

Π SF α,n = 1 kcut i=1 i -α      1 -α 2 -α . . . k -α cut      (2.2)
where k cut is a cut-off calculated as the highest degree for which the number of nodes having this degree is higher than 1 in a α-scale-free network of range n:

k cut = argmax k k -α k i=1 i -α ≥ 1 n (2.
3)

The normalization term

1 k cut i=1 i -α
allows us to compare degree distributions of any size with the target distribution. The cutoff k cut is needed more for technical reasons: it avoids to penalize a distribution for negligible value in the tail of the target distribution and it fixes a limit for the practical computation of the distribution. We define now the scale-free cost function: Definition 2.2 (Scale-free cost function) For any network G the scale-free cost function is the L 2 relative distance to the target distribution.

J SFα (G) = Π G -Π SF α,|G| 2 Π G 2 , (2.4)
where Π SF α,|G| is the scale-free target distribution defined as in (2.2) and |G| is the number of nodes in G.

Let us note that Π G and Π SF α,|G| are not necessarily of the same size. In this case, zeros are added at the end of the smallest vector so that the sizes match. Figure 2.1 illustrates this cost function.

It is also possible to impose a scale-free distribution both on the indegree and the outdegree with two different coefficients α in and α out . In this case the scale-free cost function is:

J SFα (G) =µ in Π in -Π SF α in ,|G| 2 Π in 2 + µ out Π out -Π SF αout,|G| 2 Π out 2 (2.5)
where µ in , µ out > 0 are two coefficients allowing to adjust the relative importance to steer one distribution with respect to the other one. Having two different scale-free coefficients for indegree and outdegree can be useful: if the network considered is endowed with a linear dynamical system as in [START_REF] Anna | Scale-free networks are rare[END_REF], the work in [START_REF] Lindmark | A driver node selection strategy for minimizing the control energy in complex networks[END_REF] suggests that different scale-free coefficients for indegree and outdegree distribution can be useful to improve controllability. Note that the mathematical results presented further are independent of the scale-free cost function chosen. Hence, any definition of the cost function could be used without questioning the validity of the results. However, as we are going to see, this definition gives sufficiently good results. . By minimizing the dashed zone the reduce networks tends to be scale-free.

A meta-algorithm to solve the optimization problem

In this section, we present a general method providing a sub-optimal solution to problems of the class presented in the previous section. This is a meta-algorithm in the sense that it gives the skeleton of the method, and for each specific problem, some specifications have to be provided. A way to solve exactly this problem is to explore all the partition of a given network and select the one which minimizes the scale-free cost function and respects the constraints. However, as mentioned in Chapter 1 the number of partitions of a network is very large (even for connected partitions) and the exploration of all of them is computationally unfeasible. We propose hence an iterative algorithm in which at each step we look for the merging S v,w minimizing the scale-free cost function2 . As presented in introduction, a merging is a particular type of partition where only two nodes are gathered together. Therefore, instead of exploring once the set of all partitions we explore iteratively the set of merging. By doing this, the number of computations is hugely reduced. Here is an insight of this economy of computation: the number of partitions of a network with n nodes in k parts is called the Stirling number of the second kind, and its order of magnitude is k n-k [START_REF] Cameron | On Stirling numbers of the second kind[END_REF]. In contrast, the number of merging of a network with n nodes is n 2 and to reach k parts, the research has to be iterated n -k times. Therefore, via this approximation, the number of candidates to test goes down from about k n-k to (n -k)n 2 , which is a huge improvement when considering large-scale network. As an example, to partition a network of n = 100 nodes in k = 20 parts, the exploration of all partitions would require around 10 104 test and an iterative exploration of merging would require around 8.10 5 tests. In the particular case of connected partitions, the computations would be more complicated (the estimation found in Chapter 1 could be used) but the gain would be of the same magnitude. By using this approximation, the Scale-Free cost-function is only minimized at each iteration. This is a greedy algorithm, and it will not find the best solution of Problem 2.1. We will see, though, that the networks obtained with this method are sufficiently close to a scale-free structure. Furthermore, even with this approximation, when dealing with large-scale networks, looking for the best merging S v,w within all pair of nodes (v, w) still requires heavy computations. As pointed above the number of tests is cubic with respect to the number of nodes. For a network with ten thousand nodes, it would require around 10 12 tests, which is unreachable in reasonable time. Therefore, to cut this complexity, the best merging S v,w is searched among a relatively small random subset of pair of nodes (v, w). The effect of the approximation due to this random selection will be discussed later.

Based on this, we present now the meta-algorithm providing a sub-optimal solution to Problem 2.1. Algorithm 1 describes our approach; therein G k is the network at step k and is represented by the triple (A k , E k , V k ). The inputs are the initial network G 0 ∈ Ψ, a scale-free coefficient α SF > 0 and an integer n rand ∈ N corresponding to the the size of the random subset of pair of nodes. As explained previously, the algorithm consists in a loop (line 2)

Algorithm 1 Meta algorithm -Merge To Scale-Free Input: G 0 , α SF , n rand Output: G end 1: k = 0 2: while ¬stop do 3: Ω ←-n rand random elements of V k × V k verifying constraints of Problem 2.1 4:
for (v, w) ∈ Ω do 5:

n SF (S v,w ) = J SFα (Merge(G k , S v,w ))

6:
end for 7:

S best = argmin n SF (S v,w )

8:

G k+1 = Merge(G k , S best ) 9:
k = k + 1 10: end while decomposed as follows: first a random subset Ω of n rand pair of nodes is generated (line 3). Then for each pair of nodes (v, w) in Ω, the scale-freeness of the network obtained by merging S v,w in the network G k is computed (line 5). Finally, the best merging under the constraints of the problem is selected (line 7) and the new network is obtained by operating this merging (line 8). The function Merge associates to a network G and a merging S, a new network obtained G 1 verifying G 0 S G 1 . Function Merge may include the computation of the weights of the new network in order to respect the constraints of the problem. The stopping criterion stop is not discussed here, it may be defined as the step where it is no more possible to find a merging that decreases the scale-free cost function, or as a fixed number of iterations if the size of the reduced network is given. Let us note that if we want to obtain a connected partition it is sufficient to consider only pair of connected nodes at each step: the line 3 is thus replaced by Ω ←-n rand random elements of E k .

(2.6)

The loss due to this modification has been discussed in Chapter 1. For now on, we will mainly focus on the connected partition case, as the problem posed in this chapter is more addressed to traffic networks with a geographical nature. The class of problem 2.1 and the Algorithm 1 form the framework in which the two following sections take place. This framework will also be used in an application to epidemic developed in 5.2 where we take advantage of the scale-freeness of the abstracting network to design a vaccination strategy.

A first instance of the problem fostering node similarity

In this section, we present a first problem fitting the class of problem 2.1. We consider here a network, in which a value is attributed to each node. Besides the scale-free objective, we want to obtain a partition in which the value of nodes within a same part are close. This section does not present any major contribution but has a didactic purpose to manipulate the framework presented before. It will also allow to illustrate the algorithm with an online animation.

Specific problem formulation

A way to ensure a coherency in the reduced network G 1 is to gather only nodes of G 0 having a close value. For example, in a social network we may want to merge only individuals of the same age, or in a road traffic network to merge only roads with a similar density. We denote {x 1 , . . . , x n } the value attributed to each node of G 0 and S the partition of G 0 defined as:

S = {S 1 , S 2 , . . . , S p } where S k = {v i 1 , . . . , v ip k } ⊂ V 0 (2.7)
In order to define the constraint we introduce the following notion.

Definition 2.3 (Divergence)

Considering a network G 0 and a partition S, we define ∆(G 0 , S) the divergence of G 0 in S the following quantity:

∆(G 0 , S) = max S k ∈S max i,j∈S k |x i -x j | (2.8)
The divergence of G in S is the maximal difference between two nodes in a same part. We want to ensure that two nodes in a same part have at maximum a distance of . This leads to the following formulation of the problem: Problem 2.2 Given an initial network G 0 , a desired scale-free coefficient α, and a threshold , find a network G 1 , solution of the following minimization problem.

min G J SFα (G), subject to G 0 G ∆(G 0 , S) < (2.9)
Therefore, ∆(G 0 , S) < is the binary relation translating the similarity we want to preserve. Let us note that unlike the formulation of the general Problem 2.1 the similarity constraint here concerns directly the initial network G 0 and the partition S. Actually, this constraint concerns indirectly the graph G 1 as this one depends only on G 0 and S. This difference is negligible and an equivalent formulation of Problem 2.2 could make appear G 0 and G 1 .

Specific algorithm

Based on the skeleton given in Algorithm 1, we propose here an algorithm providing a suboptimal solution to Problem 2.2. To ensure that two nodes in a same part can not respect the distance , at each step the lower and higher value of the nodes composing a part must be known. Therefore, we associate to the nodes v of the current network G k , the couples (m v , M v ) respectively the minimum and maximum value of the nodes merged in v. This algorithm is obtained by adding a block if..then..else to test the difference between the nodes of the tested edge. for (v, w) ∈ Ω do

5: if |M v -m w | < and |m v -M w | < then 6:
n SF (S v,w ) = J SFα (Merge(G k , S v,w ))

G k+1 = Merge(G k , S best ) 13: k = k + 1 14: end while
Where, the function Merge(G k , S best ) is as follows:

Merge(G, S best ) : Γ n × E k -→ Γ n-1 G, (v, w) -→ G = ( • , V , E ) (2.10)
where

V = (V\{v, w}) ∪ vw E = (E\{v, w}) ∪ {(vw, N out (v) ∪ N out (w))} ∪ {(N in (v) ∪ N in (w)), vw} m vw = min(m v , m w ) M vw = max(M v , M w ) (2.11)
An animation illustrating an execution of Algorithm 2 is available online 3 . In this video, the color of the nodes indicates their value between 0 and 1 and the parameters are fixed as follows = 0.2, n rand = 10 and α SF = 2.3. The convergence of the degree-distribution (plotted in a log-log representation) towards a scale-free distribution appears clearly. However, we can also see that at the very, when the reduced network becomes too small the degree distribution starts to get apart of this objective. A way to explain is to imagine that at the limit the reduced network is reduced to an only node. At this point, the network is not scale-free anymore. Therefore, after passing an optimum the network will get further to a scale-free structure. Figure 2.2 illustrate this evolution of the scale-free cost function.

Property preserving problem

In this section we present a less trivial problem, implying constraints on the dynamics of the network. In order to design an algorithm respecting these constraints we will first present several intermediate results. This problem and its solving represent the main contribution of this chapter. Sections 2.5 and 2.1 will present additional results and simulations about this problem.

Preliminaries

We first present a couple of concepts that will allow us to specify the merge to scale-free problem.

Eigenvector distance

In order to compare the behavior of two networks, we will consider the eigenvector centrality defined hereafter.

Definition 2.4 (Eigenvector centrality)

The vector of eigenvector centrality is a vector, denoted x , associating to each node of the network its relative importance. It is the only vector4 verifying:

x = P x and x 1 = 1 (2.12)
where P is is the adjacency matrix normalized by rows which is:

P i,j = A i,j k A i,k , (2.13)
This centrality can be viewed as the ratio of time spent by a random walker5 on each node of the network. This centrality is also the steady state of the following discrete dynamical equation:

x

(k + 1) = P x(k) x(0) = x 0 (2.14)
for any value of x 0 .

We denote Φ the operator associating a network in with its eigenvector centrality:

Φ : G -→ x , s.t. x = P x and x 1 = 1 (2.15)
Let us note that strong connectivity is a necessary condition for computing the eigenvector centrality and hence to develop the rest of our analysis. Therefore, for now on, we consider, in this section, that the initial network G 0 is strongly connected. Let us note that traffic networks, one of our applications of interest, are always strongly connected (one can picture that it is always possible to reach any point from any point via roads). To compare a network G 0 with a network G 1 issued from the partition S of G 0 based on their eigenvector centrality, we need an operator of projection σ S . The projection corresponds to the sum of the components within each part of the partition. We give here a precise definition: Definition 2.5 (Projection operator) Let x ∈ R n and S a partition of the set {1, .., n}, we define the projection operator σ S as:

σ S : R n -→ R |S| x -→ y : ∀i, y i = j∈S i x j (2.16)
This operator can be written as a matrix operation: σ S (x) = K S x where:

(K S ) i,j = 1 if j ∈ S i 0 else (2.17)
We can compare two networks G 0 and G 1 verifying G 0 S G 1 by looking at the vector ∆ G 0 ,G 1 defined as:

∆ G 0 ,G 1 = Φ(G 1 ) -σ S (Φ(G 0 )) (2.

18)

The i -th entry of ∆ G 0 ,G 1 represents how close the centrality of the nodes i in G 1 is to the sum of the centralities in the subset S i in G 0 . ∆ G 0 ,G 1 will be called eigenvector distance 6between the networks G 0 and G 1 . The eigenvector distance defined by (2.18) quantifies the loss of information through the partitioning regarding the steady-state of the initial network. The network G 1 is aimed to abstract the dynamical behavior of G 0 but the dynamics inside each parts is lost and only the dynamics between the parts is taking into account. Therefore, the eigenvector distance measures how much the deletion of the internal dynamics impacts the estimation of the aggregated eigenvector centrality. Imposing ∆ G 0 ,G 1 to be small implies that the weights of G 1 have to be computed in such a way that the dynamics of G 1 can mimic the dynamics of G 0 without taking into account the internal structure of the parts. We will see in the next section that it is actually always possible to compute the weights of the reduced network in order to cancel out the eigenvector distance. Said otherwise, for any partition of G 0 , the weights of G 1 can be computed such that the eigenvector centrality of each node of G 1 corresponds to the sum of the eigenvector centralities in the corresponding subset of G 0 . The eigenvector centrality is particularly interesting to preserve for some applications. As an example, consider a network where some items (cars, people, goods,...) travel from one node to another following equation (??). By canceling the eigenvector distance, the distribution of the items at the steady-state is preserved: the number of the items in a part of the partition equals the number of items given by the abstracting network. Therefore, the abstracting network can be used to estimate and analyze the aggregated steady state of a large-scale network.

T projection ∆ G 0 ,G 1 = Φ(G 1 ) -σ S (Φ(G 0 )) ∆ G 0 ,G 1 = -0.
G 0 G 1 )
we first compute the eigenvector centrality for each using (2.12). The computation of this centrality depends on the weights assigned on the edges, here we considered that all weights are equal to 1. As the two vectors are not of the same dimension we sum the component of Φ(G 0 ) within each part of the partition. In this way we obtain σ S (Φ(G 0 )) which can be compared with Φ(G 1 ) leading to the vector ∆ G 0 ,G 1 . Here we notice that the reconstruction of the yellow part is good, while the reconstruction of the other part are not.

Mass conservation

In the the problem we treat, we assume that the initial network is a flow network. As seen in the introduction, this means that for each nodes, the amount of weight going in equals the amount of weight going out. We aim to preserve this property through the reduction. The preservation of this property has a strong physical meaning because some networks as electrical networks, water supply networks or generally every network representing transportation are flow networks by their nature. For instance, in electrical network this property corresponds to the famous Kirchoff's circuit law. Thus, by preserving this property we ensure that the reduction method does not violate an intrinsic physical property of the system. We give here a definition of the set of networks having this property:

Ψ f low =    G = (A, V, E), ∀k, i A ik = j A kj    (2.19)
We also call flow matrix an adjacency matrix of a flow network which is a matrix A such that ∀k, i A ik = j A kj .

Total mass

A third property of interest, when considering system implying a flow, is the total mass. The total mass is the sum of all the weights in the network. When these weights have a physical meaning (capacity, resistance,...) it may be useful to preserve their sum. The total mass of a network G will be denoted by G 0 . Equivalently, the sum of all the values of its adjacency matrix A is denoted by A 0 .

Specific problem formulation

In the previous section, we presented three notions allowing us to give specifications to Problem 2.1. Thus, we look for a reduced network that comes out of a partition of the initial network with the following three features: it minimizes the scale-free cost function (2.4), it is a flow network as defined in (2.19), it cancels out the eigenvector distance (2.18) and it preserves the total mass of the initial network. This leads to the following formulation: Problem 2.3 Given a strongly connected initial network G 0 ∈ Ψ f low and a desired scale-free coefficient α, find a network G 1 , solution of the following minimization problem.

min G J SFα (G), subject to G 0 G G ∈ Ψ f low ∆ G 0 ,G = 0 G 0 0 = G 0 (2.20)
Where Ψ f low is given in (2. [START_REF] Anna | Scale-free networks are rare[END_REF]) and 0 is a vector of zeros of the corresponding dimension. To compare with the general formulation (2.1), here the physical property to preserve is the mass conservation Ψ = Ψ f low and the similarity is decomposed in two components:

G 0 ≡ G ⇐⇒ ∆ G 0 ,G = 0 and G 0 0 = G 0 .

Result on the optimization problem

In this section, we present preliminary results on the constraints of Problem 2.3 leading to the design of the specific algorithm. In particular, we will see how the weights of the reduced network can be chosen such that: i) the eigenvector distance is null, ii) the reduced network remains a flow network and iii) the sum of all weights in the network is preserved. These results refers to the hard constraint of the problem.

Canceling eigenvector distance

Here, we are going to see that, with a certain choice of the weights of the reduced network, we can ensure a perfect consistency, in terms of eigenvector centrality, between the two networks.

Theorem 2.1

Let G 0 = (A 0 , V 0 , E 0 ) ∈ Γ n . Let G 1 be the network coming out of the merging S v,w for any edges (v, w) ∈ E 0 . There is a choice of the weights of G 1 such that the eigenvector distance between G 0 and G 1 is null, which is ∆ G 0 ,G 1 = 0. To do so, it is sufficient to take P 1 , the normalized adjacency matrix of G 1 as:

P 1 = F P 0 H , (2.21)
where F, H ∈ R n-1×n are defined by:

F i,j =        1 if i < n -1 and S i = {j} β v if i = n -1 and j = v β w if i = n -1 and j = w 0 else (2.22) H i,j = 1 if j ∈ S i 0 else (2.23)
and

β v = x 0 (v)
x 0 (v)+x 0 (w) , β w =

x 0 (w)

x 0 (v)+x 0 (w) where x 0 is the eigenvector centrality of G 0 .

Proof of Theorem 2.1

In order to prove Theorem 2.1 we have to show three points which are: the matrix P 1 defined in (2.21) i) has a structure compatible with a network coming out of the merging S v,w of the network G 0

ii) is normalized iii) has an eigenvector centrality equal to the projection of the eigenvector centrality of P 0

This three points will be proved one after the other: i) By definition of a network coming out of a partition (see [START_REF] Balthrop | Technological networks and the spread of computer viruses[END_REF]), there is an edge i -→ j in the reduced network if and only if there exists an edge l -→ k in G 0 such that l ∈ S i and k ∈ S j . We want to show that the position of the non-zeros values in P 1 respects this. By definition of P 1 (2.21), we have:

P 1i,j = n k=1 n l=1 F i,l P 0l,k H j,k
and, from the definition (2.23), we know that F i,l = 0 ⇔ l ∈ S i and that H j,k = 0 ⇔ k ∈ S j . Thus:

P 1i,j = k∈S j l∈S i F i,l P 0l,k H j,k
It comes out that:

P 1i,j = 0 ⇐⇒ ∃(l, k) ∈ S i × S j s.t. P 0l,k = 0 (2.24)
Therefore, P 1 is indeed the adjacency matrix of a network coming out the merging S v,w of the network G 0 .

ii) We want to show that the matrix P 1 is normalized in the sense that ∀i ∈ [1, . . . , n -1] we have j P 1i,j = 1. By definition of P 1 (2.21), we have:

n-1 j=1 P 1i,j = n-1 j=1 k∈S j l∈S i F i,l P 0l,k H j,k
We decompose n-1 j=1 P 1i,j in n-2 j=1 P 1i,j + P 1i,n-1 , and so

n-1 j=1 P 1i,j = k∈S n-1 l∈S i F i,l P 0l,k H n-1,k + n-2 j=1 k∈S j l∈S i F i,l P 0l,k H j,k
We recall that a merging S v,w has the following form:

S v,w = { {1} S 1 , . . . , {v -1} S v-1 , {v + 1} Sv , . . . , {w -1} S w-2 , {w + 1} S w-1 , . . . , {n} S n-2
, {v, w}

S n-1 } (2.25)
We note that for all j < n -1, there exists a unique k ∈ S j and so, with the definition of H (2.23), a unique k such that H j,k = 1. Denoting it by k j , we have:

n-1 j=1 P 1i,j = k∈{v,w} l∈S i F i,l P 0l,k + n-2 j=1 l∈S i F i,l P 0l,k j
Moreover, when j covers the set {1, ..., n -2} then k j covers the set {1, .., n}\{v, w} and then:

n-1 j=1 P 1i,j = k∈{v,w} l∈S i F i,l P 0l,k + k∈{1,..,n}\{v,w} l∈S i F i,l P 0l,k
Finally, merging the two parts of the sum, we have:

n-1 j=1 P 1i,j = n k=1 l∈S i F i,l P 0l,k = l∈S i F i,l n k=1 P 0l,k
Yet, P 0 is normalized, so n k=1 P 0l,k = 1. It follows:

n-1 j=1 P 1i,j = l∈S i F i,l
Now, either i < n-1 and, with the definition of F (2.23) we have directly n-1 j=1 P 1i,j = 1, or i = n -1 and then

n-1 j=1 P 1n-1,j = l∈S n-1 F n-1,l n-1 j=1 P 1n-1,j = β v + β w = x 0 (v) x 0 (v) + x 0 (w) + x 0 (w) x 0 (v) + x 0 (w) = 1
Therefore, based on the proof of i) and i)), P 1 is the normalized adjacency matrix of a reduced network G 1 coming out of the merging S v,w of G 0 .

iii) Let x 1 be the eigenvector centrality of G 1 . We want to show that σ(x 0 ) = x 1 . It is sufficient to show that σ(x 0 ) fulfill the definition of the eigenvector centrality of G 1 which are σ(x 0 ) = P 1 σ(x 0 ) and the sum of σ(x 0 ) is 1. By uniqueness of the eigenvector centrality, this will proof iii). Before that, we need some preliminary results: At first, we remark that the definition of H is the same as the definition of K S in (2.17) so we have σ(x) = Hx for all x. Moreover, the matrix product H F has the following form:

H F =                       1 . . . 1 β v β w 1 . . . 1 β v β w 1 . . . 1                       (2.26)
which can also be written as follows:

H F = I n-1 + (β v -1)e n-1 v,v + β v e n-1 w,v + (β w -1)e n-1 w,w + β w e n-1 v,w
where e n i,j is the square matrix of size n whose only non-zero entry is a 1 at the (i, j)th position, and I n is the identity matrix of size n. It follows that ∀i / ∈ {v, w}, (x 0 H F ) i = x 0 (i)

and if i = v, (x 0 H F ) v = x 0 (v)β v + x 0 (w)β v (x 0 H F ) v = (x 0 (v) + x 0 (w)) x 0 (v) x 0 (v) + x 0 (v) = x 0 (v)
and if i = w, (x 0 H F ) w = x 0 (v)β w + x 0 (w)β w (x 0 H F ) w = (x 0 (v) + x 0 (w))

x 0 (w) x 0 (v) + x 0 (v) = x 0 (w)

Hence x 0 = x 0 H F , and then:

x 0 P 0 H = x 0 H F P 0 H
and by definition x 0 P 0 = x 0 and F P 0 H = P 1

x 0 H = x 0 H P 1

Hx 0 = P 1 Hx 0 σ(x 0 ) = P 1 σ(x 0 )
Moreover, it is clear that σ(x 0 ) = x 0 = 1. Thus, σ(x 0 ) fulfill the definition of the eigenvector centrality of G 1 . And by uniqueness of the eigenvector centrality σ(x 0 ) = x 1 . This result concerns only merging, which is a particular partition, but it can be extended to any partition. For simplicity, and since it is sufficient for the following, we have only shown the case of the merging. Note that the preservation of the eigenvector centrality influences only the normalized adjacency matrix of G 1 . Therefore, it remains many degrees of freedom to choose the adjacency matrix and so the weights of G 1 .

Preservation of the mass conservation

The mass conservation property defined in (2. [START_REF] Anna | Scale-free networks are rare[END_REF]) is another physical property that we aim to preserve through the reduction. We see here that if the initial network is a flow network we can ensure that the reduced network is a flow network too.

Theorem 2.2

Let P be a normalized matrix as defined in (2.13) then it exists a diagonal matrix X such that XP is a flow matrix. To do so, it is sufficient to take X as:

X = κ Diag(x ) (2.27)
= where κ = 0 and x is the eigenvector centrality associated with P .

Proof of Theorem 2.2

Let x be the eigenvector centrality of P , which is x P = x and X = κ Diag(x ) for any κ = 0. We have that κx P = κx and consequently 1 XP = 1 X = (X1) = (XP 1) . Thus, the vector whose entries are the sum of the column of XP is equal to the vector which entries are the sum of the row of XP . Hence, XP is a flow matrix.

As the preservation of the mass conservation does not influence the normalized adjacency matrix it is compatible with the canceling of eigenvector distance. Moreover, with κ we still have one degree of freedom to choose the weights of G 1 .

Preservation of total mass

From Theorems 2.1 and 2.2 we have the following corollary: Corollary 2.1 Let G 0 be a network and P 0 its normalized adjacency matrix. Let S be any merging and F and H the merging matrices associated to S. Consider the network G 1 defined by the matrix A 1 as:

A 1 = κ Diag(x 1 )F P 0 H , (2.28)
where x 1 is the eigenvector centrality of P 1 := F P 0 H and κ = 0. Then G 1 is a flow network and ∆ G 0 ,G 1 = 0.

Let us note that the network G 1 is not unique as its adjacency matrix is defined up to a multiplicative constant κ. In the following we fix κ such that the sum of all weights in G 1 is equal to the sum of all weights in G 0 , which is:

κ = |A 0 | 0 | Diag(x 1 )F P 0 H | 0 (2.29)
where | • | 0 is defined as: |A| 0 = i,j A i,j for all matrices A. In this way, the reduced network G 1 is uniquely defined and verifies the constraints of Problem 2.3. Thus given a network G 0 and a merging S, we denote G S 0 , the network coming out the partition of S and fulfilling all the constraints of Problem 2.3. The adjacency matrix of this graph is given by:

A S 0 = |A 0 | 0 | Diag(x 1 )F P 0 H | 0 Diag(x 1 )F P 0 H (2.30)

Reformulation of the optimization problem

The results of this section has shown that for any partition we can choose the weights of the resulting network such that the constraints of Problem (2.3) are respected. Therefore, finding the partition minimizing the scale-free cost function is enough to solve Problem (2.3). Thus, we formulate this new problem:

Problem 2.4
Given G 0 = (A, V, E) ∈ Ψ, find the partition S minimizing the scale-free cost function:

min S J SFα (G S 0 ) (2.31)

Specific algorithm

Based on the result of the Section 2.4.3, a description of the algorithm is presented in Algorithm 3. Therein" the network G k is represented by (A k , E k , V k ). First, we compute the eigenvector centrality x 0 of the initial network (line 1), the normalized adjacency matrix P 0 (line 2) and the coefficient κ (line 3). A random subset Ω of n rand edges is drawn (line 6). For each edge S, we compute the reduced network G S coming from the merging S in G k (line 8) using κ, x k and P k . The scale-free cost function of G S is computed (line 9). Finally, the best edge to merge is chosen (line 11) and the new network is computed (line 12). After recomputing x k as a projection of the previous value (line 13) and P k (line 14), the loop restarts with the new network.

G k+1 = G S best k from (2.

30)

13:

x k+1 = σ S best (x k )

14:

P k+1 from (2.13)

15: k++ 16: end while 2.5 Some results about the algorithm

Algorithm complexity

In this section, we discuss the complexity of the algorithm in terms of number of operations. Several definitions and notations are used to quantify an order of magnitude. Here, we use the notation Θ( • ) defined as follows:

f (x) = Θ(g(x)) ⇐⇒ ∃ c 1 , c 2 > 0, c 1 g(x) < f (x) < c 2 g(x)
(2.32) Proposition 2.1 Consider Algorithm 3 on an initial network G 0 with N nodes, and with n rand the size of the random subset. The algorithm can be divided in two phases:

• An initial phase in which, in particular, the eigenvector centrality is computed. The complexity of this phase is Θ(N 3 ) in the worst case, but can be lowered to Θ(N 2 ) in some cases.

• The reduction phase which consists in at most N iterations having each a complexity of Θ(N n rand )

Overall the worst-case complexity is Θ(N 3 ).

Proof of Proposition ??

For the first phase, the computation of an eigenvector needs Θ(N 3 ) operations. However in [START_REF] Valakevicius | A recursive algorithm for computing steady state probabilities[END_REF], it is shown that if the maximum degree of the network is bounded, the computation can be done in Θ(N 2 ). For the second phase, we know that at each step of the algorithm, the number of nodes decreases by 1 and the total number of iterations can not be larger than N . Then, we consider that the number of steps is Θ(N ). Let C be the total number of operations in each iteration, we have

C = C rand + n rand C Merge + C J SFα + C argmin + C σ
The different functions can be detailed as follows:

• rand consists in picking n rand values, so C rand = Θ(n rand ).

• Merge is the computation of the new network (2.30), which can be computed as a combination of the columns and rows of the previous adjacency matrix, so C Merge = Θ(N ).

• J SFα can be decomposed as follow:

• Compute the degree distribution of the adjacency matrix. The number of operation needed is the number of different degrees in the network. Thus, the number of operations is smaller than N .

• Computation of the scale-free cost function: it is the norm of a difference of two vectors whose sizes are always smaller than N . Thus, the number of operations is also smaller than N .

Finally C J SFα = Θ(N ).

• argmin require Θ(n rand ) operations.

• σ consists in the combination of the coordinates of x k . Hence C σ = Θ(N )

Finally we have:

C = Θ(n rand + n rand (N + N ) + n rand + N ) C = Θ(N n rand )
Thus, the complexity of the second phase is Θ(N 2 n rand ).

This complexity is polynomial with respect to the size of the initial network, whereas the naive way to find a partition of a network by testing all possibilities have an exponential complexity. Even by improving the partitioning algorithm, the complexity is lower-bounded by the complexity of the eigenvector centrality which can not be lowered. However, this algorithm is not supposed to be run in real time, but once to find a reduced network which can then be used as an abstracting model. Thus a relatively high complexity is not crippling for the application.

The complexity of the reduction phase is linear with respect to n rand . Therefore, it is possible to tune this parameter to reduce the computation time. We will investigate in the next section the influence of this parameter on the performance of the algorithm.

Influence of the size of the random subset

In this section, some experiments are presented to emphasize the influence of n rand in Algorithm 3. In particular, we focus on two points:

1. The speed of convergence towards a scale-free network: Through the iterations, the current network gets closer and closer to the scale-free structure. We will wonder to what extent testing more candidates at each iteration improves this convergence.

2. The reproducibility of the the algorithm: As the algorithm implies a random process (the generation of the subset of pair of nodes), even with similar initial conditions, two executions of the algorithm will produce different output. We will wonder if these different output still have similar properties. Beyond the similarity of the properties, we will also wonder if the reduced networks come from similar partitions and so if some areas of the network of the initial network tend to always cluster together.

For these experimentations we will consider a synthetic family of networks: the Manhattan-like grids introduced hereafter

The Manhattan-like grid Manhattan grids, or simply grids, is a family of directed network inspired by the topology of the urban network of Manhattan [START_REF] Stanislawski | The origin and spread of the grid-pattern town[END_REF].

It consists simply of a grid of size N × N in which each of the N 2 intersections is a node. Therefore G = (A, V, E) is a N × N Manhattan grid if:

∀ i, j ∈ [1, . . . , N 2 ], A i,j = A j,i =    1 if i -j = 1 and i ≡ 1 mod n 1 if i -j = N 0 else (2.33)
In our case, in order to get heterogeneous networks we add some random irregularities:

• Nodes are removed with probability β:

∀ v ∈ V, V = V\{v} with probability β (2.34)
• Diagonal shortcuts are created with probability γ

∀ i, j ∈ [1, . . . , N 2 ], s.t. i -j = N + 1 and i ≡ 1 mod n or i -j = N -1 and i ≡ 0 mod n E = E ∪ {(i, j)} with probability γ (2.35)
• Edges are restricted to a unique direction with probability δ ∀ (i, j) ∈ E, E = E\{(i, j)} with probability δ/2 and E = E\{(j, i)} with probability δ/2 (2.36) Such a network is a Manhattan grid with perturbations, hence the name Manhattanlike grid. The weights on the edges are generated randomly while ensuring that the grid is a flow network (see Appendix B). The advantages of this type of network are multiple: i) the degree distribution is far from a scale-free distribution, so it can shows the ability of the algorithm to steer the network towards a scale-free structure, ii) it is easy to build this type of network, even with an arbitrarily large size, making the results presented easily reproducible and iii) it is a good representation of some physical networks [START_REF] Franco Travostino | Grid networks: enabling grids with advanced communication technology[END_REF] such as urban traffic networks or brain networks [START_REF] Van J Wedeen | The geometric structure of the brain fiber pathways[END_REF].

Hereafter an example from this family of network where thick lines represent doubleway edges.

On the convergence of the algorithm

In fig. 2.4 we observe the evolution of the scale-free cost function through the iterations of the algorithm for different values of n rand . When n rand = 1, the edge merged is randomly chosen. That is why it is labeled 'Random edge' in the legend. Let first remark that for every value of n rand the error decreases initially, even in the case n rand = 1, where the edge to merge is randomly selected. This shows that networks (at least this type of grids) naturally tends towards a scale-free structure when edges are iteratively merged. The figure shows that the benefit from increasing n rand is logarithmic. Thus, increasing n rand does not increase substantially the performance while it increases linearly the computation time as seen in Proposition 2.1. In this case, n rand = 10 produces network almost as scale-free as in the exhaustive case while being around 100 times faster (in the exhaustive case, there is about 1000 edges to test).

On the reproducibility of the algorithm

Now we examine, how close the networks obtained via several executions of the algorithm are and how the value of n rand influences this consistency. To answer this question, we have executed Algorithm 3 several times with the same initial network and the same parameters. Then, we compare topological properties of the networks obtained. Precisely, we consider an initial Manhattan-like grid 25 × 25 and we run the algorithm until there is no more merging that increases the scale-freeness. We have executed the algorithm 50 times with n rand = 3, 50 times with n rand = 30 and once with n rand = +∞ which is the exhaustive case (as the output is deterministic one execution is enough). Then, we compute four properties for each output network: number of edges, number of nodes, radius (minimum eccentricity of any node), and scale-free cost function. Let us note that, to have a fair comparison, the radius is divided by the number of nodes in the network. In fig. 2.5 the results are presented in the form of histograms. We remark that the values are arranged around an expected value in an almost bellshaped distribution. When n rand is higher, this Gaussian behavior is more marked with a lower mean deviation is lower and an expected value closer to the case n rand = +∞ (which can be considered as a reference value). Therefore, as expected, a large value of n rand reduces randomness. In addition to the question of the consistency of the properties, we wonder if the partitions obtained from different execution of the algorithm are close. For this purpose, we compare the partitions obtained when n rand = 3 and n rand = 30 with the partition of reference obtained with n rand = +∞. A common way to compare two partitions is to use the normalized mutual information [START_REF] Danon | Comparing community structure identification[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF]. The definition is quickly recalled hereafter. It is rather technical, thus the reader can pursue the reading just knowing that the normalized mutual information gives a value between 0 and 1 on the similarity between two partitions.

The normalized mutual information Let us consider two partitions S = {S 1 , ..., S m } and T = {T 1 , ..., T p } over a network a of size n. The partial distributions of the part S i is P

(S i ) = 1 n |S i |.
It measures the proportion of nodes which are in the part S i . The joint distribution of S i and T j is P (S i , T j ) = 1 n |S i ∩ T j |. It measures the proportion of nodes which are both in S i and T j . The entropy of the partition S is defined as H(S) =i P (S i ) log(P (S i )) and translates how much the set {1, .., n} is fragmented in S: if S = {{1, ..., n}}, then H(S) = -P ({1, ..., n}) log(P ({1, ..., n})) = 0 = -1 × log(1). On contrary if S = {{1}, ..., {n}}, then the entropy is maximal. The joint entropy is defined as H(S, T ) =i,j P (S i , T j ) log(P (S i , T j )) and translates how much the set {1, .., n} is fragmented in the intersection partition

{S 1 ∩ T 1 , S 2 ∩ T 1 , ..., S m ∩ T p }.
Finally, the mutual information is defined as Ĩ(S, T ) = H(S)+H(T )-H(S, T ). In a word, it translates how much the intersection of S and T is more fragmented than S and T are. To calculate the normalized mutual information, we add a normalization factor: I(S, T ) = 2 Ĩ(S,T ) H(S)+H(T ) . Thanks to this tool coming from information theory, we are able to attribute a value I(S, T ) ∈ [0; 1] to measure the similarity between two partitions S and T . In particular, if S = T then I(S, T ) = 1.

a Here, we consider partitions over a network, but the definition remains the same for partitions over any set.

We consider a Manhattan-like grid of size 35×35. To test the consistency of the partitions, we compare each of the 50 partitions obtained with n rand = 3 with the reference partition (obtained when n rand = +∞). We also make the comparison between each of the 50 partitions obtained with n rand = 30 and the reference partition. Figure 2.6 shows the obtained results. Once again, we observe a bell-shaped distribution of the values. We observe that the mean value is closer to 1 when n rand is larger. It means that, as expected, when the random effect is reduced, the partitions obtained are closer to the reference partition. In conclusion, in Sections 2.5.1 and 2.5.2 we have seen that when n rand increases: the run time increases linearly, the scale-free error decreases logarithmically and the variability of the outputs decreases. However, the consistency of the output is not necessarily a property of interest. According to the numerical results, it appears that a relatively small value of the number of edges tested at each step (n rand ≈ 20) is a good balance.

Modification of topological properties

The main effect of the algorithm is to modify the degree distribution of an arbitrary network. However, one can wonder how the other structural properties of the initial network are modified. We would want to compare the properties of the initial and final networks, but the direct comparison could be biased by the difference of their sizes. Therefore, to compare the properties fairly, we generate a small-scale version of the initial network. This network is build the same way as the initial network but with a size similar to the final network. In Table 2.1 we show the structural properties of the initial network, of the small-scale version of the initial network named reference network and the averaged values for 50 networks resulting of the algorithm. The structural properties which are compared are: Number of nodes, number of edges, radius7 , diameter 7 , number of hub (we defined a hub as a node connected with at least 5% of all nodes), clustering coefficient 7 , maximum indegree and mean indegree. The comparison is rather fair since the reduced networks and the reference network have a similar size (number of nodes and edges) and since the initial network and the reference network are consistent (no hubs, same clustering coefficient, same max and mean degree). One can remark that the characteristic distances (radius and diameter) of the reduced network are significantly lower than the reference network, while the clustering coefficient is significantly higher, which are two features commonly observed in scale-free models. The other topological modifications, presence of hubs and higher maximum indegree, is directly explained by the power-law degree distribution of scale-free networks.

Simulation 2.1. In this section, Algorithm 3 is applied to an academic case. We consider an initial large-scale Manhattan-like grid and we apply the reduction algorithm to it. The tuning of the different parameters is presented in Table 2

Conclusion

In this chapter, we have introduced a class of network partitioning problem inducing a scalefree distribution. These problems are formulated as optimization problems: we want to optimize the scale-freeness of the graph under constraints on similarity and properties preservation.

In particular, while treating a particular problem, we have shown that it is possible to optimize the scale-freeness under three constraints: the eigenvector centrality is preserved up to a projection, the total mass remains the same and the mass conservation property is preserved. Then, we define a partition algorithm which takes advantage of these results and allows to find a sub-optimal solution. Experimental results brought some insights on the functioning of the algorithm and strong clues on the choice of a free-parameter of the algorithm. In particular, we show that we can speed up the execution with almost the same efficiency. The multi-level presentation of the problem and the algorithm allows to easily generalize our results to other contexts. Moreover, the algorithm could be used to drive a network towards any desired structure and still verify the similarity constraints. Chapter 4 presents an implementation of this algorithm on a large-scale traffic network taking advantage of the preservation of the properties. In the other, Section 5.2 presents an application in epidemiology taking adavantage of the scale-freeness of the reduced network. Chapter 3

Network partitioning algorithm towards average detectability One of the main concern of the Scale-Freeback project is to develop tools for control and observation of large-scale network. In particular, concerning observability, one question echoed our investigation of network partitioning problems: how to partition a network between measured and unmeasured nodes in order to ensure a good reconstruction of the network state ? Precisely, the recent work of Niazi et al. [START_REF] Umar | Average observability of large-scale network systems[END_REF] proposed the novel notions of average detectability and average observability referring to systems in which it is possible to reconstruct the average state of the unmeasured nodes (respectively in open and close loop). We will focus here on average detectability that we will introduce more precisely later. Through this chapter we present tools to partition a network in order to ensure this property or a relaxed version of it. The last algorithm proposed in this chapter will be applied to network epidemiology in Chapter 5.

Introduction

In network theory, observation problems aim to reconstruct the state of the whole system by knowing only the state of few nodes [START_REF] Felix | Network observability: theory[END_REF]. This topic has been widely studied and has raised the question, among others, of the choice of the measured nodes to improve the reconstruction [START_REF] Gou | An improved measurement placement algorithm for network observability[END_REF][START_REF] Lo Iudice | On node controllability and observability in complex dynamical networks[END_REF][START_REF] Shi Henghua1 | Algorithm research for selecting measurement nodes in measuring network traffic based on adjacency matrix[END_REF]. In observability and controllability theories, most of the approaches aim to reconstruct or to control the whole state of the systems [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF][START_REF] Liu | Controllability of complex networks[END_REF][START_REF] Notarstefano | Controllability and observability of grid graphs via reduction and symmetries[END_REF][START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF]. To solve the problem in large-scale networks two issues emerge: the complexity of the computation and the limited number of sensors (and/or their price). Taking this into account, it is often difficult to reconstruct the exact state of a large-scale network. Yet, in many instances, there is no need to reconstruct the state of each node, but only an aggregation of these states. For example, in a large-scale traffic network, the number of measurements and the computational effort required to reconstruct the density of vehicles in each street would be disproportionate since the knowledge of the average density in different areas is quite enough for traffic management purposes. Recently, Niazi et al. [START_REF] Umar | Average observability of large-scale network systems[END_REF] took advantage of this observation and proposed the notions of average observability and average detectability. These notions refer to the capacity to reconstruct the average state of the unmeasured nodes respectively in closed-loop and in open-loop. Precisely, in an average detectable system, it is possible to design an observer estimating the average of the unmeasured nodes such that the error converges to zero. In this chapter, we focus on this latter notion. In [START_REF] Umar | Average observability of large-scale network systems[END_REF] the authors propose a sufficient condition for average detectability allowing to test if a given network and a given subset of measured nodes form an average detectable system. To go further, if it is possible to choose the placement of the measured nodes, a question emerges: given a network what is the smallest subset of nodes to measure in order to fulfill the average detectability condition ? Said otherwise, what is the smallest subset of nodes to measure in order to be able to reconstruct the average of the unmeasured nodes ? This is the question we address throughout this chapter. In order to transform the condition for average detectability into a structural condition, we will restrict ourselves to a particular type of system: negative uniform network. We will show that with such systems, if the subgraph of unmeasured nodes forms a regular network1 , then the system is average detectable. Therefore, our problem becomes detecting the largest regular induced subgraph (RIS) out of a given network. The question of finding induced subgraphs with particular properties has been addressed in several works. We can cite the maximum clique problem [START_REF] Immanuel | The maximum clique problem[END_REF] which has implications, in particular, in social networks; frequent subtree mining [START_REF] Chi | Frequent subtree mining-an overview[END_REF] which is applied to data analysis; induced subgraph isomorphism problem [START_REF] Maciej | The subgraph isomorphism problem for outerplanar graphs[END_REF] or its variant as snake-in-the-box problem or the maximum independent set problem. In most cases, these problems are either oriented to data analysis or are graph problems with no direct application. To our knowledge, the present work is the first to use an induced subgraph problem for a reconstruction concern. The problem posed here -the detection of regular induced subgraph-has been studied in different contexts and we will propose a brief review of the works in this domain in Section 3.2. However we will see that the detection of regular induced subgraph to reach average detectability raises some difficulties. Therefore, in Section 3.3, we relax the problem by introducing the notion of quasi-regularity, which qualifies a network which is close to be regular. We derive then a result linking the error of regularity and the error of reconstruction: the more regular is the unmeasured subgraph , the better is the reconstruction. On these grounds, we treat the problem of quasi-regular induced subgraph detection (qRIS). Finally, we also extend the approach to multiple quasi-regular induced subgraph (mqRIS) which allows to estimate averages of several subsets of nodes. The main contributions of this chapter are:

• The emphasis of link between the reconstruction of the average and the regularity of the unmeasured nodes.

• The design of algorithms identifying the nodes to measure such that the average of the unmeasured nodes can be efficiently estimated.

The chapter is organized as follows: after some preliminaries, Section 3.2 presents the exact problem of reconstruction and the algorithm associated and Section 3.3 presents the relaxed problem, the extension to the multiple subgraphs case and the algorithms associated to both problems.

Preliminaries

In this chapter we associate to the network a dynamical equation as introduced in the introduction:

Σ : ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t) (3.1)
where A is the weighted adjacency matrix of the network, x(t) = [ x 1 (t), . . . , x n (t) ] T is the state vector associating a value to each nodes of the network and u(t) = [ u 1 (t), . . . , u p (t) ] T is the input vector. We will consider that the output vector y contains a sample of k components of the state vector x. This means that y = [ x 1 (t), . . . , x k (t) ] T and so C = I k 0 . The nodes V 1 := {v 1 , . . . , v k } are called the measured nodes while V 2 := {v k+1 , . . . , v n } are the unmeasured nodes. We denote m the number of unmeasured nodes: m = n -k. We also denote x 2 (t) = [ x k+1 (t), . . . , x n (t) ] T , the state of unmeasured nodes and x av 2 the average value of the unmeasured nodes:

x av 2 = 1 m 1 T x 2 (3.2)
Correspondingly, we decompose the matrices A and B as follows:

A = A 11 A 12 A 21 A 22 , B = B 1 B 2 . ( 3

.3)

With A 11 ∈ R k×k , A 22 ∈ R m×m and all the other block matrices of corresponding dimensions. We denote by σ the deviation vector defined as:

σ = x 2 -1x av 2 =      x k+1 -x av 2 x k+2 -x av 2 . . . x n -x av 2      (3.4)
This vector contains the difference between the value of each unmeasured nodes and the average value of the unmeasured nodes. We have 1 T σ ≡ 0. The evolution of x av 2 is described by the following equation:

ẋav 2 = αx av 2 + gy(t) + bu(t) + ησ(t) (3.5) with α = 1 m 1 T A 22 1, g = 1 m 1 T A 21 , b = 1 m 1 T B 2 and η = 1 m 1 T A 22 .

Let xav

2 be an open-loop observer for x av 2 described as:

ẋav 2 = αx av 2 + gy(t) + bu(t) (3.6)
We will see in the next section the condition on the system to ensure that the observer xav 2 converges to x av 2 .

Regular Induced Subgraph (RIS) detection for exact average detectability

In this section, we explore the problem of network partition between measured and unmeasured nodes to ensure the average detectability property that we will precisely define. We will see that under hypothesis, this partitioning problem can be solved by detecting a regular induced subgraph. We will see then how to detect such subgraphs. Finally, we will enlighten some limitations of this approach leading to the relaxed problem presented in the next section.

Average detectable system

Definition 3.1 (Average Detectability: AD) A system Σ as defined in (3.1), with a subset V 1 of measured nodes is said to be average detectable if zero output and zero input implies that the average value of V 2 converges to zero:

∀ x av 2 (0) ∈ R m , ∃ T ∈ R, ∀ t > T, y(t) = 0 m , u(t) = 0 p =⇒ lim t→∞ x av 2 (t) = 0 (3.7)
where 0 n is a vector of zeros of length n.

This means that, in an average detectable system, if nothing goes in or comes out the unmeasured subgraph then the average value of the unmeasured nodes will vanish: No internal

Regular Induced Subgraph (RIS) detection for exact average detectability 87

dynamics can live only within the unmeasured subgraph. The average detectability of system Σ is in fact equivalent [START_REF] Umar | Average observability of large-scale network systems[END_REF] to the convergence of this observer

Σ AD ⇐⇒ lim t→∞ |x av 2 (t) -x av 2 (t)| = 0 (3.8)
where xav 2 is the estimator defined in (3.6). We exhibit hereafter a sufficient condition for average detectability. In order to introduce the condition for average detectability we first define a network-based notion.

Definition 3.2 (Outflow balanced network)

Let G be a directed weighted network represented by its adjacency matrix A. G is said to be outflow balanced2 if the sum of the weights of the outgoing edges is the same for every nodes, which is :

∃ γ ∈ R, 1 T A = γ1 T (3.9)
Moreover, if γ < 0, then the network is said to be negatively outflow balanced.

Example 3.1 illustrates this property.

Example 3.1. Consider the network G represented in the figure hereafter. Its adjacency matrix A is as follows:

A =     0 0 -2 -5 -5 0 -3 0 0 -1 0 0 0 -4 0 0     (3.10)
We verify that 1 T A = -5 × 1 T . Hence the network G is negatively outflow balanced.

v 1 v 2 v 3 v 4 -5 -1 -4 - 2 -3 -5
We can now give the condition for average detectability.

Proposition 3.1 (Sufficient condition for average detectability -Theorem 3 in [START_REF] Umar | Average observability of large-scale network systems[END_REF]) Consider a system Σ associated to the network G and denote by G V 2 the subgraph of G induced by the subset of unmeasured nodes. The system Σ is average detectable if G V 2 is negatively outflow balanced.

v 1 v 2 v 3 v 4 v 5 -3 -1 -1 1 1 -3 -4 2 -2
Figure 3.1: By measuring the node v 2 , the unmeasured nodes V 2 = {v 1 , v 3 , v 4 , v 5 } induces a negatively outflow balanced G V 2 with γ = -2. Thus, the system is average detectable. This result implies that, if the set of nodes can be partitioned into two subsets such that one induced subgraph is negatively outflow balanced, then measuring the nodes outside this subgraph makes the system average detectable. Figure 3.1 gives an example of such a system.

Regular Induced Subgraph detection

Motivated by Proposition 3.1, we shall consider the following problem.

Problem 3.1 (Negatively outflow balanced induced subgraph detection)

In a given network, find the largest induced subgraph which is negatively outflow balanced.

Based on Proposition 3.1, by measuring the nodes outside the subgraph found the system is average detectable. However, in an arbitrary network with independent weights there is, almost surely, no outflow balanced subgraph. That being said, two solutions can be considered: either we restrict ourselves to particular systems for which we know that negatively outflow balanced subgraphs can be found, or we relax the notion of average detectability and hence the notion of regularity. The latter solution will be explored in Section 3.3 where we introduce the notion of quasi-regularity. In the remainder of this section, we focus on the first solution: we treat the problem for a particular type of systems: the negative uniform networks defined hereafter.

Definition 3.3 (Negative uniform network: NUN)

A network G, represented by the adjacency matrix A, is said to be negative uniform if all its non-zero weights are equal and negative, which is

∀ i, j, A ij ∈ {a; 0} (3.11)
with a < 0.

Given this definition, the following fact is immediate Proposition 3.2 (Sufficient condition for average detectability of negative uniform network) Let Σ be a system associated to a negative uniform network G. Then, Σ is average detectable if G V 2 is regular.

Proof of Proposition 3.2

In a negative uniform network we remark that

1 T A = a × deg out (G), (3.12)
Therefore, with (3.9) and (3.12), a negative uniform network is negatively outflow balanced if there exists γ < 0:

a × deg out (G) = γ1 T deg out (G) = γ a 1 T
This mean that all the outdegree of G must be the same, which is G has to be regular.

Finally we have that finding a regular induced subgraph in a negative uniform network implies average detectability which is equivalent to the convergence of the estimator:

RIS & NUN =⇒ AD ⇐⇒ xav 2 (t) -x av 2 (t) -→ t→∞ 0 (3.13)
Remark 3.1. Although negative uniform network is a quite restrictive case, we can also consider positive uniform network with a same negative self-loop η. Indeed in this case, we have 1 T A = a × deg out (A) -η1, and even with a > 0 the right side can be negative if the self-loop η is large enough. Proposition 3.2 remains true if the system is associated with such a network. This type of networks includes for example some heat systems with high dissipation [START_REF] Sakhraoui Imane | Discrete Linear Functional Observer for the Thermal Estimation in Power Modules[END_REF]. The model of epidemic used in the application in Chapter 5 falls also in this scope. In the rest of the section, we only consider negative uniform network for the simplicity of the development.

We can now formulate the problem arising from Problem 3.1 restricted to the negative uniform networks case.

Problem 3.2 (Regular induced subgraph detection)

Let G be a negative uniform network. We look for the largest regular induced subgraph (RIS) of G, which is:

max I⊂V |I|, s.t. G I is regular. (3.14)
where G I is the subgraph of G induced by the subset of nodes I.

Based on Proposition 3.2, by measuring the nodes outside the subgraph solution of Problem 3.2, we obtain an average detectable system. Figure 3.2 illustrates this approach. Solving Problem 3.2 can benefit from the extended literature on the k-regular induced subgraph (or k-RIS) problem, which differs from Problem 3.2 in fixing the desired degree k. The works in this domain can be classified as follows:

• Complexity of the k-RIS problem: A first work [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] showed that the problem in the case k = 0 is NP-hard. Then several works [4,[START_REF] Domingos M Cardoso | Maximum k-regular induced subgraphs[END_REF] generalize the result for any k and different type of networks. Some studies [START_REF] Kobler | Finding Maximum Induced Matchings in Subclasses of Claw-Free andP 5-Free Graphs, and in Graphs with Matching and Induced Matchingof Equal Maximum Size[END_REF][START_REF] Vadim | Maximum regular induced subgraphs in 2P3-free graphs[END_REF] exhibit a polynomial complexity for some particular types of network.

• Algorithms to detect the largest k-RIS: Despite the complexity of the problem, some algorithms have been proposed to solve it. In the case k = 0, [START_REF] Fedor | Measure and conquer: a simple O(20.288n) independent set algorithm[END_REF][START_REF] Michael | Algorithms for maximum independent sets[END_REF] propose fastexponential algorithms (which is in O(c n ) with c ≤ 2). For any k, a fast-exponential algorithm based on a branch-and-bound approach is proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF] and a polynomial algorithm for a particular type of networks in [START_REF] Agra | The k-regular induced subgraph problem[END_REF]. However these results consider undirected network and standard regularity (not out-regularity as us). Still, the branchand-bound approach proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF] can be extended to our case and will be presented later.

• Upper-bound on the size of the largest k-RIS: Facing the complexity of the problem it is interesting to obtain an upper bound on the size of the optimal solution. An intuitive upper bound on the size of the largest k-RIS is the size of the k-Core of the network. The k-Core is a subgraph obtained by removing iteratively nodes with a degree smaller than k. More elaborate upper bounds have been proposed for any k [START_REF] Domingos M Cardoso | Maximum k-regular induced subgraphs[END_REF][START_REF] Luz | Improving an upper bound on the size of k-regular induced subgraphs[END_REF] or for particular values of k [START_REF] Lovász | On the Shannon capacity of a graph[END_REF][START_REF] Luz | An upper bound on the independence number of a graph computable in polynomial-time[END_REF]. As above, these results are valid only for undirected network and, from our knowledge, only the k-Core approach can be extended to our case.

• Approximating algorithm to find a sub-optimal solution: While it would be interesting to find an approximate solution of our problem, it is shown that this problem is hard to approximate [START_REF] Asahiro | Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems[END_REF].

These insights will be the basis for our approach to RIS, which we elaborate next.

An algorithm for the RIS problem

As discussed in the previous section, the literature proposes only methods to find the largest k-regular induced subgraph but nothing to solve the problem for every k. A simple approach consists in solving the problem for each k and then keeping the best solution: We denote RIS(G) and k-RIS(G) respectively, the largest regular and k-regular induced subgraphs of G.

We have then:

| RIS(G)| = max k∈N | k-RIS(G)| (3.15)
Some tricks can be used to optimize the approach:

• As seen in the previous section, there are some methods allowing to find an upper bound on the size of k-RIS(G). We denote this upper bound by θ k (G). While testing the value of k-RIS(G) for every k, if θ k 0 (G) is smaller than the largest k-RIS(G) so far, it is useless to compute k 0 -RIS(G). Noticing that the computation of this upper bound is faster by far than the computation of the k-RIS(G), this helps to compute the regular induced subgraph.

• The cases with k = 0 and k = 1 are particular: they are known as the maximum independent set and the maximum matching. Specific algorithm can be applied for these case.

• Using an approximate algorithm for the k-RIS would imply a sub-optimal solution for the RIS which can be interesting if the approximation is good.

Based on these remarks, we propose Algorithm 4 to detect the largest regular induced subgraph within a given network.

Algorithm 4 Regular induced subgraph detection

Input: G 1: RIS = [] 2: for k = 0 : max(deg out (G)) do 3: θ k = UpperBound_k-RIS(k, G) 4: if θ k > | RIS | then 5: k-RIS = Find_k-RIS(k, G ) 6:
RIS = max(RIS, k-RIS)

7:
end if 8: end for Output: RIS This is actually a meta-algorithm as we gave here only the skeleton of the method and not the sub-algorithms UpperBound_k-RIS and Find_k-RIS. The choice of these sub-algorithm is discussed hereafter.

Remark 3.2. The sub-algorithms Find_k-RIS(k, G) and UpperBound_k-RIS(k, G) can be different algorithms for the particular cases k = 0 and k = 1. However, for directed networks, it seems that there is no specific algorithms providing a clear benefit.

Sub-algorithm for the upper bound

We first discuss the implementation of the UpperBound_k-RIS(k, G) algorithm. This algorithm is detailed in Algorithm 5 and is based on the computation of the k-Core. As said before, the k-Core of a network is the subgraph obtained after removing repetitively the nodes with a degree smaller than k. It is clear that

k-RIS(G) ⊂ k-Core(G) (3.16)
and so, the size of the k-Core is an upper bound on the size of k-RIS.

Regular Induced Subgraph (RIS) detection for exact average detectability 93

Algorithm 5 k-Core Input: G, k 1: I ← Nodes in G with outdegree < k 2: while I is not empty do 3:

Remove I from G

4:

I ← Nodes in G with outdegree < k 5: end while 6: θ k ← number of nodes in G Output: θ k an upper bound on the size of the k-RIS

Sub-algorithm to find the k-RIS

The implementation of the second sub-algorithm Find_k-RIS(k, G) is described in Algorithm 6. It is an extension of the branch-and-bound approach proposed in [START_REF] Gupta | Fast exponential algorithms for maximum r-regular induced subgraph problems[END_REF]. It is a recursive algorithm designed as follows: Given a network G and a degree k, we first compute the k-Core of G (line 1). If the network obtained is k-regular then the k-RIS is found (line 3) and the algorithm terminates. Otherwise there is at least one node, denoted r, with a degree larger than k (line 5). It is clear that either r is not in the k-RIS either (at least) one of its successors3 is not (line 6). Thus, we consider the subgraphs obtained by removing r or a successor of r (line 8). Finally we compute the k-RIS for each of them (line 9) and select the largest one (line 11).

Algorithm 6 k-RIS Input: G, k 1: G ← k-Core(G, k) 2: if G is k-regular then 3: k-RIS ← G 4: else 5:
r ← a node of G with degree > k 6:

I ← N out (r) ∪ r 7: for i ∈ I do 8: G tmp ← remove i in G 9: k-RIS tmp {i} = k-RIS(G tmp , k) 10: end for 11: k-RIS = max(k-RIS tmp ) 12: end if Output: k-RIS Remark 3.3.
It is possible to use a technical trick to speed-up the algorithm. The size of the current best solution can be stored and passed to the recursive call to k-RIS (line 9). If the size of the current subgraph is smaller than the size of the best solution, the recursion stops. This shortcut is not in algorithm 6 for the sake of readability. [START_REF] Norman | The mathematical theory of infectious diseases and its applications[END_REF]. Considering that the network is negative uniform, the system is average detectable by measuring the 8 nodes outside of the red subgraph.

Discussions

The method proposed above suffers some limitations which we summarize below:

• Negative uniform systems, which motivate our search for RIS, are rare: It seems that there is no practical example in the literature. Even if we consider positive uniform systems with large negative self-loop, as mentioned in Remark 3.1, the applications are scarce.

• RIS is a fragile notion: For example, a grid network which is very close to regular (only the nodes on the border have a smaller degree) does not fulfill the condition of the theorem. Moreover, the largest RIS in a network is generally relatively small.

• The RIS problem is hard to solve: there is no specific method for the RIS problem and the k-RIS problem has to be solved several times. Moreover, as said before, the k-RIS problem is a NP-hard problem and there is no good approximation algorithm to solve it.

• The largest RIS in a network is often very small, and suboptimal heuristics return even smaller subgraphs.

Based on these statements, the RIS detection approach introduced in this section is difficult to apply to real-world problems. We will see that it is possible to accept some errors on the regularity will preserving the possibility to reconstruct efficiently the average. We introduce, in the next section, the notion of quasi-regularity leadong to more flexibility.

Approximate average detectability

Link between error of regularity and error of reconstruction

In Proposition 3.1, the sufficient condition for average detectability was 1 T A 22 = γ1 T with γ < 0. To relax the problem we consider now that this equality is no more exactly verified and we introduce a perturbation vector s defined as:

γ = argmin γ ∈R 1 T A 22 -γ 1 T , s = 1 T A 22 -γ1 T (3.17)
and a regularity error defined as:

= s 1 m|γ| (3.18)
We denote xav 2 := x av 2 -xav 2 the reconstruction error. The following proposition gives the link between the regularity error the reconstruction error, defined as:

e ss = lim sup t→∞ |x av 2 | (3.19)

Proposition 3.3 (Relation between regularity error and reconstruction error)

Assume that

1 m 1 T A 22 1 < 0 (3.20)
Then, the reconstruction and regularity errors satisfiy

e ss ≤ max i σi 1 - , (3.21)
where σ = lim sup t→∞ |σ(t)|.

Proof of Proposition 3.3

From equations (3.5) and (3.6) we have then:

ẋav 2 (t) = αx av 2 (t) + ησ(t) (3.22)
where σ defined in ( 3.4) is the deviation from average,

α = 1 m 1 T A 22 1 = 1 m (γ1 T + s T )1 = γ + 1 m s T 1 (3.23) aand since 1 T σ(t) = 0, ησ(t) = 1 m 1 T A 22 σ(t) = 1 m (γ1 T + s T )σ(t) = 1 m s T σ(t) (3.24)
Therefore, (3.22) becomes

ẋav 2 (t) = (γ + 1 m s T 1)x av 2 (t) + 1 m s T σ(t) (3.25)
which is a stable dynamics by virtue of (3.20). Since A is stable, σ(t) is bounded in magnitude and

lim sup t→∞ xav 2 (t) ≤ - 1 m |s T σ| γ + 1 m s T 1 (3.26)
Finally,

- 1 m |s T σ| γ + 1 m s T 1 = |s T σ| m|γ| -s T 1 ≤ |s T σ| m|γ| -|s T 1| ≤ s 1 max i σi m|γ| -s 1 (3.27)
and (3.21) follows from with the definiton of in (3.18) The constant σ depends on the physical system of interest and corresponds to the maximal difference between the state of an unmeasured node and the average state of the unmeasured nodes. According to Proposition 3.3, in order to minimize the reconstruction error, it is interesting to find a subgraph having a reasonable regularity error . Relation (3.21) is emphasized through simulations in the following section.

Remark 3.4. The reconstruction error e ss grows with the regularity error which means that the reconstruction will be better if the subgraph of unmeasured nodes is large, close to be regular and with a large degree of regularity.

Before investigating the qRIS detection problem, we present some simulations enlightening the relation described in Proposition 3.3. To this end, we first introduce a family of networks for which we can control the regularity.

Definition 3.4 (p-reg network)

Given a network G, we denote N out (i) = {j, (j, i) ∈ E}, the set of successors of i. A network is said p-reg if it verifies:

|N out (i)| = 1 if i is odd |N out (i)| = p if i is even (3.28)
Graphs of this family have the particularity to have one half of their nodes with outdegree 1 and the other half with outdegree p. In particular if p = 1, the network is 1-regular (it is a cycle). By increasing the value of p, the regularity worsens as shown in fig. 3.4. In the following numerical simulations, we consider a series of networks composed of a p-reg network and one additional measured node as in fig. 3.5. Therefore, with such network, by tuning the value of p we can modify the regularity of G V 2 while preserving the shape of the system. The network used in the experiment contains 101 nodes (100 nodes in the p-reg network plus one extra node to measure). We add some random inputs to the system and we compare the error e ss for different value of p. The results are displayed in fig. 3.6. We notice that as predicted by The error of reconstruction is then computed as the bias between the signal and the reconstruction at t = 1000 (which is a good approximation of e ss ). This emphasizes the link between the regularity of a subgraph and the ability to reconstruct its average. Proposition 3.3 the error of reconstruction grows with the error of regularity. This simulation enlightens the fact that by minimizing the error of regularity we can control the error of reconstruction e ss .

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9

Quasi-Regular Induced Subgraph detection

While detecting quasi-regular subgraph, if a small error is imposed on the regularity, the subgraph found might be small (and so the number of nodes to measure would be high). In the other hand, Proposition 3.3 ensures that the reconstruction would be better. Consequently, a compromise between the number of measure and the quality of the reconstruction has to be found. An interesting way to implement this compromise is by fixing a threshold for the error of regularity and then find the largest subgraph whose regularity error is lower than this threshold. This leads to the qRIS detection problem defined hereafter.

Problem 3.3 (Quasi-regular induced subgraph detection)

Let G be a network and 0 > 0 a threshold for the quasi-regularity. We look for the largest quasi-regular subgraph of G, which is:

max I⊂V |I|, s.t. (G I ) < 0 (3.29)
where (G) is the regularity error associated to G as defined in (3.18).

Therefore, by measuring the nodes outside the subgraph solution of Problem 3.3 we can reconstruct the average value of the subgraph with an error of the order of σ 0 1-0 . Note that this problem may have no feasible solution if 0 is chosen to be too small. After this caveat, we present a beam search algorithm providing a sub-optimal solution to Problem 3.3.

An algorithm for qRIS detection

Like in the RIS case, a combinatorial algorithm exploring every possible subgraph would find the exact solution but it is uncomputable in practice even for networks with a relatively small size. We present here a beam-search algorithm providing a sub-optimal solution to Problem 3.3.

Principle of beam search algorithms

The principle of beam-search algorithms is as follows: A set of candidate solutions is considered as a seed. Then, a set of solution deriving from these candidates is considered and the β most promising are memorized (β is called the beam width) and form the new set of candidates. The algorithm stops when a candidate is satisfying enough or when the new candidates are no more satisfying. In this latter case, the final solution is chosen among all the previous candidates.

For the quasi-RIS detection the algorithm is described in Algorithm 7: We initialize the set of candidates with the singletons of each node (line 1). Then we iterate while one of the candidate has a regularity error smaller than the minimum accepted 0 (line 2) (see Remark 3.5 for a discussion on this point). At each iteration, new candidates are derived from the current candidates (line 4-5). These new candidates J c are all the subsets composed by one current candidate c and any other nodes S i of the network. Finally all these new candidates are united (line 7), the β best form the new candidates (line 8) and the best one is stored as quasi-RIS (line 9). By repeating this operation several times, the size of the candidates grows until none of the candidate have a regularity error small enough. At the end, the candidate with the smallest regularity error is chosen. Figure 3.7 illustrates this algorithm. Beam-search algorithms, like this one, are a type of greedy algorithm and hence do not provide an optimal solution. However the computations are relatively fast and the solutions found are rather good, as we will see.

Remark 3.5. In Algorithm 7 the while loop will stop if none of the candidate have a regularity Here the beam width β = 2, so at each step the best two candidates are kept (solid line). Two small modifications are brought to make the example more readable: the seed is a single candidate while in the algorithm the seed is composed of the singletons of each node; the new candidates are the subsets composed of a previous candidate and a node neighboring this candidate, while the latter node can be arbitrary chosen in the algorithm.

Algorithm 7 quasi-RIS detection

Input: G: network with n nodes, 0 maximum acceptable error, β beam width Ω ← c J c 8:

Cand ← β smallest (G c ) for c ∈ Ω 9:
quasi-RIS ← smallest (G c ) for c ∈ Ω 10: end while Output: quasi-RIS error small enough. However, this condition is relatively strict as it is possible that it is not verified at some iteration but it will be verified in the future. Thus, a relaxed condition would be to stop if the the condition is disrespected several iterations in a row. Then, the solution would be chosen among the last candidate verifying the condition.

Remark 3.6. The new candidates are chosen in a way that may induce a disconnected subgraph. This allows to explore more potential solutions. However, as discussed in Chapter 1, for some applications the connectedness of the unobserved subgraph may be required or wished. For example when the network has a geographical nature (as urban traffic network or electrical grid), it is interesting to estimate the average of a geographical area. In this case, the algorithm can be adapted by changing line 4 with S ← N in (c) ∪ N out (c). Simulation 3.2. For this simulation, we designed a network including a particularly regular subgraph to emphasize the ability of the algorithm to detect it. In this simulation the parameters are 0 = 0.1 and β = 300 which means that at each step we conserve the 300 best candidates. The subgraph obtained is presented in fig. 3.8(a). We compute then the reconstruction of the average in this subgraph. Figure 3.8(b) shows the actual average and the estimation made by measuring the nodes outside the subgraph.

We have seen how to detect a regular or quasi-regular subgraph in order to estimate their average. We propose, in the next section, to generalize this approach, to detect several subgraphs and estimate different averages.

Extension to Multiple quasi-Regular Induced Subgraphs (mqRIS)

In the previous problems we tried to find one regular or quasi-regular subgraph in order to estimate its average. We wonder, now, to which extent it is possible to detect several regular or quasi-regular subgraphs and estimate their respective average. Considering the limitations posed by the regularity case evoked in Section 3.2.4, we focus only on the quasiregular problem. However a similar generalization can be led for the regularity case. In the RIS and qRIS problems we wanted to have the minimum number of nodes to measure leading to the minimization problems 3.2 and 3.3. Here again we have the same objective to minimize the number of measured nodes. Thus, we want to find disjoint quasi-regular induced subgraphs G I 1 , . . . , G Im maximizing the cardinality of the union of the subgraphs. Moreover, these subgraphs can not share any successors which is nodes outside the subgraph and pointed by a node of the subgraph. This is because the successors of a subgraph are measured to estimate the average value of the subgraph. If a node is pointed by two nodes belonging to two different subgraphs, the condition for the reconstruction does not hold (see [START_REF] Umar | Average observability of large-scale network systems[END_REF]). We denote I = [I 1 , . . . , I m ] the set of the subsets of nodes. The problem tackled in this section is formulated as follows: Problem 3.4 (Multi quasi-regular induced subgraph detection) Let G be a network and 0 > 0 a threshold for quasi-regularity. We look for a set I of quasi-regular subsets minimizing the number of nodes to measure, which is:

max I=[I 1 ,...,Im] I j , s.t. ∀ i, (G I i ) < 0 ∀ i, j, (I i ∪ N out (I i )) ∩ (I j ∪ N out (I j )) = ∅ (3.30)
The second constraint translates the non-overlapping of the subgraphs and their successors. The quasi-RIS detection algorithm 7 presented in the previous section can be extended almost straightforwardly to the multiple subgraphs case as follows: a first quasi-regular subgraph is detected, the subgraph and its neighborhood (which are the nodes to measure) are removed from the network and the process is repeated with the new network. To limit the number of nodes to measure it is interesting to limit the number of neighbors of the subgraph selected at each iteration. To this end, the new candidate at each iteration are the subgraphs maximizing |I|/|N out (I)| which is the ratio between the size of the subgraph and the size of its neighborhood instead of the subgraph minimizing (G I ) in Algorithm 7.

The algorithm for multi quasi-RIS detection is described in Algorithm 8 where quasi-RIS refers to the algorithm 7 where "smallest (G c )" in lines ( 8) ans ( 9) is replaced by

argmax c∈Ω, (Gc)< 0 |c| |N out (c)| (3.31) Simulation 3.3.
We propose here a simulation of Algorithm 8 for the mqRIS detection. To this end, we consider an initial network (fig. 3.9) designed with five zones more regular than the average. This aims to test the capacity of the algorithm to detect regular subgraphs. The result of the simulation is displayed in fig. 3.10. In this case, the quasi-RIS detection algorithm is applied five times before no more satisfying subgraphs can be found. At each step, we can see that the subgraph and its out-neighborhood found at the previous step is removed and the algorithm is applied with the new network obtained. The algorithms aims to find these zones. These zones are not easily identifiable at the naked eyes and the reader is invited to try it before looking at the result of the algorithm.

Conclusion

Based on the novel notion of average detectability, we proposed here three algorithms identifying measured node placement in order to estimate the average of the unmeasured subgraph. Considering a particular type of system, the first algorithm finds regular induced subgraph to reach exact average detectability which is the estimation of the average is asymptotically unbiased. Due to the limitation of this first problem, we proposed a relaxation: we focused on the detection of quasi-regular induced subgraph which results in an estimation of the average with a bias which depends on the quasi-regularity. The second algorithm achieves this task. The third algorithm allows to detect several quasi-regular induced subgraphs to estimate the averages of different subsets of the system. In Chapter 5 we will apply the third algorithm to estimate the evolution of a disease spreading in an interaction network over French territory. (e) The fourth subgraph found and its successors are removed and the algorithm is applied again to detect a fifth subgraph (in blue). The algorithm stops here as there is no other subgraph which are enough regular.

(f) The network obtained when merging the subgraphs obtained at each steps. By measuring the remaining nodes, the average of the subgraphs detected can be estimated. Chapter 4

Application to traffic

The question of whether machines can think is about as relevant as the question of whether submarines can swim Edsger Djikstra This chapter is dedicated to present a concrete implementation of the partitioning algorithm introduced in Chapter 2. We consider here the urban traffic network of Grenoble that we will present in a first section. Then, a partition of this algorithm is obtained thanks to the MergeToScaleFree algorithm. Finally, due to the properties preserved by the algorithm, the reduced network is used to simulate the dynamics of the initial system. studied and is a part of the GTL-ville experimentation2 (following the GTL experimentation started in 2009 [START_REF] Canudas-De | Grenoble traffic lab: An experimental platform for advanced traffic monitoring and forecasting[END_REF]). As large networks are hard to control, we wonder how an abstracted version of the network could help to design a control strategy and how the scale-freeness of this abstracting network can be an advantage. It is in this framework that the study of the reduction of the urban traffic of Grenoble takes place. The network, provided by TomTom, is a representation of the city center of Grenoble as it contains all roads and intersections within an area of about 5 km per 5 km. Figure 4.2 represents the area considered within the Grenoble Metropolis. In this network, the nodes correspond to the roads and there exists an edge between two nodes n i and n j if there is an intersection linking road n i to road n j . The weight on the edges is an estimation of the flow of vehicles going from one road to another in average. The computation of this estimation is explained hereafter.The network possesses 13099 nodes and 31570 edges.

Traffic network of Grenoble

Estimation of the flow

In the light of the properties preserved by the MergeToScale-Free algorithm, and in particular the eigenvector centrality, one of the objective of this reduction could be to estimate the distribution of vehicle in the city at the steady state. To this end, the weights assigned to each edge of the network represents the average flow of vehicle going from one road to another. To estimate this flow we consider two different pieces of information: the number of lanes and the speed limit of the downstream road. Indeed, the more important (in terms of flow) a road Figure 4.2: The traffic network of Grenoble metropolis and in red the city center that we will consider here. is, the higher is its speed limit and the larger is the road. Based on this assumption the weight w ij from road n i to road n j is computed as follows:

w ij = l j v max j (4.1)
where l j is the number of lanes in road j and v max j is the speed limit on road j. These data are provided by TomTom. However, with this computation, nothing ensures that the network is a flow network3 . To ensure this we project the network into the flow network space. This computation is explained in Appendix B. Figure 4.3 illustrates the network model.

Physical properties of traffic networks

In a traffic network, if the weights represent the average flow of cars from a street to another, the flow coming in one node is equal to the flow coming out the node 4 . Therefore, the mass conservation is an intrinsic property of the system, and the preservation of this property through the reduction is essential to ensure the physical consistency. The cancellation of the eigenvector distance ensures that the dynamics of the initial network and the abstracting network are consistent. In particular, the number of vehicles in each zone of the network at the steady state will be the same in the two systems. The preservation of the total sum of all weights guarantees that the number of vehicles is the same in the initial and the reduced networks. Therefore, Algorithm 3, which ensures the preservation of these three properties, is particularly relevant for traffic network. In the next section we present the results obtained with the algorithm and we compare the dynamics of the two networks.

Reduction of the Grenoble traffic network

Within this section, we apply the method presented in Chapter 2 in order to obtain a scale-free network abstracting the Grenoble traffic network and preserving a certain consistency. We will see then, how this reduced network can be used to simulate the dynamics of the system compared to the initial network.

The reduced system

We apply the reduction Algorithm 3 on this network and we impose a scale-freeness on the indegree distribution. The choice of the different parameters of the algorithm is presented in Table 4.1. As a reminder, |G| is the number of nodes in the initial network, α SF is the imposed scale-free coefficient for indegree, n rand is the number of edges tested at each iteration and n iter gives the number of iterations. Hence, the number of nodes in the reduced network is 2099 which correspond to a reduction of 83.9%. The ability of the algorithm to get close to the desired distribution is clear as the reduced network exhibits a power law degree distribution. Few hubs are visible on the reduced network. However, as seen in Chapter 2, when the reduced network becomes too small it tends to loose its scale-free structure. Therefore, a compromise must be found between the scale-freeness of the reduced network and its smallness.

Simulations on the reduced network

Model

We will now see that the reduced network can be used to analyze the dynamics of the system. We consider a linear time-invariant discrete-time system:

Σ : x(k + 1) = P x(k) + Bφ in (k) (4.2)
where x represents the number of vehicles in each road, P is the normalized adjacency matrix issued from the adjacency matrix A as defined in (2.13), B points the road having an in-flow, and φ in represents the dynamics of the inflows. The computation of the adjacency matrix A in order to estimate the real flows and to ensure the mass conservation property has been explained in the previous section and in Appendix B. In this model, the distribution of vehicle at time k + 1 is given by the state at time k and the matrix P describing the transitions from one road to another. Therefore, the time from a vehicle to go from one node to another does not depend on the length of the street, which is a drawback of the model. However, we can roughly estimate that this time is, in average, around thirty seconds. Therefore in the simulation, we consider that the time past between two states is thirty seconds.

Let us note that a linear system like this one is not realistic for traffic system where a lot of nonlinear phenomena occur. However, in the case of free-flow (which is without any congestion on the roads) a linear system is acceptable. The results obtained in Chapter 2 state that the algorithm preserves the steady-state in the reduced system if the evolution equation is:

ẋ(t) = P x(t) (4.3)
This equation does not include any input. This is why, in the scenario we will consider, the in-flows stop after a while (φ in (t) = 0, t > T ) to show that after that the distributions converges towards each other. The advantage of considering some in-flows at the beginning of the simulation is to emphasize the capacity of the abstracting system to emulate the dynamics of the initial system even in the range where we do not have theoretical results.

Scenario

We consider that, at t = 0, there is no car inside the network which is x(0) = 0. This can be seen as an ideal case of the network during the night, where there is almost no traffic. Then, in the morning, at t > 0, some cars enter into the network. The entry points of the network, pointed by matrix B, are the roads at the border of the network5 . As shown in fig. 4.6, we divide the entry points in three categories: the ones from the north (in blue), the ones from the east (in red) and the ones from the south (in yellow). The west border remains unexcited. Different dynamics govern the inflow in these different entry points. After a while, when t = 400 (which corresponds to more than 3 hours) the in-flows are stopped and we observe the evolution of the vehicles distribution converging towards an equilibrium.

Simulations

Figure 4.7 shows the results of the simulation after 2000 time steps 6 . The color displayed here represents the relative density at each node. Precisely the color of nodes v i at time t is proportional to:

c i (t) = x i (t) max j x j (t) (4.4)
and the color on the edges corresponds to the average color of its two extremities.

This simulation enlightens the capacity of the abstracting network to mimic the dynamical behavior of the initial network and in particular its equilibrium point. We note however that the nodes of the reduced network do not necessarily correspond to sensitive zones of the initial network that we would want to watch over. As an example, the large road crossing the north of Grenoble from west to east (more or less red in the initial network) is not well captured by the reduced system. That being said, one could add a constraint or an additional cost function to the problem in order to force the partition to capture these tactical points of the traffic network. The simulation on the reduced network is about 5 times faster. Therefore, using the abstracting network to estimate the traffic condition in real-time or to compare different strategies of traffic control offers a good performance both with regard to the run-time and the accuracy.

Application to network epidemiology

First, the terror. And then a moment of hunger. This is how the sense of taste disappears from our world. They don't even have time to give the disease a name. The theoretical development of Chapters 2 and 3 appears rather academic and disconnected from real-world problems. Within this chapter, we consider the study of diseases spreading over a population to present two applications of these results. In the first section, some preliminaries about network epidemiology are given which allow to introduce the models used in the applications. Section 5.2 present a cure-allocation strategy using a scale-free abstraction as presented in Chapter 2. This work has been presented at the NecSys conference 2018 conference in Groningen and published in [START_REF] Martin | MergeToCure: a New Strategy to Allocate Cure in an Epidemic over a Grid-like network Using a Scale-Free Abstraction[END_REF]. Finally, Section 5.3 uses the result of Chapter 3 to reconstruct from few measurements an aggregated state of the evolution of an epidemic.

Susan, Perfect Sense

Introduction to network epidemiology

Overview of the models

History of network epidemiology

The mathematical modeling of epidemic spreading aims to evaluate the progression of an epidemic through a population and to design tools to control the propagation. The first work using mathematics to understand disease is due to Daniel Bernouilli in 1760 [START_REF] Bernoulli | Essai d'une nouvelle analyse de la mortalité causée par la petite vérole, et des avantages de l'inoculation pour la prévenir[END_REF] when he aimed to study the reliability of the smallpox inoculation 1 . This work is considered as the first attempt of mathematical modeling of life and as a precursor of biomathematics. However it was not until 1897 that a first model of disease spreading was proposed by Ronald Ross in his study of malaria [START_REF] Ross | On some peculiar pigmented cells found in two mosquitos fed on malarial blood[END_REF]. He obtained results on the processus of evolution of the epidemic and promoted the study of this new field. In particular, Gray McKendrick encouraged by Ross published from 1927 together with William Kermack three articles [kermack1927contributions] introducing a new class of models: the compartmental models. In these class of models, the population is divided into compartments having the same characteristics and the evolution of the size of the compartments is described. As we will see, the most common compartments used are Susceptible (S), Infected (I) and Recovered (R) leading, among others, to the two models: SIS and SIR. All along the twentieth century, works in this field increased and focused, in particular, on this compartmental models. A more complete review of the history and the models of mathematical epidemiology can be found in [START_REF] Diekmann | Mathematical tools for understanding infectious disease dynamics[END_REF]. At the same time, the second part of the twentieth century saw the appearance of the network theory explaining a wide range of natural phenomenon. Limited until then by the hypothesis of homogeneity of the population, compartmental models benefited in the early 2000s from the development of network theory. Indeed, networks allowed to take into account the interactions among the population. This leads to the network epidemiology models that we will use in the two applications presented in this chapter. A review of the use of networks in epidemiology can be found in [START_REF] Nowzari | Analysis and control of epidemics: A survey of spreading processes on complex networks[END_REF].

Compartmental models

In 1927, the groundbreaking theory of Kermack-McKendrick [START_REF] Ogilvy | A contribution to the mathematical theory of epidemics[END_REF] introduced the notion of compartments in epidemiology. Their model divides the population into three compartments: Susceptible (S): healthy individuals who can be infected Infected (I): individuals suffering the disease Recovered (R): individual immunized to the disease who can not be infected anymore 1 also called variolation, it is somehow the ancestor of the smallpox vaccine.

A susceptible individual can pass into the infected compartment if he gets the disease and then in the recovered state if he is cured. Thus the evolution of a patient follows this scheme S -→ I -→ R. The proportion of the population represented by each compartment n S , n I and n R (such that n S + n I + n R = 1) is governed by a differential equation which depends on the parameters of the disease. Thus, in the Kermack-McKendrick model the evolution of individuals does not take into account their neighborhood and is restricted to the evolution of their compartment. Yet, one can imagine that an individual which is in contact with a lot of people is more vulnerable to the disease than an isolated individual, which can play a role in the spreading of the epidemic. With the introduction of networks into compartment models, the evolution of the individuals depends also on the state of their neighborhood. Thus, for example, a susceptible individual will be more likely to be infected if he is surrounded by infected individuals. Figure 5.1 illustrates the difference between this two types of models.

Originally, the compartmental models included only the three compartments mentioned above. The models which use these compartments are commonly referred as SIR models. After that, ither compartments have been introduced, for example:

Exposed: individuals infected but not yet infectious

Carrier: individuals not suffering the disease but who can infect other Quarantine: individuals infected but put in quarantine so they can not infect others Considering these additional compartments allows to refine the accuracy of the model and is sometimes necessary to model certain epidemics. On the contrary, another commonly used model, the SIS model, considers only the Susceptible and Infected compartments. This model, used in the two applications presented in this chapter, is described in the next section.

The SIS model

Classical model

As the name suggests, in the SIS model, a susceptible individual can pass into the infected compartment if he gets the disease and then comes back in the susceptible compartment if he is cured as illustrated in fig. 5.2. It differs from the SIR model in the state of the cured individual: in the SIS model a cured individual can be infected again, while in the SIR model a cured individual can not be infected again. This model is particularly relevant for some infections, as common cold or influenza, for which there is no immunization upon recovery. The transition from one compartment to the other is governed by two values: the infection rate β and the recovery rate δ (with 0 ≤ β, δ ≤ 1).

We denote X i (k) the state of individual i at time k: X i (k) = 0 means that the individual i is susceptible and X i (k) = 1 means that the individual i is infected. The exact equation of

if X i (k) = 0, X i (k + 1) = 1 with probability β 1 |N in (i)| j∈N in (i) X j (k) if X i (k) = 1, X i (k + 1) = 0 with probability δ (5.1)
This can be read as follows: if an individual is susceptible at time k, the probability that he gets infected at time k + 1 is the proportion of infected people within its neighbors scaled where X(k) is the average value of the vector X at time k. This formulation of the prevalence has been chosen empirically to efficiently capture the prevalence observed. Let us note that the prevalence only depends on the structure of the network G and the spreading rate λ = β δ , but not on the initial subset of infected nodes (as long as this subset is non-empty) [START_REF] Pastor | Immunization of complex networks[END_REF]. We will write the prevalence as ρ(G, λ). For the first application, in Section 5.2, we will consider Model (5.1) which is commonly used in network epidemiology [START_REF] Dezső | Halting viruses in scale-free networks[END_REF][START_REF] Pastor | Epidemic spreading in scalefree networks[END_REF]. For the second application, in Section 5.3, we consider a slightly different version described in the next section.

Linearized mean-field approximation

We consider here a mean-field approximation of the SIS model introduced in [START_REF] Van Mieghem | The N-intertwined SIS epidemic network model[END_REF]. In this case, the nodes of the network do not represent individuals but groups of people. The nodes are not in a fixed state S or I but have a proportion p of people infected. The dynamics of p is then: ṗ(t) = (AB -δI)p(t) -P ABp(t), p(0) = p 0 (5.3) where p = [p 1 , . . . , p n ] are the proportions of infected people in each group (and P = diag(p 1 , . . . , p n )), I is the identity matrix, B = βI and p 0 is the initial proportion of infected people in each group. In order to use the approach developed in Chapter 3, we consider a linearization around zero [START_REF] Nowzari | Analysis and control of epidemics: A survey of spreading processes on complex networks[END_REF] of (5.3):

ṗ(t) = (AB -δI) A p(t), p(0) = p 0 (5.4)
In order to include sources of infection that are external to the population, we define a matrix B ∈ {0; 1} n×b to identify nodes that are in contact with sources of infection, and the function u(t) ∈ R b to represent the temporal evolution of these sources of infection. By including these inputs u, the dynamics becomes ṗ(t) = Ap(t) + Bu(t), p(0) = p 0 (5.5) This leads to the matrices with the following form:

A =            -δ β 0 β 0 0 0 0 -δ 0 0 β β 0 β 0 -δ 0 0 0 0 β 0 β -δ 0 β 0 0 0 0 0 -δ 0 β 0 0 0 β β -δ 0 0 0 0 0 0 β -δ            and B =            1 0 1 0 0 0 1            (5.6)
These matrices correspond to the system illustrated in fig. 5.3. System (5.5) falls in the scope of positively uniform system with a large negative self-loop as discussed in Remark 3.1. Therefore, the Multiple Quasi-Regular Induced Subgraph detection can be applied.

Remark 5.1. Although we use in this article the terminology of epidemics, let us note that these models are also used in other contexts such as: spreading of computer viruses over web networks [START_REF] Balthrop | Technological networks and the spread of computer viruses[END_REF] or information spreading over social networks [START_REF] Leskovec | Patterns of cascading behavior in large blog graphs[END_REF].

5.2 MergeToCure, scale-free abstraction for cure allocation strategy

Introduction

In network epidemiology, a common problem is to choose individuals to cure in order to reduce the spreading. As cured individuals can not be infected or infect other individuals they can be considered as removed from the network. Therefore, if the number of cures is limited, identifying individuals which removal will reduce the most the spreading is an interesting problem known as cure allocation2 . Intuitively, the best choice is to remove nodes such that the network becomes less connected and so the epidemic can not spread easily. However, finding the best nodes to remove in order to decrease the connectedness of the network is a NP-complete problem [START_REF] Van Mieghem | Decreasing the spectral radius of a graph by link removals[END_REF]. Therefore, several papers propose heuristics to approximately solve this problem. Essentially it is proposed to remove the most important nodes: [START_REF] Holme | Attack vulnerability of complex networks[END_REF] proposes to remove the nodes with the highest betweenness centrality and [START_REF] Joel | Effective vaccination strategies for realistic social networks[END_REF] the nodes with the highest PageRank [88]3 . In [START_REF] Dezső | Halting viruses in scale-free networks[END_REF], the problem is addressed in the context of scale-free networks.

As discussed in Appendix 0.3.4, it is shown that for this type of networks allocating cures to the most connected nodes reduces efficiently the spreading. This strategy will be called here the hub-removal strategy. In homogeneous networks such as Manhattan-like grids, the absence of hubs reduces the efficiency of this strategy. In [START_REF] Rhodes | Epidemic thresholds and vaccination in a lattice model of disease spread[END_REF] the question of allocating cure in a grid network is addressed. However, in this work the proposed strategy requires to know the location of the seed4 of the epidemic, which is unrealistic.

The main contributions of this section is the introduction of a strategy to allocate cure in Manhattan-like grids. This strategy uses a scale-free network abstracting the initial Manhattan-like grid. We show numerically that this strategy is better than other strategies for a large range of the parameters.

Allocating cures in scale-free networks Appendix 0.3.4 presents cure-allocation strategy in scale-free networks. Let us introduce some additionnal results. It is known [START_REF] Roy M Anderson | Infectious diseases of humans: dynamics and control[END_REF] that in a grid or a random network there exists an epidemic threshold λ c under which the prevalence is always zero:

∀λ < λ c , ρ(G hom , λ) = 0 (5.7)
where G hom is any homogeneous network (grid or random).

At the contrary, in scale-free network there is no such epidemic threshold [START_REF] Dezső | Halting viruses in scale-free networks[END_REF]. Thus, if a population forms a scale-free network, even a minor infection will always persist. However, as discussed in Appendix 0.3.4 removing the hubs in a scale-free network allows to reduce drastically the epidemic. In particular, [START_REF] Dezső | Halting viruses in scale-free networks[END_REF] shows that it is possible to restore such an epidemic threshold by removing the biggest hubs, and this threshold can even be made larger than in a homogeneous network by removing enough hubs. Precisely, if we consider a scale-free network build with the Barabási-Albert model, we have:

λ c = k 0 -m k 0 m ln -1 k 0 m (5.8)
where m is the number of edges added at each step in the Barabási-Albert model5 and k 0 is the degree above which every node is removed.

However this strategy is not efficient if the degree distribution of the network is homogeneous. Similarly, the strategies recommending to remove nodes with the highest PageRank or the highest betweenness centrality lose their interest in a network where all the nodes are more or less similar. Therefore, in the next section we address the following problem: how to find an efficient strategy of cure allocation for homogeneous networks ? To this end, we present an approach inspired by the hub-removal strategy: by finding a scale-free abstraction of a homogeneous network we can highlight some zone-hubs which are more interesting to cure. To find this scale-free abstraction we use the algorithm MergeToScaleFree, presented in Chapter 2.

The strategy Merge To Cure

Description of the strategy

The idea of the strategy is to identify zones which play the role of hubs in the network by using the algorithm MergeToScaleFree, and then to focus on curing these zones.

The strategy can be detailed as follows:

1. Extract a scale-free abstraction out of the original homogeneous network.

2. Identify the hubs in the scale-free abstraction, corresponding to zones-hubs in the initial network.

3. Assign a cure to the nodes at the border of the zone-hubs.

The interest of the hub removal is to cut the main routes of infection. Then, in the case of zones-hubs, it is sufficient to only remove the border of these zones. Figure 5.4 gives an illustration of the strategy.

Remark 5.2. An interesting link can be made with the so-called meta-population models. In these models, introduced in [5], nodes do not represent individuals but groups such as cities.

In our case, if the initial network is a network of individuals, our strategy consists in finding how to regroup these individuals at a coarser scale and this way extract a meta-population model out of the initial model. As the meta-population network is designed to be scale-free we just have to identify the most connected groups of individuals to cure and therefore reduce the spreading of the epidemic.

Experimental results

In this section, we present the experimental setup to validate our strategy. Through this section we consider Manhattan-like grids as defined in 2.5.2. To test the efficiency of our method we consider a Manhattan-like grid G and we numerically compute its prevalence using (5.1). Then we remove nodes according to different strategies:

1. MergeToCure. We denote n cure the number of nodes removed.

2. By curing randomly n cure nodes 3. By curing the n cure nodes with the highest degree: hub-removal strategy.

4. By curing the n cure nodes with the highest betweenness centrality.

5. By curing the n cure nodes with the highest PageRank.

Then the prevalence is computed for the networks obtained with each of these strategies. The prevalences are compared with the null case where no cure is allocated in the network. For each strategy σ we compute the benefit B σ as:

B σ (n cure , λ) = ρ(G, λ) -ρ(G σ , λ) ρ(G, λ) (5.9)
where G σ is the network obtained with the strategy σ. This benefit measures how much the strategy σ reduce the initial prevalence of the network. Thus, the higher is B σ the better is the strategy σ.

In the simulation presented in fig. 5.5, a tenth of the population is initially infected. In the

Initial network

Scale-free abstraction

Remove hubs

Remove nodes at the border of zone-hubs We observe that the MergeToCure strategy has a larger benefit than all other strategies when λ 1 and n cure 25%. For a large proportion of removed nodes (larger than 30% of the population) the hub strategy becomes more efficient than the MergeToCure strategy. We suggest then, that, in a Manhattan-like grid, the MergeToCure strategy is the most efficient to reduce the prevalence for parameters: (λ, n cure ) ∈ [1; +∞) × (0, 0.3N ], where N is the number of nodes in the network. This means that our strategy is the best when the infection is particularly virulent and the number of available cure is very limited. To get an idea of the value of λ for real diseases, [START_REF] Td Eames | Modeling dynamic and network heterogeneities in the spread of sexually transmitted diseases[END_REF], for example, estimates this value for sexually transmissible diseases between [0.76, 1.52]. In order to improve the efficiency of the MergeToCure strategy we also wonder how to choose the scale-free coefficient in the MergeToScalefree algorithm. Thus, we consider the benefit B(n cure , λ, α SF ) with 25% of node reduced and varying λ and α SF . Figure 5.6 shows the results. The benefit tends to be higher for high value of α SF , which is when the hubs are fewer but more connected.

Average detectability of an epidemic spreading

In this section we apply the mqRIS algorithm presented in Section ?? to a real-world case: the spreading of a disease over an interaction network of the main cities in France. By reconstructing the average state of different subgraphs, we aim to estimate the evolution of the proportion of infected people in different areas.

The estimation problem

It is clear how important it is to estimate the evolution of a disease, for instance in order to take appropriate sanitary measures or to study the efficiency of a treatment (fig. 5.7). As it is very costly to determine the state of each individual, one needs methods to reconstruct the spreading of the epidemic per areas and with relatively few measurements. We propose here to use our approach to estimate the evolution of the proportion of infected people in different areas, by measuring the state of few groups. In order to construct a concrete example, we shall consider the above linearized SIS dynamics over a contact network beween the main French cities.

Topology of the network

We consider a network of interactions between groups of individuals in the main cities of France. The network is structured at two different scales: one level within the cities and one level between the cities. It is known that at the level of a city, individuals are strongly interconnected and tend to form clusters [START_REF] Boguná | Models of social networks based on social distance attachment[END_REF][START_REF] Toivonen | A model for social networks[END_REF]. Here we use the Watts-Strogatz model [START_REF] Duncan | Collective dynamics of small-world networks[END_REF] which is known to well capture the features of social networks. At the level of the country,

Simulations

Figure 5.9 presents the partition found with Algorithm ??. The network has been divided in 11 subgraphs containing 1112 nodes in total. Thus, only 292 nodes remains to measure which represents only 20.80% of the nodes. Some parts fit cities while others include a whole region. The figure gives also the regularity error , the number of nodes |V| and the mean degree k for each subgraph.

Next, since we have the partition in which each induced subgraph is quasi-regular it is possible to estimate the value of the average inside each subgraph. The parameters of the model are fixed as follows: β = 0.05 and δ = 0.98. We randomly add 323 sources of infection randomly distributed in the territory. To be close to the reality we use as initial conditions the situation presented in fig. 5.7 which is available on www.sentiweb.fr. ). The solid lines are the actual averages while the dotted lines are the estimated averages. Figure 5.11 shows the evolution of the absolute error for each subgraph. We observe that, as expected, the estimation errors decrease quickly and remain relatively small. However, as we did not find exact regular subgraphs, the system is not detectable and the errors do not converge to zero.

Conclusion

In this chapter we applied two methods developed throughout this thesis to network epidemiology: the MergeToScaleFree algorithm and the Multiple Quasi-Regular Induced Subgraph detection.

In the first application, we explored the problem of allocating a limited number of cure in a network in order to reduce the spreading of an epidemic. It is known that in scale-free networks an efficient strategy consists in curing the hubs. Thus, thanks to the MergeToScaleFree algorithm presented in Chapter 2, we derived a scale-free abstracting network to identify some zone-hubs in a homogeneous network. We showed numerically that this strategy is better than all other strategies when the epidemic is particularly violent and the number of vaccine is very restricted.

In the second section, we explored the problem of estimating the evolution of an epidemic over a population with few measures. As shown in Chapter 3, it is possible to estimate the average of unmeasured nodes if the subgraphs which they form are close to regular. Based on this observation, we use the algorithm developed in Chapter 3 to identify such quasi-regular subgraphs. We identify thus the individuals to diagnose in order to know the average state of the unmeasured communities in the population.

Conclusion

All models are wrong, but some are useful

Georges Box

In this conclusion we will first draw up a list of the contributions presented throughout the thesis. Based on the limitations of these contributions we will present some possible extensions and opened questions that this thesis sparked.

Review of the contributions

Through this thesis we have raised and investigated several questions concerning network partitioning algorithms. We first wondered how a partitioning can be done regarding to the connectedness of the parts. Precisely, we estimated the loss due to the connectedness constraint. Following this theoretical question, we proposed two problems of network partitioning and we exhibited algorithms bringing solutions to these problems. In the first problem, we wanted the reduced network to have a scale-free structure while preserving somehow the characteristics of the initial network. In the second problem, we aimed to partition the network with a reconstruction purpose: we separated the measured nodes and the unmeasured nodes such that the average of the unmeasured nodes can be efficiently estimated. Following this three first chapters presenting theoretical results, we proposed applications divided into two chapters corresponding to the field of application: traffic and epidemiology. A detailed review of the contributions per chapter is given hereafter:

The price of connectedness: For any problem of optimal network partitioning, one may consider that the part have to be connected or not. Depending on the application, this constraint of connectedness may be necessary or only desirable. Therefore, a question emerges: how much this constraint of connectedness will damage the quality of the optimization. This damaging is what we call the price of connectedness and we aimed to estimate its value throughout the chapter. We first emphasized the link between this price of connectedness with another quantity: the ratio of connectedness which is the ratio between the number of connected partitions and the total number of partitions of a given network. We proposed then a tight upper bound on the ratio of connectedness which is the ratio between the number of partitions without isolated nodes and the total number of partitions. Finally, we exhibit an exact formula for this value and we show that it is indeed a good upper bound for the ratio of connectedness.

Network partitioning algorithm towards scale-free structure: In the introduction we have exhibited clues on the potential interest of a scale-free abstracting network. Thus, this chapter was dedicated to the elaboration of a partitioning algorithm inducing a scalefree reduced network. We first introduced a general framework composed of a class of partitioning problems inducing scale-free networks and a meta-algorithm to solve such problems. We treated then two problems corresponding to this class of problem. The first problem had more a didactic purpose whereas the second one required an important mathematical development. Indeed, in this second problem, we want to preserve three properties through the partition: the eigenvector centrality6 of the system up to a projection, the mass conservation7 and the total mass 8 . We show then how to recompute the weights of the reduced network such that these properties are preserved for the particular type of partition used in the algorithm. Finally, we proposed some results on the algorithm and a simulation. Note that the framework developed in this chapter is reused in the first application to epidemic which take advantage of the scale-freeness of the reduced network.

Network partitioning algorithm towards average detectability: Noticing that it is often useless and difficult to reconstruct exactly each state of a large-scale network, it seems relevant to reconstruct only an aggregated state. Yet, precisely, the recently introduced notion average detectability refers to systems in which it is possible to reconstruct the average state of the unobserved nodes (in open loop). In this chapter, we proposed a method to determine which nodes have to be measured in order to make the system average detectable. Precisely, we show that for a certain type of systems, the regularity of the unmeasured subgraph implies the average detectability of the system. We reuse then the existing literature on regular subgraph detection to build an algorithm inducing average detectable system. As the hypothesis on the initial system were restrictive and the results quite poor, we relaxed the strict notion of average detectability to allow errors in the regularity of the unmeasured subgraph. We show that, in this case, the error of reconstruction, is upper bounded by a function of the error of regularity. Therefore, we proposed an algorithm detecting quasi-regular subgraph. Finally, we generalized the method to consider several different subgraphs for which we estimate separately the average. This approach is reused in the last chapter to estimate the evolution of an epidemic.

Application to traffic: The second algorithm developed in Chapter 2 is particularly interesting for traffic network. Thus, we applied this algorithm to the traffic network of the city-center of Grenoble. First, we introduced the model considered: the geographical network and the estimation of the traffic flow. Then, a scale-free network abstracting this network is obtained through the algorithm. Finally, we simulate a scenario over the two networks and show that the reduced network can efficiently be used to analyze the evolution of the traffic conditions.

Application to network epidemiology: The last chapter is divided into two different ap-plications using the same models of network epidemiology. Therefore, in a first part, we introduced network epidemiology theory and the different models used. Then the two applications are presented:

MergeToCure, scale-free abstraction for cure allocation strategy We proposed in this section a strategy for cure allocation 9 for networks with a homogeneous degree distribution: we partition the initial network and we use the scale-free abstraction to identify some zone-hubs. Then, the individual at the border of theses zone are cured. We numerically compared this method with others cure-allocation strategies, using a SIS model. We showed that our method is the most efficient to reduce the propagation of the disease when the number of cure is very limited and when the epidemics is particularly virulent.

Average detectability of an epidemic spreading: When considering the spreading of a disease, it is not possible to know precisely the state of each individual. In this section, we applied the method proposed in Chapter 3 to determine the individuals which state have to be measured in order to reconstruct an aggregation of the states. By measuring few nodes, one can estimate the average state in different parts of the population. This approach has been applied on a large-scale network that we have generated: an interaction network over the french territory.

Possible extensions

The results presented in this thesis are at some point limited by the hypothesis or the models considered. However, since these limitations are not locked doors but opportunities to extend our work, we will highlight some questions raised and potential future work for each chapter:

The price of connectedness: The formula (1.23) for the upper bound on the ratio of connectedness is a recursive formula and can not be used for large value of the parameters. Thus, it could be very useful, and surely feasible, to rewrite this formula in another way making it more easily computable. While the tightness of the upper bound has been enlightened through simulations, this work would benefit from a theoretical result quantifying somehow this tightness and/or showing that the two quantities converge towards each other. Finally, if the estimation of the ratio of connectedness is a quite solid result, the link with the price of connectedness is weaker. A better understanding of the link between these two quantities, possibly regarding to the partitioning problem considered, would enhance this work.

Network partitioning algorithm towards scale-free structure: The framework developed is quite efficient to obtain a reduced network with a scale-free structure. However, we can wonder if the scale-free cost function proposed is relevant. Maybe a cost-function focusing more on the right part of the distribution could be better if only the distribution of hubs matter. The framework proposed includes a large variety of problems. An investigation could be lead to understand in which contexts and to what extent the scale-freeness of the reduced network can be used, and the constraints that have to be added to the problem in each cases.

As discussed in the chapter, the computation of the weights satisfying the constraints can be generalized to any partition (and not only merging). Therefore, an efficient way to find the best partition inducing a scale-free network would be more efficient than looking iteratively for the best merging.

Network partitioning algorithm towards average detectability: Several limitations for the strict case (RIS) have been presented within the chapter leading to the relaxed case (qRIS and mqRIS). These limitations was not only about the solutions but also about the problem itself so that we do not expect any extension for the RIS case. In contrast, for the relaxed problem, it seems that the link between the error of regularity and the error of reconstruction could be better understood. Indeed, the relation that we proposed includes a constant of the system making it less quantifiable. Throughout the chapter, we proposed to identify the nodes to measure in order to reach average detectability. A same approach could be used with the notion of average observability also introduced in [START_REF] Umar | Average observability of large-scale network systems[END_REF], or in order to identify nodes to control to steer the average state as proposed in [START_REF] Nikitin | Boundary Control for Output Regulation in Scale-Free Positive Networks[END_REF].

Application to traffic: The model used for traffic is quite unrealistic as it considers a linear dynamic. While the theoretical results are valid only for such a linear dynamic, one can wonder if the estimations made by the reduced network are still relevant with a more realistic traffic model implying non-linearity.

The value of the flow on the network are estimated from partial data on the roads. With real flow information the simulation would be more interesting. In the frame of the ERC Scale-Freeback project, the collect of traffic data is precisely one of the objectives and will be integrated to the GTL-ville platform 10 . Finally, one can wonder to what extent the scale-freeness of the reduced network is useful in the context of traffic modeling. It seems that a first answer could be brought by the boundary control theory as shown in [START_REF] Nikitin | Boundary Control for Output Regulation in Scale-Free Positive Networks[END_REF], where the use of scale-free network is favored.

Application to network epidemiology: As for the application to traffic, the application here suffers from the limitation of the models. In this case, one of the main limitation of the network model of epidemiology is that it is impossible to know with precision the exact interconnection within a population. Therefore, it could be interesting to investigate, how the results of this section can be generalized to other models. More precisely for each of the application:

MergeToCure, scale-free abstraction for cure allocation strategy In this sec-tion, we proposed a cure assignation strategy for networks with a homogeneous degree distribution. However, one can wonder if some interaction networks (or computer networks) are actually homogeneous. At least [START_REF] Liljeros | The web of human sexual contacts[END_REF] shows that for sexual transmitting diseases, transmission networks have a scale-free structure.

As said before, the misunderstood of the exact structure of the network prevents from identifying the zone-hubs and, even more, the individuals at the border of these zones. However, one could investigate, how to identify individuals who probably play this role with partial information on the network, and how much this inaccuracy would impact the efficiency of the strategy. Finally, it is obvious that choosing the individuals to cure implies some ethical issues. Most of the time, the resources allow to cure every individuals without distinction, making this question only academic. However, in some cases, such as for computer network, this strategy may be applicable.

Average detectability of an epidemic spreading: Above the limitations due to the model, the fact that the subgraphs detected do not necessarily correspond to city or small area may be an inconvenient. However, a simple way to prevent this issue would be to add a cost function in the algorithm penalizing the subgraphs scattered. Moreover, this work would be more relevant if it would have been compared to other estimation methods specially with regard to the number of measurement, the quality of the reconstruction, and the running time of the algorithm.

Hopefully, the possible extensions presented in this section may reach someone and the work presented throughout this thesis will be carried a little bit further until it reaches any practical usage. At least, all this work will benefit to myself. In a minor part, for all the knowledge I discovered through these years. And in a major part, for all the personal skills I had to develop to achieve such a piece of work. Resilience being probably the most important of them.

We present here the algorithms used to solve problems (1.4) and (1.7). A deep description of the algorithm would require the introduction of several definition and notions which are out of the scope of this thesis, we present only some insights to understand its principle and especially how it has been adapted to solve the constrained problem (1.7). The detailed algorithm can be found in [START_REF] Ishizaki | Clustered model reduction of positive directed networks[END_REF]. The algorithm is an iterative greedy algorithm which means that at each step the best pair of nodes is selected and merged. The metric used to quantify the value of a pair of node, denoted by δ in the algorithm, of node is not given here. At each step only the number of nodes in the network is reduced by one, and then the same procedure is applied (n -n) times where n is the size of the initial graph and n is the desired size of the final graph. By merging iteratively nodes, we end up with a partition of the initial network. In the original algorithm, any pair of nodes may be merged at each iterations. Thus, the final partition may be disconnected. This is described in Algorithm 9 hereafter and is taken from [START_REF] Ishizaki | Clustered model reduction of positive directed networks[END_REF]. In the adaption we proposed, described in Algorithm 10, only the connected nodes can be merged at each step. Thus, the final partition is necessarily connected. In the algorithms, V k and E k correspond respectively to the set of nodes and the set of edges of the network after k iterations. for all pair (i, j) ∈ V k × V k do 4:

Assign a reducibility value to the pair (I i , I j ) := δ i,j

5:

end for

6:

Merge the parts minimizing the reducibility value, which is Other computations are done after this algorithm to deduce the weight in P but there are identical for the two problems. For our concern we are only interested in this part of the reduction method. Note that these two algorithms are suboptimal. In a first estimate we consider that the weights are W 0 = [START_REF] Vadim | Maximum regular induced subgraphs in 2P3-free graphs[END_REF][START_REF] Guimera | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF][START_REF] Monshizadeh | Stability and synchronization preserving model reduction of multi-agent systems[END_REF][START_REF] Holme | Attack vulnerability of complex networks[END_REF][START_REF] Krioukov | Hyperbolic geometry of complex networks[END_REF] . This set of weights does not induce a flow network. By computing the orthogonal projection of W 0 on Ker(A e ) we find, a vector W 1 of weights inducing a flow network and minimizing the difference W 0 -W 1 2 . In this case, the vector is as follows W 1 = [133. 75, 28.75, 133.75, 28.75, 162.5] .

Introduction 0 . 1 Contents 3 . 3 104 4to traffic 107 4. 1 107 4. 2 110 5to network epidemiology 117 5. 1

 0133104107110721101171 Motivation to network reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2 Introduction to network theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.3 Scale-free networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.4 Problematics and contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 The price of connectedness 1.1 The price of connectedness and problem formulation . . . . . . . . . . . . . . . 1.2 Illustrative example: The clustered model reduction . . . . . . . . . . . . . . . 1.3 Value of the ratio of connectedness in a (n, p)-Erdős-Rényi graph . . . . . . . . 1.4 Validation of the upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Network partitioning algorithm towards scale-free structure 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Framework for a class of problems . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 A first instance of the problem fostering node similarity . . . . . . . . . . . . . 2.4 Property preserving problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Some results about the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Network partitioning algorithm towards average detectability 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Regular Induced Subgraph (RIS) detection for exact average detectability . . . xi xii Approximate average detectability . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Application Traffic network of Grenoble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reduction of the Grenoble traffic network . . . . . . . . . . . . . . . . . . . . . Application Introduction to network epidemiology . . . . . . . . . . . . . . . . . . . . . . . 118 5.2 MergeToCure, scale-free abstraction for cure allocation strategy . . . . . . . . . 122 5.3 Average detectability of an epidemic spreading . . . . . . . . . . . . . . . . . . . 128 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Conclusion 133 A Algorithms for clustered model reduction 139 B Weight projection to ensure the mass conservation property Introduction L'art de donner le même nom à des choses différentes Henri Poincaré 0.1 Motivation to network reduction 0.1.

  (a) Network of the connection between the characters of the Game Of Thrones universe (season 1) (b) Simplified network of the human metabolism (c) The Zachary's karate club network is an example of social network commonly used (d) Visual representation of a portion of the Internet structure from the Opte Project

Figure 2 :

 2 Figure 2: Use of networks in various research areas.

Figure 3

 3 Figure3gives an illustration of the degree distribution of a network.

Figure 3 :

 3 Figure 3: A network of 5 nodes (a) and the corresponding degree distribution (b): Three nodes (v 2 , v 3 , v 5has degree 1, one node (v 4 ) has degree 2 and one node (v 1 ) has degree 3.

Figure 4

 4 Figure 4 illustrates the notions of partition, merging and network coming out of a partition.

Figure 4 :

 4 Figure 4: Illustration of partition and merging

Figure 5

 5 Figure 5: Network connectedness

  much a network tends to form clusters. Different versions of the clustering coefficient exist. The one we use requires first the computation of the local clustering coefficient: Definition 0.12 (Local clustering coefficient) The local clustering coefficient of a node v, denoted c v is the following quantity:

Figure 7 Figure 8 :

 78 Figure 7: Network regularity

( a )

 a Network with a homogeneous degree distribution: all nodes have more or less the same degree (b) Scale-free network: some nodes are highly-connected and most are poorlyconnected The degree distribution of a scale-free network is heavy-tailed: the right side is extended further.

Figure 9 :

 9 Figure 9: Comparison of two types of networks and their respective degree distribution

Figure 13 :

 13 Figure 13: Due to its underlying hyperbolic nature, a scale-free networks is particularly adapted to network navigation. The computation time needed for it is several order of magnitude lower than the classical Djikstra algorithm.

  (a) Scale-free network. The ten most connected nodes are plotted in red. (b) Scale-free network after vaccination: the ten most connected nodes has been removed. (c) Random network. The ten most connected nodes are plotted in red. (d) Random network after vaccination: the ten most connected nodes has been removed.

Figure 14 :

 14 Figure 14: Strategy of vaccination for scale-free networks

Figure 15 :

 15 Figure 15: We present two different configurations of a basic information propagation model.In (a) the system is structurally controllable: every node is reached by the input. In (b) the system is not structurally controllable: a node can not be reach by the input.

Figure 16 :

 16 Figure 16: Even if the two networks are structurally controllable one can feel that the information is much more easily transmitted in the second case.

Figure 17 :

 17 Figure 17: Energy needed to transmit the information up to Chloé as a function of the probability of transmission. Here we plot the three metrics measuring the control energy

x

  Time and computation consumingNeed few energy to controlGood approximation of controlNot time-consumingx Need a lot of energy to controlGood approximation of controlNot time-consuming Need few energy to control

Figure 18 :

 18 Figure18: In[START_REF] Casadei | Scale Free Controllability of Large-Scale Networks: an Output Controllability Approach[END_REF] several control strategy for network are compared. In the first scenario, the whole system is considered. A control design can be found to reach a desired state with low energy. However, for large-scale network the computation needed to find this control may be tremendous. The second and third scenarios uses then an abstraction of the large-scale network to reduce the computation requirements and preserve a good approximation of the desired state. Moreover, in the third scenario it is emphasized that if the controlled nodes are the hubs of the network, the energy needed is much lower than for random controlled node.

Figure 19 :

 19 Figure 19: Principle of the Scale-Free reduction approach.

Figure 20 : 1 37 1. 2 40 1. 2 . 1 40 1. 2 . 2 42 1. 2 . 3 43 1. 3 45 1. 3 . 1 45 1. 4

 2013724021402242234334531454 Figure 20: A visualization of the structure of the thesis

Figure 1 . 1 :

 11 Figure 1.1: A class in which pupils have different affinity forms a network.Here the nodes are the pupils and the edges represent the friendship between them which can be one-sided (yes it may be sad, but it is for the sake of the example). To constitute working groups, should the teacher consider this friendship network ? This image is from "Les Choristes" of Christophe Barratier.

∆Figure 1 . 2 :

 12 Figure 1.2: Partitioning the network in three parts in order to minimize the standard deviation within the parts. The price of connectedness is the difference between the optimal solutions in the unconstrained and constrained case, in this case ∆ = 1.35 -0.94 = 0.41.

Figure 1 . 3 :

 13 Figure 1.3: In order to estimate the price of connectedness, we compare for a given network the number of partitions and the number of connected partitions. The ratio of the two cardinalities is the ratio of connectedness.

  With this network the partition is connected:I(P ) ∈ I c (G).

Figure 1 . 4 :

 14 Figure 1.4: Connected and disconnected partitions. The partition is the one defined in (1.6) applied to two different networks.

Definition 1 . 1 (

 11 Connected partition) A partition I of a network G is a connected partition if and only if every subgraph G I l induced by a part I l is weakly connected. I c (G) represents the set of connected partitions of a network G. See fig. 1.4 for an example of connected and disconnected partitions. Using this definition, the constrained problem can be written as follows:

  Figure 1.5 shows the value of u and c as a function of the reduction factor n-n n .

Figure 1 . 5 :

 15 Figure 1.5: Estimation error in the unconstrained problem and in the constrained problem. The difference between the two results is the price of connectedness.

Figure 1 . 6 :

 16 Figure 1.6: Relation between the price of connectedness and the ratio of connectedness. Each point correspond to an Erdős-Rényi graph with n = 100 and p ∈ [0; 1]. The ratio of connectedness, ρ(G, M ) is estimated by counting the number of connected partitions over the 500 partitions randomly generated (we fix arbitrarily M = [5, 5, . . . , 5]). The price of connectedness ∆(G) is computed using (1.10) and Appendix A. In dotted blue the fitting function in (1.14).

  should be replaced respectively with m(m -1) -2, m(m + 1)/2 -1 and m(m -1)/2 -1 and m 2 k the total number of network with m nodes and k edges should be replaced respectively with m(m-1) k , m(m+1)/2 k and m(m-1)/2 k .

Figure 1 . 7 :

 17 Figure 1.7: This diagram illustrates the approach proposed in this chapter. In order to estimate the price of connectedness we estimate the ratio of connectedness ρ(p, n, M ): line (1). Based on (1.15), we factorize the problem: line (1) to line (2). Then the upper bound (1.17) allows the passage from line (2) to line (3). The rest of the chapter present the calculations leading to Propositions 1.1 and 1.2 giving the value of ρ0 . Finally the factorization formula (1.22) lead to the final upper bound of the ratio of connectedness: line (3) to line (4).

Figure 1 . 8 :

 18 Figure 1.8: Comparison between the experimental value of ρ(m, p) (the probability that a given (m, p)-Erdős-Rényi graph is connected) and the theoretical value of the upper bound ρ0 (m, p) (the probability that a given (m, p)-Erdős-Rényi graph has no isolated node) for p ∈ [0, 1] and for different values of m. The phase transition behavior detailed in (1.16) is represented in dotted black: when m grows ρ(m, p) gets closer to the transition.

Figure 1 . 9 :

 19 Figure 1.9: Comparison between the experimental value of ρ(100, p, {5, . . . , 5}), and the theoretical value of the upper bound ρ 0 (100, p, {5, . . . , 5}) for p ∈ 0 : 0.005 : 1.

Figure 2 . 1 :

 21 Figure 2.1:The scale-free cost function measures the difference between the degree distribution Π G and the target scale-free distribution which is here Π SF 2,100 . By minimizing the dashed zone the reduce networks tends to be scale-free.

Algorithm 2

 2 Merge To Scale-Free with node similarity Input: G 0 , α SF , n rand , Output: G end 1: k = 0 2: while ¬stop do 3: Ω ←-n rand random elements of E k 4:

Figure 2 . 2 :

 22 Figure 2.2: Evolution of the scale-free cost function through the algorithm. The evolution is averaged over 100 simulation on a same network of size 1000 with n rand = 50.

Figure 2 .

 2 Figure 2.3 illustrates the computation of the projection and the comparison between G 0 and G 1 .

G

19 TFigure 2 . 3 :

 1923 Figure 2.3: This figure illustrates the projection operator(2.16) and the computation of the eigenvector distance(2.18). To compare the dynamical behavior of G 0 and G 1 (with G 0 G 1 ) we first compute the eigenvector centrality for each using (2.12). The computation of this centrality depends on the weights assigned on the edges, here we considered that all weights are equal to 1. As the two vectors are not of the same dimension we sum the component of Φ(G 0 ) within each part of the partition. In this way we obtain σ S (Φ(G 0 )) which can be compared with Φ(G 1 ) leading to the vector ∆ G 0 ,G 1 . Here we notice that the reconstruction of the yellow part is good, while the reconstruction of the other part are not.

Figure 2 . 4 :

 24 Figure 2.4: Comparison of the evolution of the scale-free cost function through the algorithm for different values of n rand . The initial network is a Manhattan-like grid of size 45 × 45 and with 1962 nodes. The simulation is stopped when the size of the current network is equal to 5% of the size of the initial network.

Figure 2 . 5 :

 25 Figure 2.5: Histograms of the properties of the different networks obtained with different instances of the algorithm and with the same initial network. For each property, the x-axis represents the values and the y-axis, the frequency of apparition of each value. The green bars shows the values obtained when n rand = 3, the red bars when n rand = 30 and the blue bar when n rand = +∞. The superimposed lines fits the histograms.

Figure 2 . 6 :

 26 Figure 2.6: Histograms of the normalized mutual information between the partition of reference and the 50 partitions obtained with n rand = 3 (in blue) and the 50 partitions obtained with n rand = 30 (in red).

  (a) The initial network. Double-way links are thicker than one-way ones. (b) Indegree distribution of the initial network, of the reduced network and the target distribution in log-log representation. (c) The reduced network issued from the partition. The size of the nodes represents their degree and the color matches with the color of the partition in (d). (d) Final partition of the initial network. The color matches with the colors of the nodes in the reduced network (c).

Figure 2 . 7 :

 27 Figure 2.7: Result of the Manhattan-like grid simulation. (a) the initial network, (b) the indegree distributions, (c) the final network and (d) the final partition. Sub-figure (b) emphasizes well the efficiency of the network to drive the degree distribution very close to the target distribution.

  (a) We detect a regular induced subgraph. Here the five nodes in the center have a same outdegree equal to 2.(b) The system is excited with an arbitrary sinusoidal input in some nodes. The dotted blue lines represent the evolution of the unmeasured node and the solid blue line their average. The solid red line represents the evolution of the observer described in (3.6) which converges towards the averaged value.

Figure 3 . 2 :

 32 Figure 3.2: Representation of the approach proposed in this section: (a) from an initial negative uniform network, a regular subgraph is detected; (b) as the system is average detectable, the observer (3.6) converges towards the averaged value of the unmeasured nodes.

Figure 3 . 3 :

 33 Figure 3.3: Left: The largest regular induced subgraph found is highlighted in red. The double-way edges are thicker. All the nodes in the subgraph have an outdegree equal to 3. Right: The upper bound (k-Core) is displayed in blue for k ∈ {1; 2; 3; 4}. The real size of k-RIS are in dot red for k ∈ {1; 2; 3}. The 4-RIS is not computed since σ(4) < |3-RIS|. The red dotted line represents the size of the RIS.

Figure 3 . 4 :

 34 Figure 3.4: The family of p-reg networks allows to control the regularity of a network.

Figure 3 . 5 :

 35 Figure 3.5: A 2-reg network as defined in Definition 3.4 with an additional node to measure. For the experiments, a similar network is used with 100 nodes and p varying from 1 to 100.

Figure 3 . 6 :

 36 Figure 3.6: Error of reconstruction as a function of the error regularity for the family of p-reg network. For each p ∈ [1, ..., 100], 25 p-reg network are generated with different inputs.The error of reconstruction is then computed as the bias between the signal and the reconstruction at t = 1000 (which is a good approximation of e ss ). This emphasizes the link between the regularity of a subgraph and the ability to reconstruct its average.

Figure 3 . 7 :

 37 Figure 3.7: Illustration of Algorithm 7.Here the beam width β = 2, so at each step the best two candidates are kept (solid line). Two small modifications are brought to make the example more readable: the seed is a single candidate while in the algorithm the seed is composed of the singletons of each node; the new candidates are the subsets composed of a previous candidate and a node neighboring this candidate, while the latter node can be arbitrary chosen in the algorithm.

Figure 3

 3

Figure 3 . 8 :

 38 Figure 3.8: Illustration of the qRIS approach. Our algorithm is able to detect a subgraph (a) which is enough regular to make the reconstruction of its average quite good (b).

Algorithm 8 Figure 3 . 9 :

 839 Figure3.9: The initial network is a grid designed such that certain zones are more regular. The algorithms aims to find these zones. These zones are not easily identifiable at the naked eyes and the reader is invited to try it before looking at the result of the algorithm.

  (a) A first subgraph is found (in blue). On the right the evolution of the regularity error of the best candidate through the iterations. The red dot corresponds to the iteration where the subgraph maximizing (3.31) is found. (b) The first subgraph found and its successors are removed and the algorithm is applied again to detect a second subgraph (in blue). (c) The second subgraph found and its successors are removed and the algorithm is applied again to detect a third subgraph (in blue). (d) The third subgraph found and its successors are removed and the algorithm is applied again to detect a fourth subgraph (in blue).

Figure 3 .

 3 Figure 3.10: (a-e) Left: in blue the detected subgraph within the current network; Right: the evolution of the regularity error of the best candidate is displayed through the iteration. A red dot shows the iteration of the selected subgraph. (d) represents the network obtained by merging the different subgraphs. This reduced network offers an estimation of the initial network, and thus can be seen as an aggregation of it.

Contents 4 . 1

 41 Traffic network of Grenoble . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.1.1 Geographical network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.1.2 Estimation of the flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.1.3 Physical properties of traffic networks . . . . . . . . . . . . . . . . . . . . 109 4.2 Reduction of the Grenoble traffic network . . . . . . . . . . . . . . . . 110 4.2.1 The reduced system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.2.2 Simulations on the reduced network . . . . . . . . . . . . . . . . . . . . . 111

4. 1 . 1

 11 Geographical networkSituated in the south-east of France, close to the Alps, Grenoble is the 16th largest city of France. The situation of the city, surrounded by three ranges of mountains, constraints the urban traffic network making Grenoble the fifth most congested city in France[115]. See fig.4.1 for a satellite picture of the city. In the framework of the ScaleFree-Back project 1 the collection of traffic data and the monitoring of the traffic condition over the whole city is1 For further information see http://scale-freeback.eu/.

107

 107

Figure 4 . 1 :

 41 Figure 4.1: Satellite picture of Grenoble. We can see the Vercors range in the west, the Chartreuse range in the north and the Belledonne range in the south-east constraining the development of the urban traffic network.

Figure 4 . 3 :

 43 Figure 4.3: Sample of the network: the nodes represent the streets, and the weights on edges are estimated flow from one node to another. The weights are computed such that the network is a flow network.

Figure 4 .

 4 Figure 4.4 presents the initial network and the partition found by the algorithm. Figure 4.5 presents the reduced network coming out of this partition and the different degree distributions.The ability of the algorithm to get close to the desired distribution is clear as the reduced network exhibits a power law degree distribution. Few hubs are visible on the reduced network. However, as seen in Chapter 2, when the reduced network becomes too small it tends to loose its scale-free structure. Therefore, a compromise must be found between the scale-freeness of the reduced network and its smallness.

  (a) Initial network (b) Partition obtained through the algorithm. The color of each part matches the color of the nodes of the reduced network in fig. 4.5

Figure 4 . 4 (

 44 Figure 4.4

Figure 4 . 5

 45 Figure 4.5

Figure 4 . 6 :Figure 4 . 7 :

 4647 Figure 4.6: The Grenoble traffic network with the inflows coming from the borders

Contents

5. 1

 1 Introduction to network epidemiology . . . . . . . . . . . . . . . . . . . 118 5.1.1 Overview of the models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.1.2 The SIS model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.2 MergeToCure, scale-free abstraction for cure allocation strategy . . . 122 5.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.2.2 The strategy Merge To Cure . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3 Average detectability of an epidemic spreading . . . . . . . . . . . . . 128 5.3.1 The estimation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.3.2 Topology of the network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.3.3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

  The model proposed by Kermack-McKendrick is the first one to propose a compartment system. In this model, the population is divided into three different compartments (susceptible, infected, recovered) whose size is governed by a differential equation. Other compartment models exist with different compartments and different dynamics. With the arrival of network theory, compartmental models can take into account the interaction between individuals. The equation of evolution depends on the model chosen and is not precised here.

Figure 5 . 1 :

 51 Figure 5.1: Illustration of the compartments model in epidemiology

Figure 5 . 2 :

 52 Figure 5.2: Sketch of the SIS model

Figure 5 . 3 :

 53 Figure 5.3: Example of a network corresponding to the SIS model in (5.6). The snake lines correspond to the inputs.

Figure 5 . 4 :

 54 Figure 5.4: Illustration of the strategy MergeToCure to find a subset of nodes to cure in a Manhattan-like grid. For simplicity, we present here an undirected network, but the same process can be applied to a directed network.

Figure 5 . 5 :

 55 Figure 5.5: Averaged benefit brought by each strategy for different value of λ and N hub in a 60 × 60 grid network. When B = 1 it means that ρ(G σ , λ) = 0 which means that the strategy allows to completely eradicate the disease.

Figure 5 . 6 :

 56 Figure 5.6: Benefit brought by the strategy MergeToCure as a function of the scale-free coefficient of the abstracting network.

Figure 5 . 7 :

 57 Figure 5.7: Interpolating map of the number of individual infected with flu for 100000 inhabitants in January 2019 in France. Map available on www.sentiweb.fr. c Inserm

Figure 5 .

 5 10 shows the evolution of the proportion of infected individuals inside each subgraph and the estimation made with the open-loop observer xav 2 described in (3.6

Figure 5 . 8 :

 58 Figure 5.8: The network of interactions over the France territory. It is composed of 1404 nodes, each representing a population of 5000 individuals. The subgraphs within the cities are based on the Watts-Strogatz model while the network between the cities is a random network where the probability of connection between two nodes decreases exponentially with the distance.

Figure 5 . 9 :

 59 Figure 5.9: Partition obtained via the mqRIS algorithm. The legend gives the error of regularity, the number of nodes and the mean degree for each subgraph detected.

Figure 5 . 10 :

 510 Figure 5.10: Proportion of infected individuals within each subgraph. The solid lines are the ground-truth values and the dotted lines are the estimated values.

Figure 5 .

 5 Figure 5.11: Semi-log representation of absolute errors between the ground-truth value and the estimated value for each subgraph. The errors are decreasing but they do not converge to zero.

Algorithm 9 1 :

 91 Original Cluster Model Reduction Input: Network G and desired final size n Output: Final partition I Initialize the partition as I ← {I 1 , . . . , I N } = {{1}, . . . , {N }} 2: for k = 1 : (n -n) do 3:

(

  I a , I b ) := argmin δ(I i , I j ), I a ← I a ∪ I b , I ← I\I b (A.1) 7: end for

  139

  The initial estimation of the flow. The thickness of the edges represents the flow.

  The flow after projection on the space ensuring a flow network. The thickness of the edges represents the flow.

Figure B. 2 : 4 )w 5 -

 245 Figure B.2:The projection of the set of weight on the null space of the edge adjacency matrix ensures the network to be a flow network and to be as close as possible from the initial weights.

Figure B. 2

 2 illustrates this transformation of the weights.

Table 1 :

 1 Eccentricities, radius and diameters for networks of fig.5

  Complex Networks 2017-The 6th International Conference on Complex Networks and Their Applications. 2017, pp. 294-296 Nicolas Martin, Paolo Frasca, and Carlos Canudas-de Wit. "A network reduction method inducing scale-free degree distribution". In: 2018 European Control Conference (ECC). IEEE. 2018, pp. 2236-2241 Nicolas Martin, Paolo Frasca, and Carlos Canudas-de Wit. "MergeToCure: a New Strategy to Allocate Cure in an Epidemic over a Grid-like network Using a Scale-Free Abstraction". In: IFAC-PapersOnLine 51.23 (2018), pp. 34-39 Nicolas Martin et al. "The price of connectedness in graph partitioning problems". In: 2019 18th European Control Conference (ECC). IEEE. 2019, pp. 2313-2318

		With or without
		connectedness ?
		Chapter 1
		Network
		partitioning
	Towards	Towards de-
	scale-freeness	tectability
	Chapter 2	Chapter 3
	In urban	Cure	Estimate
	traffic	allocation for	epidemic
	network	epidemics	spreading
	Chapter 4	Section 5.2	Section 5.3

  Algorithm 3 Merge to scale-free with property preservation Input: G 0 , α SF , n rand

	Output: G end
	1: x 0 = Φ(G 0 )
	2: P 0 from (2.13)
	3: κ from (2.29)
	4: k = 0
	5: while ¬stop do
	6:	Ω ←-n rand random elements of E k
	7:	for (v, w) ∈ Ω do
	8: 9:	Compute G n SF (S v,w ) = J SFα (G Sv,w from (2.30) k Sv,w k )
	10:	end for
	11:

S best = argminn SF (S v,w ) 12:

Table 2 . 1 :

 21 Modification of the properties of the network through the reduction

		Initial network Reference network Reduced networks Evolution
	Num. of nodes	1165	508	516.42
	Num. of edges	4426	1911	2236.80
	Radius	29	20	9.16
	Diameter	57	37	17.22
	Num. of hub	0	0	35.14
	Clust. coeff.	0.1	0.1	0.43
	Max indegree	6	6	23.3
	Mean indegree	3.80	4.33	3.76

Table 2 . 2 :

 22 .2 and the output of the simulation is presented in fig. 2.7. Parameters of the simulation on the Manhattan-like grid

	Size	|G| α SF n rand Degree
	65 × 65 3824	2	10	in

1 :

 1 Cand ← {{1}; {2}; . . . ; {n}} 2: while min I∈Cand (G I ) < 0 do

	3:	for c ∈ Cand do
	4:	S ← [1, . . . , n]\c
	5:	J c = {c ∪ S 1 ; c ∪ S 2 ; . . . ; c ∪ S end }
	6:	end for
	7:

Table 4 . 1 :

 41 Parameters of the simulation on the Grenoble urban traffic network

	|G|	α SF n rand n iter
	13099	2	50	11000

Table 5 .

 5 1: Parameters for the network of interactions and the SIS model

	Population
	Number of groups (nodes)	1404
	Pop. per groups	5000
	Number of cities	22
	Network
	Model within cities	Watts-Strogatz
	Mean degree K	10
	Prob. rewire β	0.1
	Prob. connection inter-cities	e d 2 /10 850
	Number of inputs	323
	SIS model
	Infection rate β	0.05
	Recovery rate δ	0.98

Certains ouvrages en français parlent d'invariance d'échelle mais le terme anglais est le plus souvent conservé.i

See http://scale-freeback.eu/

While we use the terms of network and node throughout the thesis the notation G and V inherits from the terms graph and vertex. In the next section we will briefly discuss this terminology

However, for readability concern we may illustrate some notions with undirected networks.

In the literature, the term cluster is also used. We prefer here part for the consistency with partition and to avoid the polysemy of cluster.

We coined this term and it is not used in the literature

Note that in Chapter 2 we will consider a different type of evolution. We present here the most commonly used dynamical equations from which we can define notions of control theory.

This definition corresponds to the Gramian in infinite time. Another version in finite time exist also but will not be considered here.

The model is even ultra small-world which means that the characteristic lengths grow as the logarithm of the logarithm of the number of nodes[START_REF] Cohen | Scale-free networks are ultrasmall[END_REF]

Here is a video showing different manners to arrange the nodes of a network: https://www.youtube.com/ watch?v=sRujricoGQY

in a population, communities can be viewed as a connected subgraph

This term has been coined in reference to the concept of price of anarchy in game theory. This refers to the degradation due to the selfish behavior of the agent compared to the global optimum[START_REF] Koutsoupias | Worst-case equilibria[END_REF].

Cardinality of I(G, M ) is a known result[START_REF] Mussmann | Counting Partitions or Subsets[END_REF]. However we will not use this result since we will derive an upper bound of ρ and not its exact value.

It is clear that the ratio of connectedness ρ grows with p: increasing p gives a network with more edges and so the number of connected partitions is higher. At the limit, if p = 1 (complete graph) then ρ = 1 and if p = 0 (null graph) then ρ = 0.

When ρ goes to 0 the number of connected partitions goes to 0 and the optimal solution of the constrained problem worsens which is ∆ → ∞. On the other hand, when ρ = 1, every partition is a connected partition (the graph is complete) and the solutions of the constrained and unconstrained problems are the same which is ∆ = 0.

The video is available here: https://www.youtube.com/watch?v=UXc76Z5Ek3M&t=56s

This is why we just need the result of Theorem 2.2 for merging.

see https://www.youtube.com/watch?v=h3NUfM5weP4

The existence and uniqueness is ensured by the Perron-Frobenius theorem[START_REF] Unnikrishna Pillai | The Perron-Frobenius theorem: some of its applications[END_REF]

When he is on a node, the walker chooses randomly his next step among the neighbors of the node with a probability proportionally to the weights on the edges.

Note that the term distance does not correspond used here to the mathematical acceptance of this term which is a scalar verifying a certain number of properties.

These properties are defined in Section 0.2.2

Here, we call regular a network in which all the nodes have the same outdegree. The term out-regular would be more accurate, but we prefer regular for readability concerns.

This term should not be mistaken with the notion of balanced network existing in network theory in a different context.

Nout(r) is the set of successors of r

The GTL-ville aims to monitor the traffic condition inside the whole city of Grenoble. See http://gtlville.inrialpes.fr/.

as defined in Section 0.2.2 a flow network is a network with the mass conservation property

In this model we neglect the cars parking along a street which would violate the mass conservation property

Let us note that, in reality, a lot of cars are parked in the city and starts from inside the network. However, we choose to have inflows only from the outside of the network to observe the progressive diffusion of the cars in the network

An animation of the complete simulation is available here: https://youtu.be/6wSF_kqFVL8

instead of the term cure, the terms vaccine, treatment or quarantine are also used. Indeed, all refer, in a certain way, to the removal of the node from the network.

These notions has been presented in Section 0.2.2

patient zero, the first infected individual.

see Section 0.3.2

this measure corresponds to the steady state of the network excited by a linear and stable discrete-time system.

if a network have this property, the sum of the weights coming in a node equals the sum of the weights coming out of this node.

In network epidemiology, cure allocation strategies aim to find the nodes to remove from the network (by curing them) in order to reduce the propagation of a disease.

Following the GTL project[START_REF] Canudas-De | Grenoble traffic lab: An experimental platform for advanced traffic monitoring and forecasting[END_REF] who aimed to monitor the traffic condition on a single road in the south of Grenoble, the GTL-ville aims to monitor the traffic condition inside the whole city of Grenoble. See http://gtlville.inrialpes.fr/.

Remerciements

Algorithms for clustered model reduction

for all pair (i, j) ∈ E k do 4:

Assign a reducibility value to the pair (I i , I j ) := δ i,j

5:

end for

6:

Merge the parts minimizing the reducibility value, which is

Weight projection to ensure the mass conservation property

Given a network G = (A, V, E), the edge adjacency matrix, denoted by A e , is a matrix of size n × m, where n is the number of nodes and m is the number of edges in the matrix and define as follows:

The vector of weights W ∈ m is defined as:

If the network is a flow network then A e and W verify

Therefore, we want the vector of weights to belong to the null space of A e . Thus, considering a vector W 0 , we obtain a vector W 1 which ensure the mass conservation property by projecting W 0 on Ker(A e ). The projection is orthogonal in order to minimize the value of W Mots clés : Algorithme de partitionnement, réseau scale-free, réduction de réseau

Abstract -In light of the complexity induced by large-scale networks, the design of network partitioning algorithms and related problematics are at the heart of this thesis. First, we raise a preliminary question on the structure of the partition itself: as the parts may includes disconnected nodes, we want to quantify the drawbacks to impose the nodes inside each part to be connected. Then we study the design of a partitioning algorithm inducing a reduced scale-free network. This allows to take advantage of the inherent features of this type of network. We also focus on the properties to preserve to respect the physical and dynamical profile of the initial network. We investigate then how to partition a network between measured and unmeasured nodes ensuring that the average of the unmeasured nodes can be efficiently reconstructed. In particular we show that, under hypothesis, this problem can be reduced to a problem of detection of subgraph with particular properties. Methods to achieve this detection are proposed. Finally, three applications are presented: first we apply the partitioning algorithm inducing scale-freeness to a large-scale urban traffic network. We show then that, thanks to the properties preserved through the partition, the reduced network can be used as an abstraction of the initial network. The second and third applications deal with network epidemics. First, we show that the scale-freeness of the abstracting network can be used to build a cure-assignation strategy. In the last application, we take advantage of the result on average reconstruction to estimate the evolution of a disease on a large-scale network.