Search

The multiplicative increase multiplicative decrease (MIMD) congestion control algorithm in the form of scalable TCP has been proposed for high speed networks. We study fairness among sessions sharing a common bottleneck link, where one or more sessions use the MIMD algorithm. Losses, or congestion signals, occur when the capacity is reached but could also be initiated before that. Both synchronous as well as asynchronous losses are considered. In the asynchronous case, only one session suffers a loss at a loss instant. Two models are then considered to determine which source looses a packet: a rate dependent model in which the packet loss probability of a session is proportional to its rate at the congestion instant, and the independent loss rate model. We first study how two MIMD sessions share the capacity in the presence of general combinations of synchronous and asynchronous losses. We show that, in the presence of rate dependent losses, the capacity is fairly shared whereas rate independent losses provide high unfairness. We then study inter protocol fairness: how the capacity is shared in the presence of synchronous losses among sessions some of which use additive increase multiplicative decrease (AIMD) protocols whereas the others use MIMD protocols.

We study an adaptive window protocol (AWP) with a general increase and decrease profile in the presence of window dependent random losses. We derive a steady-state Kolmogorov equation and obtain its solution in analytic form. We obtain some stochastic ordering relations for a protocol with different bounds on window. A closed form necessary and sufficient stability condition using the stochastic ordering for the window process is established. Finally, we apply the general results to particular TCP versions such as NEW Reno TCP, scalable TCP and Highspeed TCP. We observe that Highspeed TCP can be used to approximate almost any kind of window behavior by varying only one design parameter.

Scalable TCP [x] is a proposition for a new TCP where both the increase and the decrease rate of the window size are multiplicative. It has been recently proposed in order to improve performance in high speed networks. In this paper, we present a mathematical analysis of such multiplicative increase multiplicative decrease protocols in the presence of random losses. These are typical to wireless networks but can also model losses in wireline networks with very high bandwidth delay product. Our approach is based on showing that the logarithm of the window size evolution has the same behaviour as the workload process in a standard G/G/1 queue. The Laplace-Stieltjes transform of the equivalent queue is shown to provide directly the throughput of Scalable TCP as well as the higher moments of the window size. We validate our findings using ns-2 simulations.

The non-preemptive priority queueing with a finite buffer is considered. We introduce a randomized push-out buffer management mechanism which allows to control very efficiently the loss probability of priority packets. The packet loss probabilities for priority and non-priority traffic are calculated using the generating function approach. In the particular case of the standard non-randomized push-out scheme we obtain explicit analytic expressions. The theoretical results are illustrated by numerical examples. The randomized push-out scheme is compared with the threshold based push-out scheme. It turns out that the former is much easier to tune than the latter. The proposed scheme can be applied to the Differentiated Services of the Internet.

The research results presented here are extensions of previous work on Iterative Learning Control (ILC) using projection-based update techniques. These updates were mainly developed for Quasi-Newton optimization and also for solving systems of simultaneous equations. Recently, such updates have been used by the authors to estimate the dynamics of a control system which is asked to perform a periodic task using a discrete formulation. In addition, recently, preliminary extensions of these updating techniques to continuous systems through formulation in Hilbert Space have been proposed. This paper provides a formulation of the Iterative Learning Control problem in Hilbert Space with a convergence proof of the proposed solution based on Broyden’s update.

Data transfer on the UMTS downlink can be done either through dedicated channels (DCH) or shared channel (FACH). The data transfers on the DCHs can receive very high throughputs. However, a setup time of the order of 250 ms is required before data transfer can begin on the DCH. For very short transfers it may be better to use the shared channel. However, for long data sessions it might be better to allocate a dedicated channel. In this paper, we propose a threshold policy to determine which sessions should use the dedicated channels. Initially, we use the FACH for a given connection. Then if we get an indication that the current burst might be long (for example, we observe a long queue from that source), then beyond some threshold we shall try to allocate a DCH to that connection (if there is one available). We also present and evaluate the performance of algorithms in which a timer is set when the queue size falls below a threshold and the connection is on DCH. The use of timer allows a connection to remain for a longer duration on DCH and thus improve performance. We use ns-2 simulations to obtain the performance measures for the threshold and timer based policies.

We consider the inversion of perturbed linear operators on Hubert space. Namely, we study linear operators that depend on a small parameter and are singular when the parameter is equal to zero. First we consider the affine dependence on the parameter. We treat subsequently the cases of bounded operators with closed range, bounded operators with non closed range, and densely defined and closed unbounded operators. Then, we extend the results to the cases of polynomial and analytic perturbations.

We model the TCP/IP network with non persistent sessions on three levels: Packet level, Session level and System level. On the packet level we characterization the packet arrival process at the bottleneck queue and we calculate the packet loss probability using the fixed point approach. In particular, we study by simulation under which conditions the multiplexed traffic is close to Poisson. On the session level, using the fluid model approach and conditioning on the number of loss instants, we calculate the average transfer time of the TCP flows as a function of the packet loss probability and the parameters of the TCP protocol. We show that the expected latency conditioned on the fact that a packet has been lost is not monotone with respect to the file size. Finally, on the system we apply the M/G /∞ model to obtain the distribution of the number of active active sessions. All analytical results are confirmed by NS simulations.

We consider an analytic perturbation of the Sylvester matrix equation. Mainly we are interested in the singular case, that is, when the null space of the unperturbed Sylvester operator is not trivial, but the perturbed equation has a unique solution. In this case, the solution of the perturbed equation can be given in terms of a Laurent series. We provide a necessary and sufficient condition for the existence of a Laurent series with a first order pole. An efficient recursive procedure for the calculation of the Laurent series' coefficients is given. Finally, we show that in the particular, but practically important case of semisimple eigenvalues, the recursive procedure can be written in a compact matrix form.

In this survey we present a unified treatment of both singular and regular perturbations in finite Markov chains and decision processes. The treatment is based on the analysis of series expansions of various important entities such as the perturbed stationary distribution matrix, the deviation matrix, the mean-passage times matrix and others.

