Fundamentals of Networks  (FON) Session 1

Abstract: In this talk I will sketch a body of recent results obtained in the context of stochastic networks of dependently operating resources. These could be thought of to represent real-life networks of all sorts, such as traffic or communication networks, but I?ll point out that this setup is also highly relevant in economic and biological applications. The underlying model can be thought of as a network of interacting resources, which can be modeled in a discrete state-space context through coupled queues, and in a continuous state-space context through specific systems of stochastic differential equations; the individual resources operate dependently as they react to the same environmental process. For such large networks, one would typically like to describe their dynamic behavior, and to devise procedures that can deal with various undesired events (link failures, sudden overload, etc.). I?ll show how for systems that do not allow explicit analyses, various parameter scalings help shedding light on their behavior. More specifically, I'll discuss situations in which the time-scale corresponding to the fluctuations of the available resources differs from that of the fluctuations of the customer's demand, leading to various appealing limit results. Close

Abstract: Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks, making these networks highly inhomogeneous. Such networks are typically modeled using random graphs with power-law degree sequences. In this lecture, we will investigate the behavior of competition processes on scale-free random graphs with finite-mean, but infinite-variance degrees. Take two vertices uniformly at random, or at either side of an edge chosen uniformly at random, and place an individual of two distinct types at these two vertices. Equip the edges with traversal times, which could be different for the two types. Then let each of the two types invade the graph, such that any other vertex can only be occupied by the types that gets there first. Let the speed of the types be the inverse of the expected traversal times of an edge by that types. We distinguish two cases. When the traversal times are exponential, we see that one (not necessarily the faster) types will occupy almost all vertices, while the losing types only occupied a bounded number of vertices, i.e., the winner takes it all, the loser's standing small. In particular, no asymptotic coexistence can occur. On the other hand, for deterministic traversal times, the fastest types always gets the majority of the vertices, while the other occupies a subpolynomial number. When the speeds are the same, asymptotic coexistence (in the sense that both types occupy a positive proportion of the vertices) occurs with positive probability. This lecture is based on joint work with Mia Deijfen, Julia Komjathy and Enrico Baroni, and builds on earlier work with Gerard Hooghiemstra, Shankar Bhamidi and Dmitri Znamenski. Close

Abstract: Two common features of many large real networks are that they are sparse and that they have strong clustering, i.e., large number of triangles homogeneously distributed across all nodes. In many growing networks for which historical data is available, the average degree and clustering are roughly independent of the growing network size. Recently, latent-space random graph models, also known as (soft) random geometric graphs, have been used successfully to model these features of real networks, to predict missing and future links in them, and to study their navigability, with applications ranging from designing optimal routing in the Internet, to identification of the information-transmission skeleton in the human brain. Yet it remains unclear if latent-space models are indeed adequate models of real networks, as these models may have properties that real networks do not have, or vice versa. We show that maximum-entropy random graphs in which the expected numbers of edges and triangles at every node are fixed to constants, are approximately soft random geometric graphs on the real line. The approximation is exact in the limit of standard random geometric graphs with a sharp connectivity threshold and strongest clustering. This result implies that a large number of triangles homogeneously distributed across all vertices is not only necessary but also a sufficient condition for the presence of a latent/effective metric space in large sparse networks. Strong clustering, ubiquitously observed in real networks, is thus a reflection of their latent geometry. Close

Abstract: It is generally believed that, in the thermodynamic limit, the microcanonical description as a function of energy coincides with the canonical description as a function of temperature. However, various examples of systems for which the microcanonical and canonical ensembles are not equivalent have been identified. A complete theory of this intriguing phenomenon is still missing. Here we show that ensemble nonequivalence can manifest itself also in random graphs with topological constraints. We find that, while graphs with a given number of links are ensemble equivalent, graphs with a given degree sequence are not. This result holds irrespective of whether the energy is nonadditive (as in unipartite graphs) or additive (as in bipartite graphs). In contrast with previous expectations, our results show that (1) physically, nonequivalence can be induced by an extensive number of local constraints, and not necessarily by long-range interactions or nonadditivity, (2) mathematically, nonequivalence is determined by a different large-deviation behavior of microcanonical and canonical probabilities for a single microstate, and not necessarily for almost all microstates. The latter criterion, which is entirely local, is not restricted to networks and holds in general. (joint work with Tiziano Squartini, Joey de Mol and Frank den Hollander) Close

Abstract: The mixing time of a Markov chain is the time it needs to approach its stationary distribution. For random walks on graphs, the characterisation of the mixing time has been the subject of intensive study. One of the motivations is the fact that the mixing time gives information about the geometry of the graph. In the last few years, much attention has been devoted to the analysis of mixing times for random walks on random graphs, which poses interesting challenges. Many real-world networks are dynamic in nature. It is therefore natural to study random walks on dynamic random graphs. In this talk we investigate what happens for simple random walk on a dynamic version of the configuration model in which, at each unit of time, a fraction $\alpha_n$ of the edges is randomly relocated, where $n$ is the number of nodes. For degree distributions that converge and have a second moment that is bounded in $n$, we show that the mixing time is of order $1/\sqrt{\alpha_n}$, provided $\lim_{n\to\infty} \alpha_n(\log n)^2=\infty$. We identify the sharp asymptotics of the mixing time when we additionally require that $\lim_{n\to\infty} \alpha_n=0$, and relate the relevant proportionality constant to the average probability of escape from the root by a simple random walk on an augmented Galton-Watson tree that is obtained by taking a Galton-Watson tree whose offspring distribution is the size-biased version of the limiting degree distribution and attaching to its root another Galton-Watson tree with the same offspring distribution. Proofs are based on a randomised stopping time argument in combination with coupling estimates. [Joint work with Luca Avena (Leiden), Hakan Guldas (Leiden) and Remco van der Hofstad (Eindhoven)] Close