Statistical foundations for evolving networks

The last few years have witnessed an explosion in the amount of empirical data on real networks motivating an array of mathematical models for the evolution of such networks. Examples range from biological networks (brain networks of interacting neurons), information transmission (Internet), transportation, social networks and swarm intelligence and the evolution of self-organized behavior through the interactions of simple agents. This has stimulated vigorous activity in a multitude of fields, including biology, statistical physics, statistics, mathematics and computer science to understand these models and quantify their predictions and relevance to real systems.

The aim of these two lectures is to introduce researchers to one corner of this vast field, Dynamic networks: systems that evolve over time through probabilistic rules. The following two main themes will be pursued:

(I) Macroscopic connectivity and higher order structures: A host of real world networks have structural connectivity that evolves over time or structural connectivity arising indirectly owing to measurements on vertices in the network (for example time series measurements on vertices in the network resulting in correlation networks which are then thresholded to obtain a binary network representation). We will discuss various probabilistic techniques to understand asymptotic for such systems including both techniques from the world of sparse networks such as Aldous’s multiplicative coalescent as well as from the world of dense graph limits.

(II) Evolving networks and continuous time branching: The second lecture will study the so-called preferential attachment family of network models emphasizing one particular technical tool: continuous time branching processes. We will show how this technique leads to rigorous asymptotic descriptions to a number of problems in the statistical modeling of real world systems ranging from Twitter event networks to change point detection in evolving networks.

In this talk, we study certain statistical inference problems for interacting particles systems in a mean-field limit. By studying the fluctuations of the (properly normalised) data toward a deterministic limit that solves a nonlinear transport or parabolic equation, we take advantage of the limiting object structure to estimate nonparametrically the parameters of interests. Two typical examples of applications are: nonlinear Hawkes processes and McKean-Vlasov interacting diffusions.

Social networks are usually modeled as graphs, where edges between vertices represent friendship. There exist many graph models describing their statistical properties or the growth behaviour with an increasing number of vertices. Compared to that, antagonistic relationships are only rarely modeled and their structural properties are poorly understood. An important theory in the social sciences is the balance theory which predicts that social networks are locally balanced. This means that friends should have the same friends and the same enemies. If edges are signed (+ for friends, - for enemies), this translates for the graph to have more balanced triangles with an even number of negative edges, while all other triangles are deemed unbalanced.

Balance theory has received only little empirical evaluation, also because antagonistic relationships are infrequently measured and often biased. Previous statistical tests for balance are usually permutation tests, where the null hypothesis is a graph without balance. These tests always assume that negative and positive edges are interchangeable. Based on a novel dataset of signed networks, collected from 32 isolated, rural villages in Honduras, we show, however, empirically that the statistical properties of positive and negative edges are very different. This leads to inflated test statistics, wrongly indicating balance where it is not present.

We improve on this by introducing a new permutation test that incorporates the structure of negative edges. The new test is indeed more accurate at detecting balance than the old one, which is demonstrated in several examples. Moreover, we prove asymptotic normality of our test statistic under the null model. Compared to other permutation tests, this property does not follow from a combinatorial central limit theorem, but is instead based on stochastic monotonicity and a central limit theorem for random variables in a fixed Rademacher chaos. The results are illustrated for the dataset mentioned above. Using our test and contrary to previous results, we find that there is only marginal evidence for balance.

Most of the complex networks evolve over time and this can have substantial impact on the processes unfolding on them. We will give a brief overview of the very recent steps towards the asymptotic theory of evolving networks. In particular, we will discuss the ideas related to the graph limit theory. Partially based on joint work with Jiří Černý.

We focus on modeling the dynamic attributes of a dynamic network with a fixed number of vertices. These attributes are considered as time series which dependency structure is influenced by the underlying network. They are modeled by a multivariate doubly stochastic time series framework, that is we assume linear processes for which the coefficient matrices are stochastic processes themselves. We explicitly allow for dependence in the dynamics of the coefficient matrices as well as between the two stochastic processes driving the time series. This framework allows for a separate modeling of the attributes and the underlying network. In this setting, we define network autoregressive models and discuss their stationarity conditions. Furthermore, anestimation approach is discussed in a low- and high-dimensional setting and how this can be applied to forecasting. The finite sample behavior of the forecast approach is investigated. This approach is applied to real data whereby the goal is to forecast the GDP of 33 economies.

We will consider multivariate stochastic processes indexed either by vertices or pairs of vertices of a dynamic network. Under a dynamic network we understand a network with a fixed vertex set and an edge set which changes randomly over time. We will assume that the spatial dependence-structure of the processes is linked with the network in the following way: Two neighbouring vertices (or two adjacent pairs of vertices) are dependent, while we assume that the dependence decreases as the distance in the network increases. We make this intuition mathematically precise by considering three concepts based on correlation, beta-mixing with time-varying mixing-coefficients and conditional independence. Then, we will use these concepts in order to prove weak-dependence results, e.g. an exponential inequality, which might be of independent interest. In order to demonstrate the use of these concepts in an application we study the asymptotics (for growing networks) of a goodness of fit test in a dynamic interaction network model based on a multiplicative Cox-type hazard model. This model is then applied to bike-sharing data.