We compare buffer management policies that offer differentiated services to TCP traffic, with the goal of providing some sort of performance guarantees to a premium class of traffic. Specifically, we study the effectiveness of a scheduling policy combined with various buffer management policies on the performance of competing TCP connections. In this work we consider a stochastic model for a classbased weighted-fair-queueing scheduling policy where packets of different classes are scheduled according to their pre-assigned static weights. We consider two buffer management policies: complete partitioning, and complete sharing with pushout at various thresholds. We consider two classes of TCP traffic in our model. Our goal is to propose mechanisms with easily adjustable parameters to achieve service differentiation as required. In the numerical results we show how the scheduling and buffer policies can be used to provide some sort of performance guarantee to the higher class.

We develop a model for TCP that accounts for both sublinearity and limitation of window growth. Sublinear window growth is observed when the round-trip time of the connection increases with the window size. Limitation is due to the window advertised by the receiver. First, we derive the conditions for the stability of the model. Then, we write the Kolmogorov equation under Markovian assumptions. The model is solved analytically for some particular cases. A good match between the throughput predicted by the model and the throughput measured on real TCP connections is reported at the end.

In this paper we analyze the performance of a TCP-like flow control mechanism. The transmission rate is considered to increase linearly in time until the receipt of a congestion notification (via loss detection in context of TCP) where the transmission rate is multiplicatively decreased. We introduce a general model based on a multi-state Markov chain for the moments at which the congestion is detected. With this model, we are able to account for correlation and burstiness in congestion moments. Furthermore, we specify several simple versions of our general model and then we identify their parameters from real TCP traces.

This special issue of Internet Mathematics is dedicated to the 6th International Workshop on Algorithms and Models for the Web Graph (WAW 2009), held at Barcelona, Spain, on February 12–13, 2009. The workshop has reported state-of-the-art achievements in the analysis of the World Wide Web and online social networking sites where the notion of a graph is central. The workshop program consisted of 14 regular refereed papers. The papers have been naturally clustered in three sections: “Graph Models for Complex Networks,” “PageRank and theWeb Graph,” and “Social Networks and Search.” The first section lays a foundation for theoretical and empirical analysis of the Web graph and Web 2.0 graphs. The second section analyzes random walks on the Web and Web 2.0 graphs and their applications. It is interesting to observe that the PageRank algorithm finds new exciting applications beyond now classical Web-page ranking. Nowadays, social networks are among the most popular applications on the Web. The third section of the workshop program is devoted to the design and performance evaluation of the algorithms for social networks. After the workshop, the authors were invited to submit an extended version of their work for this special issue. These extended papers were independently reviewed following the usual standards of Internet Mathematics. The papers selected for the special issue also represent well the three above-mentioned topics. The papers of P. Boldi, M. Santini, and S. Vigna; F. Chung, P. Horn, and L. Lu; and C. Karande, K. Chellapilla, and R. Andersen belong to the topic “Graph Models for Complex Networks.” The paper of F. Chung belongs to the topic “PageRank and the Web Graph.” The papers of A. Bonato, N. Hadi, P. Horn, P. Pralat, and C. Wang; and M. Gonen and Y. Shavitt belong to the topic “Social Networks and Search.” The paper of H. C. Lee and A. Borodin equally belongs to the last two topics. We would like to thank all the authors for their high-quality scientific contributions to the workshop and to this special issue, as well as all the reviewers who helped us to keep very high review standards. We would like to thank Andrei Broder, the general chair of WAW 2009, for his very valuable advice. We also would like to thank Charlotte Henderson for helping us to prepare this special volume.

We study singularly perturbed linear programs. These are parametric linear programs whose constraints become linearly dependent when the perturbation parameter goes to zero. Problems like that were studied by Jeroslow (1973). He proposed simplex-like method, which works over the field of rational functions. Here we develop an alternative asymptotic simplex method based on Laurent series expansions. This approach appears to be more computationally efficient. In addition, we point out several possible generalizations of our method and provide new simple updating formulae for the perturbed solution.

We discuss the sensitive discount optimality for Markov decision processes. The n-discount optimality is a refined selective criterion, that is a generalization of the average optimality and the bias optimality. Our approach is based on the system of nested linear programs. We provide an algorithm for the computation of the Blackwell optimal policy. The n-discount optimal policies are obtained as a by-product of this algorithm. Here we restrict ourselves to the case of completely ergodic Markov decision processes.

We consider properties of a null space of an analytically perturbed matrix. In particular, we obtain Taylor expansions for the eigenvectors which constitute a basis for the perturbed null space. Furthermore, we apply these results to the calculation of Puiseux expansion of the perturbed eigenvectors in the case of general eigenvalue problem as well as to the calculation of Laurent series expansions for the perturbed group inverse and pseudoinverse matrices.

