{'fraction_non_alphanumeric': 0.03412430369753059, 'fraction_numerical': 0.01171103995789289, 'mean_word_length': 4.697151424287856, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Large Scale Cross-Correlations in Internet Traffic

The Internet is a complex network of interconnected routers and the existence of collective behavior such as congestion suggests that the correlations between different connections play a crucial role. It is thus critical to measure and quantify these correlations. We use methods of random matrix theory (RMT) to analyze the cross-correlation matrix C of information flow changes of 650 connections between 26 routers of the French scientific network `Renater'. We find that C has the universal properties of the Gaussian orthogonal ensemble of random matrices: The distribution of eigenvalues--up to a rescaling which exhibits a typical correlation time of the order 10 minutes--and the spacing distribution follow the predictions of RMT. There are some deviations for large eigenvalues which contain network-specific information and which identify genuine correlations between connections. The study of the most correlated connections reveals the existence of `active centers' which are exchanging information with a large number of routers thereby inducing correlations between the corresponding connections. These strong correlations could be a reason for the observed self-similarity in the WWW traffic.


I. INTRODUCTION
Internet connects different routers and servers using different operating systems and transport protocols. This intrinsic heterogeneity of the network added to the unpredictability of human practices [1] make the Internet inherently unreliable and its traffic complex [2,3,4,5,6]. Recently, there has been major advances in our understanding of the generic aspects of the Internet [7,8,9,10] and web [11,12,13,14,15,16] structure and development, revealing that these networks can exhibit emergent collective behavior characterized by scaling. Concerning data transport, most of the studies focus on properties at short time scales (usually < 1 min) or at the level of individual connections [2,17,18]. In particular, it has been shown that for wide-and local-area networks the self-similarity (for time correlations) applies. Possible reasons for this behavior were shown to be [17] the underlying distribution of WWW documents, the effects of user 'think time', and the addition of many such transfers.
Studies on statistical flow properties at a large scale [3,4,6,19] concentrate essentially on the phase transition from a 'fluid' regime to a 'congested' one for which the average packet travel time is very large [20]. The existence of such a collective behavior indicates the importance of spatial correlations between connections at a large scale in the system. In order to be able to understand and to model the traffic in the network, it is thus important to measure and to quantify the correlations between the flows in different connections.
In this paper, we analyze the correlations between different connections of a wide area network which is the French scientific network 'Renater'. We use random matrix theory (RMT) to study the corresponding empirical correlation matrix. RMT has been developed in the fifties for studying complex energy levels of heavy nuclei [21] and more recently it has also been used in the study of correlations of stocks [22,23] or statistics of atmospheric correlations [25].
We first demonstrate the validity of the universal predictions of RMT for the eigenvalue statistics of the crosscorrelation matrix. However, we observe some deviations compared to the minimal hypothesis of random independent time-series. These deviations from the universal predictions of RMT identify system-specific, non-random properties of the network providing clues about the nature of the underlying interactions. This result allows one to distinguish genuine correlations in the network which are not just due to noise.

A. Data studied
We use data from the French network 'Renater' [26] which has about 2 million users and which consists of about 30 interconnected routers (Fig. 1). Most Research institutes, technological, or educational institutions are connected to Renater.
The data consist of the real exchange flow (sum of Ftp, Telnet, Mail, Web browsing, etc.) between all routers even if there is not a direct (physical) link between all of them. For a connection (i, j) between routers i and j (i = j), F ij (t) (in bytes per 5 minutes) is the effective information flow at time t going out from i to j (the flow going from i to k via j is excluded from F ij ). For technical reasons, data for a few routers were not reliable and we analyzed data for 26 routers which amounts in 26 × 26 matrices F ij (t) given for every sampling time scale τ = 5 minutes during a two weeks period. We also exclude from the present study the internal flow F ii , and the nights for which the flow is essentially due to machine activity. We thus studied data for days (8am-6pm), which amounts to a total of N = 26 × 25 = 650 different connections given for L = 12 × 10 × 14days = 1680 time counts. We choose as a measure of the magnitude of the time-series fluctuations the growth rate defined as the logarithm of the ratio of successive counts for t = 0, · · · , (L − 1)τ . This measure has several nice properties. First, any multiplicative, time-independent sample bias cancels in the ratio. Second, this measure has a natural interpretation in terms of relative growth since for a small increase g ij (t) ≃ [F ij (t+∆t)−F ij (t)]/F ij (t) is simply the relative increment. A large value of this quantity reflects a large activity (i.e. a large flow variation), while a small value corresponds to an almost constant flow. This measure is thus independent from the volume of information exchanged and thus does not eliminate the 'small' routers. The study of volume flow exchange will be published elsewhere [32] and in the present paper the quantity g allows us to study more subtle effects such as the activity of a regional router, independently of its 'size' measured in terms of exchanged information volume.

B. Correlation matrix
The simplest measure of correlations between different connections (i, j) and (k, l) is the equal-time crosscorrelation matrix C which has elements where σ ij = g 2 ij − g ij 2 is the standard deviation of the flow growth rate of the connection (i, j) and · · · denotes a time average over the period studied. The correlation matrix is real symmetric and its elements are comprised between −1 (anti-correlated connections) and 1 (correlated connections), while a null value denotes statistical independence.
The quantities g ij /σ ij have (by construction) a variance equal to one and a zero mean (for a sufficiently long time). It is thus natural to compare our empirical results with a mutual independent time-series-the 'null' hypothesis-described by the correlation matrix where A (the so-called random Wishart matrix) is an N × L matrix containing N times series of L random independent elements with zero mean and unit variance (A t denotes the transpose of A). Each element of R can be written as R (ij)(kl) = a ij a kl where a ij (t) is a time series of independent elements with zero mean ( a ij = 0) and unit variance (σ ij = 1).

Eigenvalues
The probability distribution of the elements of C shows that most on the elements are positive (Fig. 2) which indicates a strong correlation among the whole network. For comparison, the elements of R are distributed according to a centered distribution with zero mean. We now study the statistical properties of C by applying RMT techniques. We first diagonalize C and obtain its eigenvalues λ k (k = 1, · · · , N ) which we sort from the largest to the smallest. We then calculate the eigenvalue distribution and compare it with the analytical result for a cross-correlation matrix generated from finite uncorrelated time series [28] The eigenvalue distribution of C is very different from Equ. (4) which predicts a finite range of eigenvalues depending on the ratio Q. The theoretical value is Q = 2.58 and we can reasonably fit the empirical curve with an effective value Q * = 1.1 (Fig. 3a). This effective value can be explained as resulting from time correlations in the traffic of the order of Q Q * ×τ ≃ 11 minutes. However, even this fit cannot reproduce the large eigenvalues observed: For Q * = 1.1 the theoretical eigenvalues are distributed in the interval 2.17 × 10 −3 ≤ λ k ≤ 3.82 while few-a total of order 20-measured eigenvalues (not all shown on the graph) are found above λ + (Q * ) = 3.82. The largest eigenvalue is of order λ 1 ≃ 200 namely approximately hundred times larger than the maximum eigenvalue predicted for uncorrelated time series. As we will see, the empirical distribution of eigenvector components for the large eigenvalues is 'flat', all components being of the same order. This suggests that the largest eigenvalues are associated with strong correlations among the network.
We also calculate the distribution of the nearestneighbor spacings s = λ k+1 − λ k . We compare the empirical distribution of nearest-neighbor spacings with the RMT predictions for real symmetric random matrices. This class of matrices shares universal properties with the ensemble of matrices whose elements are distributed according to a Gaussian probability measure-the Gaussian orthogonal ensemble (GOE). We find good agreement (Fig. 3b) between the empirical data and Wigner's surmise which indicates a 'level repulsion' existing in our system and means that the eigenvalues are correlated.

Eigenvectors and Inverse Participation Ratio
We now analyze the eigenvectors of C. We denote by u k the eigenvector associated to the eigenvalue λ k and if we normalize the eigenvectors such that u 2 k = N , it can be shown that in the Wishart case the components u of the eigenvectors are distributed according to the so-called Porter-Thomas distribution In agreement with this result we find that eigenvectors corresponding to most eigenvalues in the 'bulk' of the spectrum (λ k not too large) follow this prediction (Fig. 4a).
On the other hand, eigenvectors with eigenvalues outside the bulk (λ k ≥ λ + (Q * )) show marked deviations from the Gaussian distribution (Fig. 4b,c). In particular, the vector corresponding to the largest eigenvalue λ 1 deviates significantly from the Gaussian distribution predicted by RMT (Fig. 4b). This eigenvector is the signature of a collective behavior-the network itselffor which all connections are correlated. This effect was already observed in the framework of stock correlations, the largest eigenvalue being in this case the entire market [22,23,24].
The distribution of the components of an eigenvector contains information about the number of connections contributing to it. In order to distinguish between one eigenvector with approximately equal components and another with a small number of large components we use the inverse participation ratio (IPR) introduced in the context of localization theory [29,30] where u ki , i = 1, . . . , N = 650 are the components of eigenvector u k . When the components of a vector are of the same order and distributed according to Equ. (7), the average IPR is small and equal to 3/N whereas a vector with only few non zero components leads to a IPR of order unity. The quantity Υ k = 3/I k is thus a measure of the number of vector components significantly different from zero. We compared Υ k for our empirical results and for uncorrelated time series with the same values of (N, L) (Fig. 5). For the latter case, Υ k has small fluctuations around N = 650 indicating that all the vectors are extended [30] which means that almost all connections contribute to them. On the other hand, the empirical data show deviations of Υ k from N for the smallest and largest eigenvalues (except for the largest eigenvalue). In these cases, the number of contributing connections is much smaller than N ranging from a few connections to a few hundreds. These deviations of few orders of magnitude of I k from its average suggests that the vectors are localized [30] and that only a few connections contribute to them. As it will be illustrated on a simple example in the next section, these results have a clear meaning in the case of large eigenvalues for which the connections are correlated. In addition, it was also shown ( [24] and see below) that strongly correlated pairs of routers (which correspond to large components in the eigenvectors) also appear with a relative negative sign in the eigenvector for small eigenvalues. This explains why the lower band edge also displays localized vectors but there is no clear connection with the spectrum observed in localization in electronic systems [30].
In addition, our empirical results exhibit 'quasiextended' states in the center of the band. These states consist essentially of a group of ≃ 300 − 400 connections corresponding to eigenvalues of order 0.2 − 0.4.
The physical picture which emerges is thus the following. The largest eigenvalue has an eigenvector which Υ k=1 is of order N and thus represents the whole network. The eigenvectors which correspond to eigenvalues which deviate from pure random matrix theory correspond to genuine correlations in the network. We have shown that these 'deviating' eigenvectors (of the order of 20) have a small value of Υ k which means that these important correlations are localized and that a relatively small number of connections concentrate most of the activity [31].

Non-Universal Properties: Active Centers
The detail of the components of the 'deviating' eigenvectors give us information about the important correlations in the network. In particular, the largest components of the eigenvectors correspond to the most correlated connections. This can be seen on the simple following example of a 3 × 3 correlation matrix where c (resp. c ′ ) denotes the strength of the (1, 2) (resp. (2, 3)) correlation. If we denote the ratio of the correlation strengths η = c ′ /c, the eigenvectors u 1 , u 2 , and u 3 are respectively and correspond respectively to the eigenvalues (sorted in decreasing order) We thus see on this simple example that the components of the eigenvector u 1 (corresponding to the largest eigenvalue) identify the most correlated indices: For η ≪ 1, u 1 ≃ (1, 1, 0) and for η ≫ 1 one obtains u 1 ∝ (0, 1, 1). This remark shows that the eigenvectors are indeed important for identifying the most correlated connections in the network. We note that the large correlations are also reflected in the components-but with a relative minus sign-of the eigenvectors for small eigenvalues.
In the case of Renater, we have seen in the previous section that all the components of u 1 are positive which indicates a correlation among the whole network. Even if all the components of u 1 indicate correlations existing in the network, the simple example above shows that its largest components correspond to the most correlated connections. We thus looked at the largest components of u 1 . A first fact is that a connection (i, j) is always (strongly) correlated with the connection (j, i). This result is not surprising since for most operations (Web browsing, Telnet, etc), there is always a 'outgoing' flow which is a significant part of the 'incoming' flow.
In order to look for other causes of correlations we plot on Fig. (6) the histogram of occurrences h(i) of the router i in the set of the n most correlated connections (i, j) which are given by the first n components of the eigenvector u 1 corresponding to the largest eigenvalue. We compared the empirical results with the control case for increasing values of n (for n approaching the total number of components N = 650 all the connections appear and the histogram of occurrences is flat). We observe marked differences between these two cases. In particular, in the control case the histogram tends to be uniform while for Renater we observe persistent peaks. On the last plot (Fig. 6c), it is apparent that there are still some fluctuations in the control case but much less than in the empirical one. The persistency of peaks and the fact that they appear to be much larger than the average value suggest that it is very unlikely that they are just fluctuations due to noise. Therefore, not all routers appear in the most correlated connections and the peaks can thus be identified as important 'active centers'. These centers are exchanging information with many other routers thereby inducing correlations between these connections.
It is interesting to note that occurrence peaks also appear in the components of the other deviating eigenvectors and would thus also correspond to active centers but at a lower level of correlation.
At this stage, we would like to emphasize that this analysis highlights active center independently of the volume of information exchanged. Indeed, in a volume flow analysis the 'small' routers even very active are completely hidden by the 'big' routers which are receiving and emitting huge amounts of bytes.

III. CORRELATIONS AND SELF-SIMILARITY IN THE WWW
The Internet is an example of a complex network which shows existence of a collective behavior such as a phase transition to a congested regime [3]. An important discovery was also the power-law decay of time correlations [2]. This self-similarity is usually explained on the basis of underlying distributions of WWW document sizes, effect of user 'think time' and the addition of many such effects in a network [17].
The present study shows that strong correlations between different connections exist in the traffic network. This result together with the existence of a phase transition, the existence of a power law decay of time correlation suggests that the large-scale data traffic dynamics could be described by a set of simple coupled stochastic differential equation, such as the Langevin equations with random interactions [33]. The equation for the Internet activity on a given connection (i, j) would thus be where the function F is usually expanded for small g as [34] F (g) ≃ −rg − ug 3 (13) and describes the relaxation of a single isolated connection. The random noise ε is associated to the effect of users and the quantity J (ij)(kl) is the coupling between connections (ij) and (kl). In the absence of interaction, the correlation function < g(t)g(t + τ ) > decreases exponentially with a typical correlation time of order 1/r (for u = 0). When the coupling is strong enough, the system described by Equ. (12) undergoes a transition to an ordered state where all g's are centered around a non-zero value. At the transition point the correlation function is decaying as a power law [34]. In this model [Equ. (12)], the observed self-similarity in time is a consequence of the strong correlation existing in the network. This is in contrast with previous studies which explained the self-similarity as an effect of existing local power law distribution (such as the file size distribution). However, more data are needed for testing this hypothesis and the validity of Equ. (12) for the Internet traffic.

IV. CONCLUSIONS
In summary, the largest part of the correlation matrix of connections is random but also contains statistical information distinct from pure noise. The eigenvectors which correspond to eigenvalues outside of the RMT predictions contain information about genuine traffic correlation. In particular, the largest components of eigenvector u 1 (which corresponds to the largest eigenvalue) indicate the most correlated connections. We found different origins for the observed correlations. First, a connection (i, j) is always strongly correlated with (j, i) which is expected since for each process-such as web browsing for example-information is exchanged in both directions.
Second, it appears that in the set of the strongly correlated connections there is only a small number of different routers which participate in different connections thereby inducing correlations. This support the idea of the existence of active centers which are either very active or very visited. More work and data-on larger space and time scales-are needed in order to understand more thoroughly the existence of such centers which seem to play an important role in the network traffic.
The approach presented in this study thus seems to allow one to extract relevant correlations between different connections and might have potential applications to traffic management and optimization. In particular, this analysis focus on activity independently of the volume of information exchanged and can thus reveal some very active routers which are usually hidden by 'big' routers exchanging very large flows.
Finally, the existence of strong correlations together with the existence of a phase transition and power-law decaying autocorrelation function suggest that the Internet traffic is similar to a spin glass close to the critical point. In this hypothesis, the self-similarity appears naturally as the result of a collective behavior without resorting to pre-existing power laws.
We thank F. Baccelli for stimulating and interesting discussions. This work was supported by the Equipe Reseaux, Savoirs & Territoires, Ecole normale Supérieure, Paris.   3. (a) The probability density of the eigenvalues of the normalized cross-correlation matrix C for the 650 connections for a 2-weeks period. The results are reasonably fitted by the analytical result obtained for cross-correlation matrices generated from uncorrelated time series (solid line, obtained from Equ. 4 with Q * = 1.1). There are however very large eigenvalues (not shown), the largest one being of order 200. (b) Nearest-neighbor spacing distribution of the eigenvalues of C after unfolding using the Gaussian broadening procedure [27]. The solid line is the RMT prediction for the spacing distribution for the Gaussian orthogonal ensemble (GOE).   FIG. 6. Number of occurrences of routers in the n most correlated connections (There is a total of 26 routers i = 1, · · · , 27, the router 24 is excluded of the present study for technical reasons). In each plot, we compared the empirical results with the control case (histogram in red). The arrows indicate the two most frequent routers for Renater. In cases (a) n = 30 and (b) n = 50, it is clear that not all routers are participating equally. (c) Case n = 100. The control case still fluctuates around its average (which is 200/26 ≃ 7.70) but much less than the empirical case. This fact and the observed persistency for increasing n suggest that it is very unlikely that the empirical peaks are just fluctuations due to noise. These peaks corresponds probably to routers which are very active and which are exchanging information with many other routers, thereby inducing correlations in the network.