International audience; Graph Semi-supervised learning (gSSL) aims to classify data exploiting two initial inputs: firstly, the data are structured in a network whose edges convey information on the proximity, in a wide sense, of two data points (e.g. correlation or spatial proximity) and, second, there is a partial information on some nodes, which have previously been labelled. Thus, the classification problem is usually a balance between two terms: one diffusing the information from the labelled points to the unlabelled ones through the network and another one that constrains the solution to be similar, on the labelled nodes, to the given labels. In practice, popular SSL methods as Standard Laplacian (SL), Normalized Laplacian (NL) or Page Rank (PR), exploit those operators defined on graphs to spread the labels and, from a random walk perspective, the classification of a given point is given the maximum of the expected number of visits from one class. Anomalous diffusion can alter the way a graph is "explored" and, therefore, it can alter classification performance. In a nushell, Lévy flights/walks are a way to create superdiffusive regimes: the customary rule for their ignition is to allow the walkers to perform non-local jumps, whose length is distributed according to a fat-tailed pdf with diverging second moment. Mathematically speaking, there have been several attempts to convert the Lévy flight phenomenon on networks and, in the context of gSSL, we settled to the use of fractional operators. Such operators are defined on the spectrum of the Standard Laplacian matrix by elevating it to some power γ: namely if the Laplacian reads L i,j = D i,j − A i,j , where D i,j is the diagonal matrix whose diagonal are the vertexes' degrees and A i,j is the adjacency matrix, then L γ = QΛ γ Q T , where Λ = diag(λ 0 ,. .. , λ N −1) are the eigenvalues and Q is the matrix whose columns are the eigenvectors. Such operators were investigated in [1, 2] and in such works it was shown that, indeed, they connect to a Lévy Flight type of process on graphs. Thus, in our SSL context, we cast those operators in the SSL problem in each different incarnation (SL, PR and NL) [3, 4] and we investigated the beneficial effect of such a procedure for classification, as displayed in Fig. 1. The L γ operator actually possesses two quite contrasting behaviours in the 0 < γ ≤ 1 and γ > 1 regimes: in the former, it is still a valid stochastic matrix (i.e. the off-diagonal terms are negative) and, therefore, it implies a random walk process. This random walk, in the Lévy Flight style, indeed performs long-range transitions and this enhanced and faster exploration allows for a better classification in cases in which the graph is badly constructed: for instance, in the figure, the existence of edges across the two moons spoils classification with the standard method, but we override this issue through the use of fractional methods. On the other hand, the γ > 1 regime, the operator L γ presents positive off-diagonal terms, so the associated graph, defined from the weights W γ i,j , has negative edges. Consequently, it is not possible anymore to draw a random walk process from it but one can still resort, for instance, to an anisotropic diffusion interpretation [5]. In this case, the effect of the operator is evident in traditionally problematic cases for standard methods, like very skewed and unbalanced ones, in which a class possesses more labels or it is denser edge-wise (Fig.1b). a b Fig. 1: (a) Classification of the Two Moons dataset with Page Rank and Fractional Page Rank. (b) Accuracy in classification for a dataset composed by connected modules with unbalanced labels. [1] Alejandro P. Riascos and José L. Mateos. Long-range navigation on complex networks using Lévy random walks. Phys. Rev.E, 86(5):056110, 2012. [2] Alejandro P. Riascos and José L. Mateos. Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights. Phys. Rev. E, 90(3):032809, 2014. flights for graph based semi-supervised classification. In 26th colloquium GRETSI, 2017. [5] Andrew V. Knyazev. Signed laplacian for spectral clustering revisited. arXiv preprint arXiv:1701.01394, 2017.

Game-Theoretic Models and Security; International audience; Nowadays energy saving and reduction of electromagnetic pollution become important issues. One approach to these problems is the introduction of taxes on the energy dissipation. In this paper we investigate a taxation game between a user or a provider or a group of users and the taxation authority. This is a Stackelberg game where the taxation authority acts as a leader and users or service providers act as followers. Clearly too big taxes will strongly discourage the user of wireless technology and hinder the progress and too small taxes will lead to a wasteful use of the energy resources and may also lead to reckless use of the radio resources. We study several important particular cases with complete and partial information. We focus on the problem of finding taxation strategy in closed form and investigating how incomplete information of authorities about users impacts the equilibrium strategy.

We propose an iterative learning control scheme based on the quasi-Newton method. The iterative learning control is designed to improve the performance of the systems working cyclically. We consider the general type of systems described by continuously differentiable operator acting in Banach spaces. The sufficient conditions for the convergence of quasi-Newton iterative learning algorithm are provided. We apply this general approach to the motion control of robotic manipulators. We also recommend to use the conventional feedback control in addition to the learning control. Finally, some simulation results are presented.

We consider Content Centric Network (CCN) interest forwarding problem as a Multi-Armed Bandit (MAB) problem with delays. We investigate the transient behaviour of the $\eps$-greedy, tuned $\eps$-greedy and Upper Confidence Bound (UCB) interest forwarding policies. Surprisingly, for all the three policies very short initial exploratory phase is needed. We demonstrate that the tuned $\eps$-greedy algorithm is nearly as good as the UCB algorithm, the best currently available algorithm. We prove the uniform logarithmic bound for the tuned $\eps$-greedy algorithm. In addition to its immediate application to CCN interest forwarding, the new theoretical results for MAB problem with delays represent significant theoretical advances in machine learning discipline., No. RR-7917 (2012)

Average consensus is an iterative protocol where nodes in a network, each having an initial scalar value called estimate, perform a distributed algorithm to calculate the average of all estimates presented in the network by using only local communication. With every iteration, nodes receive the estimates from their neighbors, and they update their own estimate by the weighted average of the received ones. While the average consensus protocol converges asymptotically to consensus, implementing a termination algorithm is challenging when nodes are not aware of some global information (e.g. the diameter of the network or the number of nodes presented). In this report, we are interested in decreasing the rate of the messages sent in the network as the estimates are closer to consensus. We propose a totally distributed algorithm for average consensus where nodes send more messages when the nodes have large differences in their estimates, and reduce their rate of sending messages when the consensus is almost reached. The convergence of the system is guaranteed to be within a predefined margin from the true average and the communication overhead is largely reduced.; Le consensus de moyenne est un protocole itératif où les nœuds d'un réseau, ayant chacun une estimation initiale, exécutent un algorithme distribué pour calculer la moyenne de ces estimations en utilisant uniquement les communication locales. A chaque itération, les nœuds échangent leurs estimations avec leurs voisins. Ces estimations seront remplacées par la moyenne pondérée de celles reçues. La convergence du consensus de moyenne est asymptotique et la mise en œuvre d'un protocole de terminaison est difficile lorsque les nœuds ne connaissent pas l'estimation global (par exemple, le diamètre du réseau ou le nombre de nœuds). Dans ce rapport, nous intéressons à la réduction du taux de messages envoyés dans le réseau quand les estimations deviennent proche du consensus. Nous présentons un algorithme de consensus de moyenne totalement distribué, où les nœuds envoient plus de messages lorsque la différence entre leurs estimations est grande et moins de messages lorsque le système est à peu prés convergeant. La convergence du système est garantie d'être proche de la vraie moyenne et le coût des communications est fortement réduit.

International audience; In many scenarios network design is not enforced by a central authority, but arises from the interactions of several self-interested agents. This is the case of the Internet, where connectivity is due to Autonomous Systems' choices, but also of overlay networks, where each user client can decide the set of connections to establish. Recent works have used game theory, and in particular the concept of Nash Equilibrium, to characterize stable networks created by a set of selfish agents. The majority of these works assume that users are completely non-cooperative, leading, in most cases, to inefficient equilibria. To improve efficiency, in this paper we propose two novel socially-aware network design games. In the first game we incorporate a socially-aware component in the users' utility functions, while in the second game we use additionally a Stackelberg (leader-follower) approach, where a leader (e.g., the network administrator) architects the desired network buying an appropriate subset of network's links, driving in this way the users to overall efficient Nash equilibria. We provide bounds on the Price of Anarchy and other efficiency measures, and study the performance of the proposed schemes in several network scenarios, including realistic topologies where players build an overlay on top of real Internet Service Provider networks. Numerical results demonstrate that (1) introducing some incentives to make users more sociallyaware is an effective solution to achieve stable and efficient networks in a distributed way, and (2) the proposed Stackelberg approach permits to achieve dramatic performance improvements, designing almost always the socially optimal network.

We provide the analysis of the Google PageRank from the perspective of the Markov Chain Theory. First we study the Google PageRank for a Web that can be decomposed into several connected components which do not have any links to each other. We show that in order to determine the Google PageRank for a completely decomposable Web, it is sufficient to compute a subPageRank for each of the connected components separately. Then, we study incentives for the Web users to form connected components. In particular, we show that there exists an optimal linking strategy that benefits a user with links inside its Web community and on the other hand inappropriate links penalize the Web users and their Web communities.

National audience; Classification through Graph-based semi-supervised learning algorithms can be viewed as a diffusion process with restart on the labels. In this work, we exploit this equivalence to introduce a novel algorithm which relies on the formulation of a non-local diffusion process, fueled by the γ-th power of the standard Laplacian matrix Lγ, with 0 < γ < 1. This approach allows to jump in one step between far apart nodes and such long-range transitions, called Lévy Flights, entail a wider exploration of the graph. In the present contribution, we embed such mechanism in graph based semi-supervised algorithms to improve the classification outcome, even in settings traditionally poorly performing such as unbalanced classes, and we derive a theoretical rule for classification decision.

International audience; A search engine uses a web crawler to crawl the pages from the world wide web (WWW) and aims to maintain its local cache as fresh as possible. Unfortunately, the rates at which different pages change in WWW are highly nonuniform and also, unknown in many real-life scenarios. In addition, the finite available bandwidth and possible server restrictions on crawling frequency make it very difficult for the crawler to find the optimal scheduling policy that maximises the freshness of the local cache. We model this problem in a multi-armed restless bandits framework, where each arm represents a web page or an aggregate of statistically identical web pages. The objective is to find the scheduling policy that gives the exact indices of the pages to be crawled at a particular instance. We provide an online learning scheme using deep reinforcement learning (DRL) framework which learns the unknown page change dynamics on the fly along with the optimal crawling policy. Finally, we run numerical simulations to compare our approach with state-of-the-art algorithms such as static optimisation and Thompson sampling. We observe better performance for DRL.

International audience; We propose a local message passing algorithm based on Belief Propagation (BP) to detect a small hidden Erdos-Renyi (ER) subgraph embedded in a larger sparse ER random graph in the presence of side-information. We consider side-information in the form of revealed subgraph nodes called cues, some of which may be erroneous. Namely, the revealed nodes may not all belong to the subgraph, and it is not known to the algorithm a priori which cues are correct and which are incorrect. We show that asymptotically as the graph size tends to infinity, the expected fraction of misclassified nodes approaches zero for any positive value of a parameter λ, which represents the effective Signal-to-Noise Ratio of the detection problem. Previous works on subgraph detection using BP without side-information showed that BP fails to recover the subgraph when λ < 1/e. Our results thus demonstrate the substantial gains in having even a small amount of side-information.

We present an analytical model for the calculation of network load and drop probabilities in a TCP/IP network with general topology. First we formulate our model as a nonlinear complementarity problem. Then we transform the model into two equivalent formulations: fixed point formulation and nonlinear programming formulation. These equivalent formulations provide efficient computational procedures for the solution of our model. Furthermore, with the help of the fixed point formulation we are able to prove the existence of a solution. Our model has the main advantage of not requiring the pre-definition of bottleneck links. The model also takes into account the receiver congestion window limitation. Our approach can be used for TCP/IP networks with drop tail buggers as well as for TCP/IP networks with active queue management buggers. We solve the problem for some network examples and we show how the distribution of load varies with network parameters. The distribution of load is sometimes counter-intuitive which cannot be detected by other models making prior assumptions on the locations of bottlenecks.

PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer and thus it reflects the popularity of a Web page. We study the effect of newly created links on Google PageRank. We discuss to what extend a page can control its PageRank. Using the asymptotic analysis we provide simple conditions that show if new links bring benefits to a Web page and its neighbors in terms of PageRank or they do not. Furthermore, we show that there exists an optimal linking strategy. We conclude that a Web page benefits from links inside its Web community and on the other hand irrelevant links penalize the Web pages and their Web communities.

Nowadays, graph-based semi-supervised learning (GB-SSL) is a fast-growing area of classifying nodes in a graph with an extremely low number of labelled nodes. However, the GB-SSL algorithms have two general limitations: the first is the memory/time complexity that arises in all state-of-the-art GB-SSL algorithms on extremely large graphs. In particular, the high memory consumption occurs in graph convolution networks and leads to Out of Memory (OOM) issues on GPU or RAM; the second one appears in all GB-SSL algorithms based on Laplacian regularization loss. This thesis' major contribution is divided into two parts in order to suggest strategies that would guarantee to avoid the restrictions mentioned above. In the first part of this thesis, we propose a novel linear algorithm called Markov-Batch Stochastic Approximation (MBSA) for solving Personalized PageRank. MBSA updates node batches and proposes a significantly better tradeoff between memory consumption and convergence rate for an optimal classification result than other linear models. Then, we propose a novel scaling graph convolution network, denoted as MBSA-NN, which embeds our linear MBSA. MBSA-NN avoids OOM issues and significantly reduces time and memory consumption on GPU and RAM. We applied MBSA-NN on several very large datasets, and we showed that it can handle graphs with more than 10M nodes and 2M of features in under one minute on one standard machine, including preprocessing, training and inference time. Furthermore, we show that it has significantly improved memory/time consumption and competitive accuracy concerning the latest best GB-SSL scaling algorithms. The second part of this thesis focuses on solutions to Laplacian regularization loss issues. For that reason, we propose a novel framework called Graph Diffusion & PCA (GDPCA). This framework combines a modified Principal Component Analysis with the classical supervised loss and Laplacian regularization loss. GDPCA allows handling the case where the adjacency matrix presents through Binary edges and avoids the Curse of dimensionality. Also, GDPCA can be applied to non-graph datasets, such as images, by constructing a similarity graph. Furthermore, we propose a framework that embeds PageRank SSL in a generative model (GenPR). GenPR joint training of nodes latent space representation and label spreading through the reweighted adjacency matrix by node similarities in the latent space. We demonstrate that a generative model can improve accuracy and reduce the number of iteration steps for PageRank SSL. Moreover, we show how to embed MBSA into the GenPR framework for providing the batch training regime of GenPR. Finally, we propose a flexible SSL framework based on stacking GDPCA and Zoetrope Genetic Programming algorithms into a novel framework: PaZoe. This self-labelling framework shows that graph-based and non-graph based algorithms jointly improve the quality of predictions and outperform each component taken alone. We also show that PaZoe outperforms state-of-the-art SSL algorithms on real datasets. Note that one of the datasets was generated in house, taking data from industrial graded equipment to mimic DC motors during operation.; De nos jours, l'apprentissage semi-supervisé basé sur les graphes (GB-SSL) est un domaine en plein essor pour classer les nœuds d'un graphe avec un nombre extrêmement faible de nœuds labélisés. Cependant, les algorithmes GB-SSL ont deux limites générales: la première est la complexité mémoire/temps qui se présente dans tous les algorithmes GB-SSL de pointe sur de larges graphes. En particulier, la forte consommation de mémoire se produit dans les réseaux de convolution de graphes et conduit à des problèmes d'OOM (Out of Memory) sur GPU ou RAM; la seconde apparaît dans tous les algorithmes GB-SSL basés sur la perte de régularisation Laplacienne. La contribution majeure de cette thèse est divisée en deux parties afin de proposer des stratégies qui garantiraient d'éviter les restrictions mentionnées ci-dessus. Dans la première partie de cette thèse, nous proposons un nouvel algorithme linéaire appelé Markov-Batch Stochastic Approximation (MBSA) pour résoudre le PageRank Personnalisé. MBSA met à jour des lots de nœuds et propose un compromis significativement meilleur que les autres modèles linéaires entre la consommation de mémoire et le taux de convergence pour un résultat de classification optimal. Ensuite, nous proposons un nouveau réseau de convolution de graphes à échelle, appelé MBSA-NN, qui intègre notre MBSA linéaire. Le MBSA-NN évite les problèmes d'OOM et réduit considérablement la consommation de temps et de mémoire sur GPU et RAM. Nous avons appliqué le MBSA-NN à plusieurs grands ensembles de données, et nous avons montré qu'il peut traiter des graphes avec plus de 10M nœuds et 2M de caractéristiques en une minute sur une machine standard, y compris le temps de prétraitement, d'apprentissage et d'inférence. De plus, nous montrons qu'il a une consommation mémoire/temps significativement améliorée et une précision compétitive par rapport aux meilleurs algorithmes de mise à l'échelle GB-SSL les plus récents.La deuxième partie de cette thèse se concentre sur les solutions aux problèmes de perte de régularisation du Laplacien. Pour cette raison, nous proposons un nouveau cadre appelé Graph Diffusion & PCA (GDPCA). Ce cadre combine une analyse en composantes principales modifiée avec la perte supervisée classique et la perte de régularisation laplacienne. GDPCA permet de traiter le cas où la matrice d'adjacence présente des Arêtes binaires et évite la Malédiction de la dimensionnalité. De plus, GDPCA peut être appliqué à des ensembles de données non graphiques, tels que des images, en construisant un graphe de similarité. En outre, nous proposons un cadre qui intègre PageRank SSL dans un modèle génératif (GenPR). GenPR joint l'entraînement de la représentation de l'espace latent des nœuds et la propagation des labels à travers la matrice d'adjacence repondérée par les similarités des nœuds dans l'espace latent. Nous démontrons qu'un modèle génératif peut améliorer la précision et réduire le nombre d'étapes d'itération pour PageRank SSL. En outre, nous montrons comment intégrer MBSA dans le cadre de GenPR pour fournir le régime de formation par lots de GenPR. Enfin, nous proposons un cadre SSL flexible basé sur l'empilement des algorithmes GDPCA et de Zoetrope Genetic Programming dans un nouveau cadre : PaZoe. Ce cadre d'auto-labélisation montre que les algorithmes basés sur les graphes et les algorithmes non basés sur les graphes améliorent conjointement la qualité des prédictions et sont plus performants que chaque composant pris séparément. Nous montrons également que PaZoe surpasse les algorithmes SSL de pointe sur des jeux de données réels. Notez que l'un des ensembles de données a été généré par nos soins, en prenant les données d'un équipement industriel classé pour imiter les moteurs à courant continu pendant leur fonctionnement.

The massive explosion of data collection led to a multi-disciplinary interest in the statistical inference of complex systems. In these systems, agents interact by pairs. Since similar agents tend to interact similarly, an important unsupervised learning problem consists of grouping the agents into communities or clusters based on the pairwise interactions. This thesis explore various aspects of this learning task.In particular, we study random graph models in which each node belong to a community (also called block) and the interactions between node pairs depend on the community structure. For those stochastic block models, we establish consistency thresholds for community recovery. These results allow for non-binary interactions, such as weighted, temporal or multiplex networks. In particular, it shows that in temporal networks with Markov interactions, consistent recovery of communities can be achieved for very sparse interactions, provided that the number of snapshots is large enough.We propose several algorithms for clustering temporal networks, such as spectral methods based on the persisting edges, or methods based on an online computation of the likelihood.We also study graph clustering in a semi-supervised setting. In this setting, an oracle provides the community memberships of a few nodes. This extra information helps to recover the community labels of the rest of the nodes.Finally, we investigate networks in which the nodes have a position in a metric space. In such geometric networks, we show that standard spectral methods (such as Spectral Clustering) fail at recovering the communities. We propose and analyze a spectral algorithm based on a higher-order eigenvector.; La multiplication des données collectées a occasionné un intérêt multi-disciplinaire autour de l'étude statistique de systèmes complexes où les individus interagissent en pairs. Dans de tels réseaux, des individus similaires ont tendance à interagir similairement. Un important problème d'inférence statistique consiste donc à regrouper les individus similaires en communautés (aussi appelées clusters) en se basant uniquement sur l'observation des interactions entre individus. Ce problème d'apprentissage non-supervisé qui consiste à placer chaque nœud dans un groupe est appelé détection des communautés. Cette thèse a pour but d'étudier différents aspects de la détection de communauté dans des systèmes complexes.En particulier, nous étudions des modèles de graphes aléatoires où chaque nœud appartient à une communauté (aussi appelé bloc) et où l'interaction entre deux nœuds dépend uniquement des blocs dans lesquels ces deux nœuds appartiennent. Pour ces modèles, nous établissons des résultats théoriques sur la possibilité et l'impossibilité de découverte des communautés. Notre étude autorise des interactions quelconques (non nécessairement binaires), ce qui rend le résultat applicable à de nombreuses situations (interaction pondérées, temporelles, multi-couches, etc.). Dans le cas particulier d'un réseau temporel où les interactions sont markoviennes, nous montrons que si le nombre d'instants temporels est assez large, les communautés peuvent être estimées de manière consistante même lorsque les interactions sont très diluées.Dans le cas particulier où les interactions entre les nœuds varient au cours du temps, nous proposons plusieurs algorithmes. Plus précisément, nous présentons des méthodes spectrales utilisant les interactions persistantes ou des méthodes basées sur un calcul itératif de la vraisemblance.Nous examinons aussi le problème de la détection semi-supervisées des communauté. Dans ce cas, un oracle nous renseigne sur la communauté d'un petit nombre de nœuds. Ces renseignements s'ajoutent aux interactions observées entre les nœuds, et facilitent le problème initial (l'apprentissage des communautés des nœuds).Enfin, nous étudions la situation où les nœuds sont positionnés dans un espace métrique. Dans ce cas, nous montrons que les méthodes spectrales classiques (telles que Spectral Clustering) peuvent totalement échouer, et nous analysons une parade basée sur la sélection de vecteurs propres d'ordre supérieur.

We study random geometric graphs (RGGs) to address key problems in complex networks. An RGG is constructed by uniformly distributing n nodes on a torus of dimension d and connecting two nodes if their distance does not exceed a certain threshold. Three regimes for RGGs are of particular interest. The connectivity regime in which the average vertex degree a_n grows logarithmically with n or faster. The dense regime in which a_n is linear with n. The thermodynamic regime in which a_n is a constant. We study the spectrum of RGGs normalized Laplacian (LN) and its regularized version in the three regimes. When d is fixed and n tends to infinity we prove that the limiting spectral distribution (LSD) of LN converges to Dirac distribution at 1 in the connectivity regime. In the thermodynamic regime we propose an approximation for LSD of the regularized NL and we provide an error bound on the approximation. We show that LSD of the regularized LN of an RGG is approximated by LSD of the regularized LN of a deterministic geometric graph (DGG). We study LSD of RGGs adjacency matrix in the connectivity regime. Under some conditions on a_n we show that LSD of DGGs adjacency matrix is a good approximation for LSD of RGGs for n large. We determine the spectral dimension (SD) that characterizes the return time distribution of a random walk on RGGs. We show that SD depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the neighborhood of the minimum eigenvalues. Based on the analytical eigenvalues of the normalized Laplacian we show that ED in a neighborhood of the minimum value follows a power-law tail and we approximate SD of RGGs by d in the thermodynamic regime.; Nous étudions le graphe géométrique aléatoire (GGA) afin d'aborder des problèmes clés dans les réseaux complexes. Un GAA est construit en distribuant uniformément n nœuds sur un tore de dimension d et en connectant deux nœuds si leur distance ne dépasse pas un seuil. Trois régimes pour GGA présentent un intérêt particulier. Le régime de connectivité dans lequel le degré moyen d'un nœud a_n croît de manière logarithmique avec n ou plus vite. Le régime dense dans lequel a_n est linéaire avec n. Le régime thermodynamique dans lequel a_n est une constante. On étudie le spectre du Laplacien normalisé (LN) et régularisé du GGA dans les trois régimes. Lorsque d est fixe et n tend vers l'infini, on prouve que la distribution spectrale limite (DSL) du LN converge vers la distribution de Dirac concentrée en 1 dans le régime de connectivité. Dans le régime thermodynamique, on propose une approximation pour DSL du LN régularisé et on fournit une borne d'erreur sur l'approximation. On montre que DSL du LN régularisé d'un GGA est approximée par DSL d'un graphe géométrique déterministe (GGD). On étudie DSL de la matrice d'adjacence d'un GGA dans le régime de connectivité. Sous des conditions sur a_n, on montre que DSL de la matrice d'adjacence du GGD est une bonne approximation du GGA pour n large. On détermine la dimension spectrale (DS) qui caractérise la distribution du temps de retour d'une marche aléatoire sur le GGA. On montre que DS dépend de la densité spectrale de LN au voisinage des valeurs propres minimales. On prouve que la densité spectrale au voisinage de la valeur minimale suit une loi de puissance et que DS du GGA est approximé par d dans le régime thermodynamique.

We study random geometric graphs (RGGs) to address key problems in complex networks. An RGG is constructed by uniformly distributing n nodes on a torus of dimension d and connecting two nodes if their distance does not exceed a certain threshold. Three regimes for RGGs are of particular interest. The connectivity regime in which the average vertex degree a_n grows logarithmically with n or faster. The dense regime in which a_n is linear with n. The thermodynamic regime in which a_n is a constant. We study the spectrum of RGGs normalized Laplacian (LN) and its regularized version in the three regimes. When d is fixed and n tends to infinity we prove that the limiting spectral distribution (LSD) of LN converges to Dirac distribution at 1 in the connectivity regime. In the thermodynamic regime we propose an approximation for LSD of the regularized NL and we provide an error bound on the approximation. We show that LSD of the regularized LN of an RGG is approximated by LSD of the regularized LN of a deterministic geometric graph (DGG). We study LSD of RGGs adjacency matrix in the connectivity regime. Under some conditions on a_n we show that LSD of DGGs adjacency matrix is a good approximation for LSD of RGGs for n large. We determine the spectral dimension (SD) that characterizes the return time distribution of a random walk on RGGs. We show that SD depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the neighborhood of the minimum eigenvalues. Based on the analytical eigenvalues of the normalized Laplacian we show that ED in a neighborhood of the minimum value follows a power-law tail and we approximate SD of RGGs by d in the thermodynamic regime., Nous étudions le graphe géométrique aléatoire (GGA) afin d'aborder des problèmes clés dans les réseaux complexes. Un GAA est construit en distribuant uniformément n nœuds sur un tore de dimension d et en connectant deux nœuds si leur distance ne dépasse pas un seuil. Trois régimes pour GGA présentent un intérêt particulier. Le régime de connectivité dans lequel le degré moyen d'un nœud a_n croît de manière logarithmique avec n ou plus vite. Le régime dense dans lequel a_n est linéaire avec n. Le régime thermodynamique dans lequel a_n est une constante. On étudie le spectre du Laplacien normalisé (LN) et régularisé du GGA dans les trois régimes. Lorsque d est fixe et n tend vers l'infini, on prouve que la distribution spectrale limite (DSL) du LN converge vers la distribution de Dirac concentrée en 1 dans le régime de connectivité. Dans le régime thermodynamique, on propose une approximation pour DSL du LN régularisé et on fournit une borne d'erreur sur l'approximation. On montre que DSL du LN régularisé d'un GGA est approximée par DSL d'un graphe géométrique déterministe (GGD). On étudie DSL de la matrice d'adjacence d'un GGA dans le régime de connectivité. Sous des conditions sur a_n, on montre que DSL de la matrice d'adjacence du GGD est une bonne approximation du GGA pour n large. On détermine la dimension spectrale (DS) qui caractérise la distribution du temps de retour d'une marche aléatoire sur le GGA. On montre que DS dépend de la densité spectrale de LN au voisinage des valeurs propres minimales. On prouve que la densité spectrale au voisinage de la valeur minimale suit une loi de puissance et que DS du GGA est approximé par d dans le régime thermodynamique.

International audience In this work we want to extend the EGT models by introducing the concept of individual state. We analyze a particular simple case, in which we associate a state to each player, and we suppose that this state determines the set of available actions. We consider deterministic stationary policies and we suppose that the choice of a policy determines the fitness of the player and it impacts the evolution of the state. We define the interdependent dynamics of states and policies and we introduce the State Policy coupled Dynamics (SPcD) in order to study the evolution of the population profile and we prove the relation between the rest points of our system and the equilibria of the game. We then assume that the processes of states and policies move with different velocities: this assumption allows us to solve the system and then to find the equilibria of our game with two different methods: the singular perturbation method and a matrix approach. 93

In this dissertation, we deal with the design of algorithms to tackle the α-fair resource allocation problem in real-time and distributed Software-Defined Networks (SDN). First, we define three major requirements that picture the challenges of real-time algorithms implementable in modern distributed SDN controllers. Those challenges are the ability to provide feasible resource allocations at all times, good transient solutions in terms of optimality gap that converge in an acceptable number of inter-controller communication rounds, and their ability of being massively parallelized independently of the network architecture. We use the Alternating Directions Method of Multipliers to design an algorithm that simultaneously, and unprecedentedly, tackles the three challenges. Motivated by a first study of the structural properties of the α-fair model, where we derive a lower bound on the optimal solution, we tune the penalty parameter of the augmented Lagrangian of the problem in order to optimize the algorithm’s performance. We show that the algorithm can function in real-time when the traffic requirements can vary more or less abruptly. The variation of the traffic requirements are modeled by real-time varying coefficients of the optimization model that is solved on-the-fly and may represent various prioritization policies of the traffic (payment, traffic type, number of connections within a tunnel, etc). Then, we describe how to extend the algorithm to real world use cases with limited modifications to cope with multi-path load balancing and online adjustments. Furthermore, we address the problem of α-fairness when the environment is uncertain and the available amount of resources over the network links is known only through general density functions. The main focus there is, instead of feasibility, the notion of safety. We design a heuristic that polishes an outer relaxation of the problem, based on the sensitivity analysis of the static problem. In general, we are able to provide a safe and acceptably efficient solution by solving several static problems., Dans cette thèse, nous étudions la conception d’algorithmes dédiés au calcul de l’allocation de ressources α-équitable en temps réel dans les réseaux Software Defined Networks (SDN) distribués. En premier lieu, nous définissons trois besoins majeurs établissant les enjeux des algorithmes en temps réel implémentable dans les contrôleurs distribués SDN. Ces enjeux sont la disponibilité de solutions faisables à tout moment, une qualité transitoire acceptable en termes d’écart à l’optimum, une convergence en un nombre raisonnable de tours de communications entre les différents contrôleurs, ainsi qu’une facilité des algorithmes à être massivement parallèles, indépendamment de l’architecture SDN du réseau. Nous utilisons les outils de l’Alternating Directions Method of Multipliers afin de définir une classe d’algorithmes qui, sans précédent, répondent simultanément à ces enjeux. À la lumière des propriétés structurelles du modèle de l’allocation α-fair, nous calculons une borne inférieure sur la solution optimale et l’utilisons afin d’ajuster le paramètre de pénalité du Lagrangien augmenté du problème dans le but d’optimiser la performance des algorithmes. Nous montrons que l’algorithme est capable de fonctionner en temps réel lorsque les exigences du trafic varient de façon plus ou moins brute. La variation des exigences du trafic est modelisée par la variation en temps réel de certains coefficients du modèle d’optimisation qui est résolu à la volée. Ces coefficients représentent en pratique des politiques de priorité variées au sein du trafic (paiement, type de trafic, nombre de connections à l’intérieur d’un chemin, etc). Ensuite, nous décrivons comment étendre l’algorithme à des scenarios réels avec des modifications minimes, afin de prendre en compte l’équilibrage en multi-chemin des flots et l’ajustement de la bande passante en temps réel. Par ailleurs, nous répondons au problème de partage de ressources α-équitable lorsque l’environnement admet des incertitudes sur la quantité de ressources disponibles sur chaque lien, connue uniquement au travers de fonctions de densités générales. L’axe prioritaire est alors, au lieu de la faisabilité, la notion de fiabilité. Nous concevons alors une heuristique qui affine une approximation extérieure du problème en se basant sur l’analyse de sensibilité du problème statique. En toute généralité, nous arrivons à fournir une solution fiable et acceptable en termes d’efficacité en résolvant quelques problèmes statiques.

International audience This chapter presents a new formulation which not only covers the fully non-cooperative behavior and the fully cooperative behavior, but also the fully altruistic behaviour. To do so, we make use of the evolutionary game theory which we extend to cover this kind of behavior. The major focus of this work is to study how the level of cooperation impacts the profile of population as well as the global performance of the system. equilibrium of the system through the notion of Evolutionary Stable Strategies and study the effect of transmission cost and cooperation level. We define and characterize the equilibrium (called Evolutionary Stable Strategy) for these games and establish the optimal level of cooperation that maximizes the probability of successful transmission. Our theoretical results unveil some behaviors. More specifically, we show that when all users increase their level of cooperation, then the performance of the system is not necessary improved. In fact, for some scenarios, the performance of groups may lead to an improvement by adopting selfishness instead of altruism. This happened when the density of agents is high. For low density, the degree of cooperation may indeed improve the performance of all groups. According to the structure of the ESS, we try to evaluate the performance of the global system in order to derive the optimal degree of cooperation. In this chapter, we explore our finding to study multiple access games with a large population of mobiles decomposed into several groups. Mobiles interfere with each others through many local interactions. We assume that each mobile 25

In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure., Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté.

The recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques; L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseau

Consensus protocols have gained a lot of interest in the recent years. In this thesis, we study optimization, control, and game theoretical problems arising in consensus protocols. First, we study optimization techniques for weight selection problems to increase the speed of convergence of discrete-time consensus protocols on networks. We propose to select the weights by applying an approximation algorithm: minimizing the Schatten p-norm of the weight matrix. We characterize the approximation error and we show that the proposed algorithm has the advantage that it can be solved in a totally distributed way. Then we propose a game theoretical framework for an adversary that can add noise to the weights used by averaging protocols to drive the system away from consensus. We give the optimal strategies for the game players (the adversary and the network designer) and we show that a saddle-point equilibrium exists in mixed strategies. We also analyze the performance of distributed averaging algorithms where the information exchanged between neighboring agents is subject to deterministic uniform quantization (e.g., when real values sent by nodes to their neighbors are truncated). Consensus algorithms require that nodes exchange messages persistently to reach asymptotically consensus. We propose a distributed algorithm that reduces the communication overhead while still guaranteeing convergence to consensus. Finally, we propose a score metric that evaluates the quality of clusters such that the faster the random walk mixes in the cluster and the slower it escapes, the higher is the score. A local clustering algorithm based on this metric is proposed.; Les protocoles de consensus ont gagné beaucoup d’intérêt ces dernières années. Dans cette thèse, nous étudions les problèmes d’optimisation, de contrôle, et de théorie de jeu qui se posent dans ces protocoles. Tout d’abord, nous étudions les techniques d’optimisation pour des problèmes de sélection de poids permettant ainsi d’augmenter la vitesse de convergence de protocoles de consensus dans les réseaux. Nous proposons de sélectionner les poids en appliquant un algorithme d’approximation: minimisation de la norme p de Schatten de la matrice de poids. Nous caractérisons l’erreur induite par cette approximation et nous montrons que l’algorithme proposé a l’avantage qu’il peut être soit résolu de façon distribuée. Ensuite, nous proposons un cadre conceptuel d’analyse des jeux d’adversaire qui peut ajouter du bruit aux poids utilisés par l’algorithme de consensus de moyenne afin d’éloigner le système de consensus. Nous analysons également la performance des algorithmes de consensus de moyenne où les informations échangées entre les agents voisins sont soumises à la quantification uniforme déterministe (les valeurs réelles envoyées par les nœuds de leurs voisins sont tronquées). Le problème de la terminaison des protocoles de consensus s’avère difficile dans le cadre distribué. Nous proposons un algorithme distribué pour la terminaison des protocoles de consensus. L’algorithme réduit la charge de communication tout en garantissant la convergence vers un consensus. Enfin, nous proposons une mesure de similarité qui évalue la qualité d’un regroupement (clustering) des nœuds dans un réseau. Un algorithme local de clustering basé sur cette métrique est donné.

International audience; We propose a model to analyze the decisions taken by an Autonomous System (AS) when joining the Internet. We first define a realistic model for the interconnection costs incurred and then we use this cost model to perform a game theoretic analysis of the decisions related to the creation of new links in the Internet. The proposed model doesn't fall into the standard category of routing games, hence we devise new tools to solve it by exploiting peculiar properties of our game. We prove analytically the existence of multiple equilibria for specific cases, and provide an algorithm to compute the stable ones. The analysis of the model's outcome highlights the existence of a Price of Anarchy (PoA) and a Price of Stability (PoS), originated by the non-cooperative behavior of the ASes, which optimize their cost function in a selfish and decentralized manner. We further observe the presence of competition between the facilities providing either transit or peering connectivity, caused by the cost differences between these two interconnection strategies.