Assia Hamzaoui

Matthieu Latapy

Clémence Magnien

Detecting Events in the Dynamics of Ego-centered Measurements of the Internet Topology

Detecting events such as major routing changes or congestions in the dynamics of the internet topology is an important but challenging task. We explore here a top-down approach based on a notion of statistically significant events. It consists in identifying statistics which exhibit a homogeneous distribution with outliers, which correspond to events. We apply this approach to ego-centerd measurements of the internet topology (views obtained from a single monitor) and show that it succeeds in detecting meaningful events. Finally, we give some hints for the interpretation of such events in terms of network events.

I. INTRODUCTION

The study of the internet topology as obtained from measurements attracted recently much attention, see e.g. [START_REF] Guillaume | Relevance of massively distributed explorations of the internet topology: qualitative results[END_REF], [START_REF] Li | A firstprinciples approach to understanding the internet's router-level topology[END_REF], [START_REF] Magoniand | Analysis of the autonomous system network topology[END_REF]. One of the key challenges in this field is nowadays to describe the time evolution of this topology. However, getting information on this is extremely difficult, as our measurement abilities are limited [START_REF] Li | Towards a theory of scale-free graphs: Definition, properties,and implications[END_REF] and object's dynamics are very complex [START_REF] Augustin | Avoiding traceroute anomalies with paris traceroute[END_REF], [START_REF] Oliveira | Observing the evolution of internet as topology[END_REF], [START_REF] Albert | Topology of evolving networks: Local events and universality[END_REF], [START_REF] Lad | Inferring the origin of routing changes using link weights[END_REF], [START_REF] Latapy | A radar for the internet[END_REF], [START_REF] Magnien | Fast dynamics in internet topology: preliminary observations and explanations[END_REF].

In [START_REF] Latapy | A radar for the internet[END_REF], the authors propose to focus on a part of the topology, which they call an ego-centered view. It consists in what a single machine, called monitor, may see of the internet topology. It is basically captured by running traceroute measurements from the monitor to a given set of randomly chosen destinations, and iterating this process every few minutes. See Section III and [START_REF] Latapy | A radar for the internet[END_REF] for details.

This approach proved to be successful in capturing interesting information [START_REF] Magnien | Fast dynamics in internet topology: preliminary observations and explanations[END_REF], [START_REF] Latapy | A radar for the internet[END_REF]. One of the main perspective is to use it to try to detect events in the dynamics of egocentered views, which has not been explored yet. This would lead to insight on the routing (and routing trees) dynamics, and may have important applications in network security (one may monitor a part of the network, or the network around a given machine).

However, previous work has shown that the dynamics of ego-centered views is intense [START_REF] Magnien | Fast dynamics in internet topology: preliminary observations and explanations[END_REF], [START_REF] Augustin | Avoiding traceroute anomalies with paris traceroute[END_REF]: new nodes are continuously observed, load-balancing introduces frequent changes in paths, etc. Distinguishing events, i.e. abnormal dynamics in this data is therefore challenging. It may even be impossible, as many events may occur at the same time, and throughout the measurement. Conversely, it is not clear that some events are very different from others, and that ego-centered measurements allow to capture some.

We present here the first method to automatically and rigorously detect events in the dynamics of ego-centered views of the internet topology. Intuitively, the internet topology is subject to a substantive dynamics, which can be described as regular, and sometimes undergo deep and unusual changes, that we call events. For instance load balancing is a normal routing dynamics. In contrast, failures in some parts of the network, creating major links and congestions may be seen as events.

The bottom-up approach is a natural approach to study such events. It consists in the study of the system in detail in order to characterize what normal dynamics and events are expected, and then to search for traces of events. However this approach raises difficult problems: first it is not known what characterizes the dynamics, either normal or abnormal [START_REF] Brutlag | Aberrant behavior detection in time series for network monitoring[END_REF]. In addition, there are many different events [START_REF] Denning | A multilevel relational data model[END_REF], [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF], that cannot necessarily be identified [START_REF] Balachander | Sketch-based change detection: Methods, evaluation, and applications[END_REF]. Finally intuition on the dynamics and its effects often is misleading, as some experiments confirm [START_REF] Magnien | Fast dynamics in internet topology: preliminary observations and explanations[END_REF].

The other complementary approach is the top-down one. In this approach, one observes the object from the outside by measuring it, as it is done for a living organism for instance. After calculating various statistics, one may then define an event as a statistically significant anomaly. The advantage of this approach is that knowledge of the system is not essential as a first step (but it is necessary for event interpretation). Furthermore, this approach is general, once established, it may be applied to different case studies. Another strong point of this method is that it is rigorous and objective and can help to discover unexpected features of the dynamics. Finally, the topdown approach is very suitable for event detection in complex systems in the interest, and our goal in this paper is to explore it in the case of ego-centred measurements of the internet topology.

We describe our methodology in Section II. We present the internet topology data which we use in Section III. We apply the method in Sections IV to VI, considering different statistics. Finally, we present some interpretations in Section VII, which show that the detected events are indeed significant from a networking perspective.

II. METHODOLOGY

A first possible approach for event detection is bottom-up: from a knowledge of which events may occur on the internet, one may attempt to define statistics to monitor, and which would indicate such events. This supposes a good knowledge of the actual dynamics of the topology, though, and the impact that events have on it. It also means that one has to guess the impact events will have on measurements, although they are very partial and biased views of the whole internet. In addition, correlating these events to statistics may turn out to be very difficult.

It must be clear that the current situation makes this approach extremely difficult. Current knowledge of internet dynamics in general, and events occurring on it in particular is very limited [START_REF] Latapy | A radar for the internet[END_REF], [START_REF] Augustin | Measuring loadbalanced paths in the internet[END_REF], [START_REF] Magnien | Fast dynamics in internet topology: preliminary observations and explanations[END_REF], [START_REF] Govindan | An analysis of internet inter-domain topology and route stability[END_REF], [START_REF] Pansiot | Local and dynamic analysis of internet multicast router topology[END_REF], [START_REF] Park | Comparing static and dynamic measurements and models of the internet's AS topology[END_REF]. It is not known which impact routing changes or local failures have on the internet topology. There is no database giving the list of all events occurring on the network (even the events occurring in a single AS are rarely and poorly documented, see Section VII).

Finally, the bottom-up approach, though appealing, is extremely challenging, and it seems out of reach in our current knowledge of the internet topology and its dynamics.

We propose here a top-down approach for event detection in the dynamics of ego-centered views of internet topology. We first consider ego-centered measurements and define simple statistics which may capture key dynamics (Sections IV to VI). We then look for statistically significant events, i.e. situations in which the observed statistics deviate significantly from the ones usually observed [START_REF] Henry | Identification of Outliers[END_REF]. These will correspond to events, and interpreting them in terms of network events needs further examination (Section VII).

The key point of our method is therefore to be able to define statistics which allow event detection, i.e. which exhibit a clear notion of normal vs abnormal dynamics.

When one considers a statistics, three typical situations may occur:

• First, the observed values may be homogeneous, which means that they all have approximately the same value, and that we never observe a significant deviation from this behavior. In such cases, the statistics is of no help in detecting events: there is never a clear deviation from the normal value.

• The observed values may be heterogeneous by nature, which means that there is no normal value, and therefore no abnormal value indicating events.

• Finally, the observed values may be homogeneous but with some outliers, which indicate abnormal events from a statistical point of view. Therefore, we are interested in statistics which have a homogeneous behavior, but exhibit some outliers. When studying a statistic, we will observe its dynamics and the distribution of its values (i.e. for each x, the number of times the statistics has value x). We will then try to distinguish between the three kinds of situations above.

Studying such distributions and deciding on their nature however is a subtle task. We will use here two complementary approaches: manual inspection of the distributions by plotting them in various scales, and automatic fit to classical distributions which characterize the three behaviors of interest pointed out above.

In order to perform manual inspection we plot each distribution in lin-lin, lin-log and log-log scales. We moreover plot the inverse cumulative distributions (i.e. for each x, the number of times the statistics has value greater than x) which are often easier to read. The use of these three scales makes it possible to highlight exponential and polynomial decreases, which are hallmarks of homogeneity and heterogeneity respectively. This gives a first mean to gain insight on the distribution and the corresponding statistics.

Once a global shape has been identified in this way, one may try to fit the observed distributions to classical model distributions. One must keep in mind that many models may be considered. Moreover automatic fitting is a difficult task, and results may be misleading [START_REF] Wasserman | All of Statistics: A Concise Course in Statistical Inference[END_REF], [START_REF] Chen | The origin of power laws in internet topologies revisited[END_REF]. This is why we complement it with manual inspection of plots.

We consider here three typical model distributions, which correspond to the three situations described above: the normal distribution (i.e.

P (x) = 1 ν √ 2π e -1 2 ( x-µ ν ) 2
) is a typical homogeneous distribution with well defined mean µ and standard deviation ν, which has an exponential decrease; the powerlaw distribution (i.e. P (x) ∼ x -α ) is a typical heterogeneous distribution characterized by its exponent α and which has no normal value; and we model homogeneous distributions with outliers by first identifying possible outliers with Grubb's test [START_REF] Hawkins | Testing for Normality[END_REF], then removing them and fit the remaining distribution to the normal distribution as above.

We will perform all fits using the classical Maximum Likelihood Estimation (MLE) [START_REF] Scott R Eliason | Maximum Likelihood Estimation: Logic and Practice[END_REF]. Notice however that, in our context, the fit is not the outcome of greatest interest: we are interested in how much this fit is relevant. To estimate this, we use one of the widely used goodness of fit called Kolmogorov-Smirnov (KS) test [START_REF] William | Numerical Recipes: The Art of Scientific Computing[END_REF].

Finally our event detection method consists in the following steps:

• Define statistics which possibly allow event detection.

• Study the calculated statistics in order to keep those exhibiting homogeneous distributions with outliers. The detected outliers will characterize our statistically meaningful events.

• Explore the detected outliers, with view to interpret them in term of network events.

III. DATA

We use here the data described in [START_REF] Latapy | A radar for the internet[END_REF]. It consists in periodic ego-centered measurements of the internet topology: a monitor runs periodic traceroute like measurements towards a set of 3000 random targets, waits for 10 minutes, and iterates this (which is called a round of measurement). There is approximately four rounds of measurements per hour (approximately 100 per day). Such measurements were performed from more than 100 monitors (mainly PlanetLab machines [START_REF]The planetlab platform[END_REF]) and for several months. The obtained datasets are freely available [START_REF]Radar datasets[END_REF]. We computed the statistics on measurements from different monitors, and obtained similar results in all cases. We present in this paper statistics on representative cases.

IV. NUMBER OF NODES AT EACH ROUND

The first statistics that one may consider in order to study the dynamics of ego-centered views is naturally the number N i of nodes observed in each round i of measurement. We display it in Figure 1 This plot shows that the number of nodes at each round is rather stable with some exceptions. Most of the time, it oscillates close to a mean value slightly above 10 600. However, one may observe that this value changes near rounds 2 100 and 5 600: during some time after these rounds, the number of nodes oscillates close to a different value. In addition to these changes in the average value, the plot also exhibits sharp downward peaks. On the contrary, no upper peak is visible.

These observations are confirmed by the distribution of the value of N i and the goodness of fit test, see Figure 1. Indeed, the distribution reveals two distinct regimes, with many values around 10 050 and 10 600. Otherwise, the distribution is clearly homogeneous with outliers. The presence of abnormally low values (points on the left) but no abnormally high values corresponds the presence of downward peaks but no upward ones.

It must be clear that downward peaks, although they are very clear statistical outliers, bring little information: they may be caused by local connectivity failures, which have the effect that ego-centered views are (partly) blank during one or a few rounds. This kind of event is trivial.

On the contrary, an upward peak would indicate an interesting event: it would mean that we suddenly observe significantly more nodes at one round. However, there is no upper peak, which is a non-trivial fact: one may easily imagine scenario where such peaks would appear. Figure 1 shows that such scenario do not occur in practice. As a consequence, one cannot detect events by observing abnormally high values of N i .

Finally, the only notable dynamics in the number N i of nodes observed at each round are changes in the mean values around which it oscillates. We detect such changes as follows: we associate to each i the median of values N i to N i +100, that we denote by M i , then we define

D i = M i -M i -1.
We plot these values in Figure 2. It appears clearly that this method succeed in identifying events, i.e. outliers in D i distribution. Goodness of fit normal distribution 0.76231 normal distribution with outliers 0.98069 power law distribution 0.00241 Fig. 2. From top to bottom: N i and M i as functions of i (N i and M i actually overlap but we shifted up M i for readability); the variations D i of M i , the distribution and the inverse cumulative distribution of D i ; goodness of fit of the distribution with the three studied distributions models.

V. NUMBER OF NODES IN CONSECUTIVE ROUNDS

The fact that the number N i of nodes observed at each round is very stable does not mean that the observed nodes are always the same: consecutive rounds may see different ones. Such changes may be evidenced by observing the number N p i of distinct nodes in p consecutive rounds, for a given integer p. We display in Figure 3 the case p = 5 (top row). This plot shows that, like N i , N 5 i is very stable and oscillates around a mean value 1 . As expected, this value is larger than the one for N i , but it is far from 5 times larger. This shows that many nodes appear in several consecutive rounds. Moreover, upper peaks appear on this plot, which make it very different from the one of N i in Figure 1. The distribution and the goodness of fit test are presented in this same figure (middle and bottom rows): it confirms the presence of a clear mean value, but also points out clear statistical outliers, both abnormally low (as before) and abnormally high (which is new). This observation is important for event detection: there are specific times (pointed out by the peaks in Figure 3) at which an abnormal number of new nodes appear in a series of consecutive rounds. This gives a new way to detect statistically significant events.

!77777777 00000000 00000000 00000000 !88888888 00000000 00000000 00000000 !99999999 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 However, automatic detection using this approach is not trivial: as the observed mean value may change during time, and as upper peaks (which we want to detect) may be smaller than these variations of the mean, we may miss some events, and making the difference between a statistically sound event and normal dynamics may be difficult. In order to solve this problem, we observe the number of appearing nodes, i.e. the number of nodes observed in a series of rounds but not observed in the previous rounds. To do so, we consider two integers p and c (for previous and current, respectively) and compute for all i the number of distinct nodes which we observe in rounds i to i + c -1, but not in rounds ip to i -1, which we denote by a i . Notice that observing the number d i of disappearing nodes is also natural. We observed similar results for appearing and disappearing nodes, and so we focus here on appearing nodes. We considered wide ranges of possible values for c and p, and observed little difference, if any, as long as they were greater than 1 or 2 and lower than 100. We illustrate here the obtained results with p = 10 and c = 2, see Figure 4.

!
The obtained plot exhibits clear upper peaks, independent of the current mean value of N c i , which is confirmed by the distributions and the goodness of fit test. We obtain this way a method for automatic detection of statistically meaningful events, by considering outliers of the appearing nodes distribution as event.

VI. CONNECTED COMPONENTS

We have seen in the previous section that, at some particular moments, an abnormal number of nodes appear in our egocentered views of the Internet topology. However, we said nothing on their structure: are they scattered in the observed topology? are they grouped? or do they belong to several small groups?... Intuitively for instance, an important routing change may lead to the discovery of a new part of the network, which would be revealed by the appearance of nodes forming a connected component in our ego-centered views.

In order to investigate this, we study the connected components of newly appearing nodes. More precisely, for all i, we select the appearing nodes as defined above, and consider links observed between these nodes. We then compute the connected components of this graph, which we call connected components of appearing nodes. As in the previous section, we use p = 10 and c = 2, which give results representative of what we observed on wide ranges of these values.

We show in Figure 5 the number of connected components observed for all i, as well as the size of the largest one for all i, together with the distributions of these values and their goodness of fit test. The statistically abnormal events detected with the number of connected components statistics are the same as the ones detected in the previous section. This shows that events detected using the number of appearing nodes are events in which many connected components appear, among which at least a large one.

Observing connected components makes it possible to go further. Indeed, it has the advantage that, at each round, several values are observed: for all i several connected components !00000000 !11111111 00000000 00000000 !22222222 00000000 00000000 !33333333 00000000 00000000 !44444444 00000000 00000000 !55555555 00000000 00000000 !66666666 00000000 00000000 !77777777 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 55555555 00000000 00000000 !22222222 00000000 00000000 00000000 !22222222 55555555 00000000 00000000 !33333333 00000000 00000000 00000000 !33333333 55555555 00000000 00000000 !44444444 00000000 00000000 00000000 !44444444 55555555 00000000 00000000 !55555555 00000000 00000000 00000000 !55555555 55555555 00000000 00000000 !66666666 00000000 00000000 00000000 !00000000

!11111111 00000000 00000000 !22222222 00000000 00000000 !33333333 00000000 00000000 !44444444 00000000 00000000 !55555555 00000000 00000000 !66666666 00000000 00000000 !77777777 00000000 00000000 !88888888 00000000 00000000 !99999999 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 55555555 00000000 00000000 !22222222 00000000 00000000 00000000 !22222222 55555555 00000000 00000000 !33333333 00000000 00000000 00000000 !33333333 55555555 00000000 00000000 !44444444 00000000 00000000 00000000 !44444444 55555555 00000000 00000000 !55555555 00000000 00000000 00000000 !55555555 55555555 00000000 00000000 !66666666 00000000 00000000 00000000

!00000000

!11111111 00000000 00000000 00000000 !22222222 00000000 00000000 00000000 !33333333 00000000 00000000 00000000 !44444444 00000000 00000000 00000000 !55555555 00000000 00000000 00000000 !66666666 00000000 00000000 00000000 !77777777 00000000 00000000 00000000 !88888888 00000000 00000000 00000000 !99999999 00000000 00000000 00000000 !00000000 !11111111 00000000 00000000 !22222222 00000000 00000000 !33333333 00000000 00000000 !44444444 00000000 00000000 !55555555 00000000 00000000 !66666666 00000000 00000000 !77777777 00000000 00000000 !00000000

!55555555 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 00000000 !11111111 55555555 00000000 00000000 00000000 00000000 !22222222 00000000 00000000 00000000 00000000 00000000 !22222222 55555555 00000000 00000000 00000000 00000000 !33333333 00000000 00000000 00000000 00000000 00000000 !00000000 !11111111 00000000 00000000 !22222222 00000000 00000000 !33333333 00000000 00000000 !44444444 00000000 00000000 !55555555 00000000 00000000 !66666666 00000000 00000000 !77777777 00000000 00000000

!11111111 00000000 !11111111 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 00000000 !11111111 !11111111 00000000 !11111111 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 00000000 !11111111 eeeeeeee ++++++++ 00000000 66666666 !11111111 !11111111 00000000 !11111111 00000000 00000000 !11111111 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 !11111111 00000000 00000000 00000000 00000000 00000000

Goodness of fit normal distribution 0.84923 normal distribution with outliers 0.98033 power law distribution 0.31121 Goodness of fit normal distribution 0.61298 normal distribution with outliers 0.58903 power law distribution 0.42118 Fig. 5. From top to bottom: number of connected components of appearing nodes; size of the largest one; distributions of the number of connected components of appearing nodes; inverse cumulative distributions of these last values; distributions of size of the largest connected components of appearing nodes; inverse cumulative distributions of these last values; goodness of fit of the distributions with the three studied distributions models. Here we considered p = 10 and c = 2 may appear, and we may consider their size. This leads to the distribution of the size of all appearing connected components, whichever round they appear in, presented in Figure 6. This distribution does not exhibit a clear difference between normal values and abnormal ones, though: the distribution is well fitted by a power-law, as the goodness of fit test on the figure 6 (bottom row) shows. As a consequence, we cannot use it to detect events that would be revealed by the appearance of an abnormally large connected component.

Notice that one may go further by computing various properties of connected components (their density, average degree, or clustering coefficient, for instance), and then observing their distribution. This may lead to the identification of statistically meaningful events. However this is out of the scope of this paper and left for future work.

VII. TOWARDS EVENT INTERPRETATION

In previous sections we have presented a methodology and some statistics which make it possible to detect statistically significant events. More precisely, we are able to point out moments in time at which events occur, and to identify nodes and links involved in these events. The ultimate goal of this procedure is to further study detected events and in particular to interpret them in term of network events (such as node or link failures, or congestions). This is crucial for a true understanding of internet dynamics and for network monitoring.

Event interpretation is challenging, though, because the current knowledge of the internet dynamics is limited, but also because of the size of the data, its ego-centered (thus biased) nature, and its lack of clear structure. Ideally, one may use a database of events occurring in the internet and match such events to the ones we detect (and conversely). This is not feasible in general, though, as no complete such database exists. Only partial information is available for some specific AS, which we explore in Section VII-A below.

One may also try to interpret detected events by visualizing the data. To do so, graph drawing is appealing, but current methods are unable to handle large graphs and/or produce drawings which are easy to interpret. Some insight may however be obtained this way, and we explore this in Section VII-B.

In the following, we select one of the most interesting statistics for detecting events, the number of appearing nodes in several consecutive rounds (Section V). We apply it to a typical measurement and select events detected this way.

Moreover, we will use a data reduction technique which will be of great help. It consists in focusing on the part of the data involved in the event under concern. To do so we first identify the set E of nodes involved in the event i.e. nodes significant appearance's for the chosen statistics. We then select the destinations such that a path from the monitor to the destination contains at least a node in E. Finally we keep only the part of the measurement obtained with these destinations, which is equivalent to measurements conduced with this reduced set of destinations. In this measurement the dynamics of nodes in E is sill visible and most nodes not involved in the event are removed.

A. Correlation with known events

In order to help maintenance and provide better services, some ISP record events occurring in their network and document them. This information is partial, poorly structured, and needs manual inspection [START_REF] Medem Kuatse | Characterizing network events and their impact on routing[END_REF], [START_REF] Huang | Practical issues with using network tomography for fault diagnosis[END_REF], but this is of great of interest here as it makes it possible to match statistically significant events which we detect to known network events reported in these databases.

Abilene [START_REF]Abilene backbone network[END_REF] is one the main ISP to provide rich information on events occurring in their network [4]. A database of tickets describing such events is freely available on line; we display typical instances in Figures 8 and9.

To match a detected event to such a ticket, we proceed as follows. First we select a statistical meaningful event with our method as explained above, and then we localize the the timestamps at which it happens (pointed out with peaks on the corresponding plot). Correlating this event with abnormal event consists in finding in the Abilene database a set of tickets such that the timestamps of these tickets overlap the timestamps of our event, and affected field cites elements whose addresses appear in the set E of involved nodes. We therefore have to collect the IP addresses of the elements cited in the ticket in order to check their presence in E.

An example of result is displayed in Figure 7. Among the detected events, two of them are correlated with tickets, and have some particularity. The first statistical event that we pointed out is followed by a significant decrease in the number of appearing nodes. This event is correlated with the trouble ticket of Abilene shown in Figure 8. A second event comes after on the plot, followed by an equivalent significant increase in the number of appearing nodes. Inspecting this second event leads to its correlation with the ticket in Figure 9, which actually is the ticket declaring that the problem cited in the first ticket ended. In this case, thus, there is a perfect fit between the two statistical events under concern and the one depicted in Figures 8 and9.

SUBJECT:

Internet2

B. Graph drawing

One may also examine a detected event by manipulating a drawing of the underlying graph. Although many drawing methods exist, with different advantages and limitations, in most cases the size of our data is prohibitive. To this regard, being able to identify a moment in time at which an event occurs and focusing on the nodes involved in the event as described above both are crucial: this data reduction leads to graphs of a few thousand nodes, which several software are able to manipulate (and draw).

One may then draw in different colors the appearing, disappearing and stable nodes and/or links. Figure 10 displays a typical example. Such manual examination of events using graph manipulation software opens the way to a more detailed understanding of detected events, and to their interpretation in terms of network events.

VIII. CONCLUSION

In this paper we propose and implement a method to automatically and rigorously detect events in the dynamics of egocentered views of the internet topology. It relies on a notion of statistically significant events. We define simple statistics to do so interestingly, all kinds of distributions are obtained: homogeneous and heterogeneous, which do not lead to the detection of events, and homogeneous with outliers, which do. We also provide approaches to interpret the detected events by drawing them and correlating them to known networking events Our main perspectives for this work are of course to explore more subtle statistics and to improve event detection. For instance, one may compute the distance between extremities of newly appearing links (before they appear). One may also conduct more case studies to gain insight on the events we observe. In order to help such interpretation, one may simulate ego-centered measurements on a graph with simulated dynamics (random removals/additions of nodes/links, for instance). This would shed light on relation between what we observe with such measurements and actual events, which is crucial in our context. Going further, one may observe events using measurements conduced from several monitors. Some events may be invisible from single monitors, giving complementary views.

Fig. 1 .

 1 Fig. 1. Top row: number N i of nodes observed at each round of measurement, as a function of the number of measurements round i performed. Middle row, left: distribution of N i ; right: inverse cumulative distribution of N i . Bottom row: goodness of fit of the distribution with the three studied distributions models.

Fig. 3 .

 3 Fig. 3.Top row: number N 5 i of distinct nodes observed during five consecutive previous rounds of measurements, as a function of the number of measurements rounds performed. Middle row, left: the distribution of N 5 i ; right: the cumulative distribution of N 5 i . Bottom row: goodness of fit of the distribution with the three studied distributions models.

Fig. 6 .

 6 Fig. 6. Top row, left: the distribution of the size of all connected components of appearing nodes observed during the measurements; right: the inverse cumulative distribution of the values on the left. Bottom row: the goodness of fit of the distribution with the three studied distributions models. Here we considered p = 10 and c = 2

Fig. 8 .

 8 Fig. 8. An example of Abilene trouble ticket which corresponds to the first event pointed out in the Figure 7. It describes a technical intervention under the ticket number 10201:45. The involved network elements are cited in the field AFFECTED. The begin and the end timestamps are given, and details are provided in field DESCRIPTION.

Fig. 9 .

 9 Fig.9. The trouble ticket corresponding to the second event pointed out in the Figure7.

Fig. 7 . 9 Fig. 10 .

 7910 Fig. 7. Number a i of appearing nodes, for all i and values p = 10 and c = 2. The two arrows denote two statistical events that were correlated with two known events tracked by the Abilene trouble tickets of Figure 8 and 9

  (top).

	!11111111 22222222 00000000 00000000 00000000
	!11111111 00000000 00000000 00000000 00000000
	!88888888 00000000 00000000 00000000
	!66666666 00000000 00000000 00000000
	!44444444 00000000 00000000 00000000
	!22222222 00000000 00000000 00000000
	!00000000
		!11111111 55555555 00000000 00000000	!22222222 00000000 00000000 00000000		!22222222 55555555 00000000 00000000	!33333333 00000000 00000000 00000000	!33333333 55555555 00000000 00000000		!44444444 00000000 00000000 00000000	!44444444 55555555 00000000 00000000		!55555555 00000000 00000000 00000000	!55555555 55555555 00000000 00000000	!66666666 00000000 00000000 00000000
	!33333333 55555555						!55555555 00000000 00000000 00000000
							!44444444 55555555 00000000 00000000
	!33333333 00000000
							!44444444 00000000 00000000 00000000
	!22222222 55555555						!33333333 55555555 00000000 00000000
	!22222222 00000000						!33333333 00000000 00000000 00000000
							!22222222 55555555 00000000 00000000
	!11111111 55555555						!22222222 00000000 00000000 00000000
	!11111111 00000000						!11111111 55555555 00000000 00000000
							!11111111 00000000 00000000 00000000
	!55555555
							!55555555 00000000 00000000
	!00000000						!00000000
	!00000000	!22222222 00000000 00000000 00000000	!44444444 00000000 00000000 00000000	!66666666 00000000 00000000 00000000	!88888888 00000000 00000000 00000000	!11111111 00000000 00000000 00000000 00000000	!11111111 22222222 00000000 00000000 00000000	!00000000	!22222222 00000000 00000000 00000000	!44444444 00000000 00000000 00000000	!66666666 00000000 00000000 00000000	!88888888 00000000 00000000 00000000	!11111111 00000000 00000000 00000000 00000000	!11111111 22222222 00000000 00000000 00000000
									Goodness of fit
			normal distribution				0.82527
			normal distribution with outliers		0.91261
			power law distribution				0.00217

  Top: number a i of appearing nodes, for all round index i and values p = 10 and c = 2, as a function of the number of measurements rounds performed. Middle, left: the distribution of a i ; right: inverse cumulative distribution of a i . Bottom row: goodness of fit of the distribution with the three studied distributions models.

	!11111111 44444444 00000000 00000000
	!11111111 22222222 00000000 00000000
	!11111111 00000000 00000000 00000000
	!88888888 00000000 00000000
	!66666666 00000000 00000000
	!44444444 00000000 00000000
	!22222222 00000000 00000000
	!00000000
		!11111111 55555555 00000000 00000000		!22222222 00000000 00000000 00000000	!22222222 55555555 00000000 00000000		!33333333 00000000 00000000 00000000	!33333333 55555555 00000000 00000000		!44444444 00000000 00000000 00000000	!44444444 55555555 00000000 00000000	!55555555 00000000 00000000 00000000		!55555555 55555555 00000000 00000000	!66666666 00000000 00000000 00000000
	!11111111 44444444 00000000							!55555555 00000000 00000000 00000000
								!44444444 55555555 00000000 00000000
	!11111111 22222222 00000000
								!44444444 00000000 00000000 00000000
	!11111111 00000000 00000000							!33333333 55555555 00000000 00000000
	!88888888 00000000							!33333333 00000000 00000000 00000000
								!22222222 55555555 00000000 00000000
	!66666666 00000000							!22222222 00000000 00000000 00000000
	!44444444 00000000							!11111111 55555555 00000000 00000000
								!11111111 00000000 00000000 00000000
	!22222222 00000000
								!55555555 00000000 00000000
	!00000000							!00000000
	!00000000	!22222222 00000000 00000000	!44444444 00000000 00000000	!66666666 00000000 00000000	!88888888 00000000 00000000	!11111111 00000000 00000000 00000000	!11111111 22222222 00000000 00000000	!11111111 44444444 00000000 00000000	!00000000	!22222222 00000000 00000000	!44444444 00000000 00000000	!66666666 00000000 00000000	!88888888 00000000 00000000	!11111111 00000000 00000000 00000000	!11111111 22222222 00000000 00000000	!11111111 44444444 00000000 00000000
										Goodness of fit
			normal distribution				0.86490
			normal distribution with outliers		0.97263
			power law distribution			0.00703
	Fig. 4.

  May 17, 2007, 11:47 AM (1147) UTC END TIME:Friday, May 18, 2007, 3:51 AM (0351) UTC DESCRIPTION:Peer SINET was unavailable to the the Internet2 IP Network Community. SINET Engineers reported the reason for outage was due to a fiber cut in New York. SINET is multi-homed.

	SUBJECT:	Internet2 IP Network Peer SINET (CHIC) Resolved
	AFFECTED:	Peer SINET (CHIC)
	STATUS:	Available
	START TIME: Thursday, TICKET NO.: 10201:45
	TIMESTAMP:	07-05-18 07:39:16 UTC

It also experiences changes of regime, like N i , for instance around round 5 600 in Figure3. Notice that, in this case, the new average value for N[START_REF] Albert | Topology of evolving networks: Local events and universality[END_REF] i is larger than before, while it was lower for N i . This means that, although we see less nodes in each round, the nodes we see vary more from one round to another. This gives some hints on further understanding the event which occurred, but deepening this is out of the scope of this paper.


Thomas Aynaud
email: thomas.aynaud@lip6.fr

Jean-Loup Guillaume
email: jean-loup.guillaume@lip6.fr

Static community detection algorithms for evolving networks

Keywords: complex networks, evolving communities, stability, tracking, blogs

Complex networks can often be divided in dense sub-networks called communities. Using a partition edit distance, we study how three community detection algorithms transform their outputs if the input network is slightly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in an evolving network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finally use it on an evolving network of blogs.

INTRODUCTION

Complex networks arise naturally in many different fields. They describe a variety of systems by modeling the interactions between constituents. For instance, the internet is a network of computers linked by physical or wireless links. Similarly, the web can be seen as a network of web pages linked by hyperlinks.

A common feature of many real networks is the existence of groups of nodes, or communities, which are crucial in understanding the underlying structure of large networks. Communities can be, for example, groups of friends in a social network, websites dealing with the same subject or scientists working on similar topics in co-authorship networks. Formalizing the notion of community and detecting communities is a harsh task which has attracted a lot of attention in the recent years. In particular, many algorithms based on the network topology have been proposed.

However, most studies usually deal with a single static network which is a snapshot of the data. Very few studies have given attention to temporal features. As real data are always evolving (in phone networks, people do not call each other permanently; on the web, pages appear, disappear or are updated continuously for instance), a lot of information is lost.

In this paper, we will try to track communities between successive snapshots of the evolution of a network. We will first use classical community detection algorithms whose main issue in this context is stability. Indeed, we will show how little modifications of the input network often lead to strong transformations of the detected community structure, making them untraceable. We will thus propose a modification of one very effective algorithm to obtain much more stable communities and then use it to study a truly dynamic dataset: a network of blogs.

The paper is organized as follows: in the first section we will present classical results about community detection, evolving networks and community tracking. Then, we will describe our experiments and results concerning stability in the second section. In the third section, we will propose a modified version of the Louvain algorithm to achieve better stability and the results of our experiments on a real graph.

I. BACKGROUND AND RELATED WORK

A. Communities

The detection of communities in complex networks has attracted a lot of interest and many definitions of a community have been proposed. Usually, algorithms are looking for a good partition of the nodes. This implies that no node belongs to more than one community and the main issue is to define what good means. People dealing with visualization problems often define a good partition as a partition where parts are drawn separately [START_REF] Auber | Multiscale visualization of small world networks[END_REF]. Good partitions can also be obtained through k-means algorithms using the classical distance in graphs as a distance between nodes [START_REF] Schenker | Graph representations for web document clustering[END_REF]. Another classical approach consists in defining a quality function which gives a score to a partition: the good partition is the one which maximizes this quality function. One of the most used quality function is the modularity, defined in [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Ranging between -1 and 1, the modularity compares for each parts (or community) the proportion of links inside the community with a null model. The higher it is, the better the partition is.

B. Detection algorithms

Finding the partition which maximizes the modularity is NP-hard [START_REF] Brandes | Maximizing Modularity is hard[END_REF] and therefore many approximation algorithms have been proposed, see [START_REF] Porter | Communities in Networks[END_REF]- [START_REF] Fortunato | Community detection in graphs[END_REF] for comprehensive surveys. In this paper, we will use three different algorithms: the first one, Walktrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF], is based on the idea that a small random walk will stay inside the community from where it's originating because there are many links inside and few bridges leading outside. the second one, Fast Greedy [START_REF] Clauset | Finding community structure in very large networks[END_REF], is a greedy optimization algorithm for modularity: each node is initially in its own community and then, at every step, the algorithm groups two communities in order to maximize the gain of modularity. the last one, Louvain Method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] is described more precisely in the next paragraph since we will modify it in section III-A. Louvain Method is a hierarchical greedy algorithm. It is composed of two phases, executed alternatively. Initially, each node is in its own community. Then, during phase 1, nodes are considered one by one, and each one is placed in the neighboring community (including its own community) which maximizes the modularity gain. This phase is repeated until no node is moved (the obtained decomposition is therefore a local maxima). Then, phase 2 consists in building the graph between communities obtained during phase 1: there is a node in the new graph for each community and, for two communities C and C H , there is a link of weight w where w = P v;v 0 PC¢C 0 weight(v; v H ). There is also a loop on C of weight P v;v 0 PC¢C weight(v; v H )1 . Then, the algorithm starts the phase 1 again with the new graph, grouping communities together, and then phase 2, and so on until the modularity does not improve. The whole process is described on algorithm 1.

Algorithm 1 Pseudo-code of Louvain Method

1: G the initial network 2: repeat 3:

Put each node of G in its own community 4:

while some nodes are moved do

5:
for all node n of G do 6:

place n in its neighboring community including its own which maximizes the modularity gain 7:

end for 8:

end while

9:
if the new modularity is higher than the initial then end if 14: until These three algorithms perform well on static networks. However, Louvain Method is the fastest and most accurate method (it achieves better modularity) and walktrap the slowest and less accurate. However, we are willing to deal with evolving networks and less efficient static algorithm can be more efficient for evolving networks. This is the reason why we did not restrict ourselves to the Louvain Method.

C. Evolving communities

The study of the evolution of communities has lead to two main approaches: using the temporal information directly in the detection or tracking communities among different snapshots, often obtained with algorithms suited for static graphs. The first direction has not been widely followed. To take into account the temporal information, authors of [START_REF] Kumar | Evolutionary clustering[END_REF] have for example modified the quality function to integrate dynamics inside it. In [START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF], a probabilistic model integrating dynamic features is defined and used to detect communities.

On the other hand, the main underlying problem when computing communities on different snapshots is to decide which community at time t has evolved into which community at time t + 1. Considering that communities may merge, split, appear or disappear, many solutions have been proposed. In [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF], Hopcroft et al. look for two parts sharing the most nodes and having similar size. In [START_REF] Spiliopoulou | Monic: modeling and monitoring cluster transitions[END_REF], this idea is generalized by introducing many rules to handle split, merge, etc. This method works but finding a consensus on rules is difficult, and there are always some parameters that must be fixed arbitrarily. When do two communities are the same? Is it when they share 70% of the nodes? Or maybe 80%, 90% or more? To avoid this kind of rules, [START_REF] Palla | Quantifying social group evolution[END_REF] uses a modification of their own community detection algorithm to do the matching. However, this requires a property on the algorithm that is barely fulfilled: by adding links to a network, the communities can only grow, merge or remain unchanged. Thus, community tracking and detection on evolving networks is still a challenge.

D. Comparing partitions and tracking

The most widely used metric to evaluate the distance between two partitions is the mutual information [START_REF] Fenn | Dynamical Clustering of Exchange Rates[END_REF]. It ranges from 0 to 1, where a value of 0 means that partitions are independent and 1 that they are equal. Defined by the information theory, it counts the number of bits shared by two random variables. This metric is really interesting but have a few issues. First, there are many ways to normalize it, leading to different values, and no normalization is clearly the good one. Secondly, it has been proven that there is a correlation between mutual information and the size of the partitions [START_REF] Epps | Information Theoretic Measures for Clusterings Comparison: Is a Correction for Chance[END_REF]. Consequently, it is not well-suited to compare algo-rithms. It is also rather difficult to interpret and, extreme values excepted, it does not allow to really decide if partitions are close, really close or far from each others.

To address these issues, we have decided to use both mutual information and an edit distance between partitions. This distance counts the number of transformations needed to move from a partition A to a partition B. For example, figure 2(a) presents two partitions with two possible matchings. In the first one, nodes C, D, E, F, G and H must be moved whereas, only C and F have to move with the second matching. The matching which minimizes the number of transformations can be computed in O(n 3 ) with n the number of parts using the Kuhn-Munkres algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]. This distance has two advantages and one disadvantage: it gives the matching and it is more intelligible but its matching is a one to one association. There are no merge, split or apparition of new communities, and thus the association is only reliable when such one to one association exists, i.e. only when the communities are really stable.

Using these algorithms and definitions, we are able to compute communities at different time steps of the evolution of a network and compute the similarities between the partitions. This will be first used to study the stability of the algorithms in case of small modifications of the networks.

II. STABILITY OF THE THREE ALGORITHMS

To study the stability of the three algorithms, we first simulate an evolution on a classical static network. The evolution simply consists in the removal, one by one, of a random node, keeping only the largest connected component to always have a connected network. This is clearly not realistic, but removing one node should not change the structure of the network and thus partitions computed with any algorithm should be very similar (both in terms of mutual information or edit distance) before and after removal. We present hereafter results using the arxiv dataset which is a network of scientists defined by Newman in [START_REF] Newman | The structure of scientific collaboration networks[END_REF]. Two scientists are connected if they have written a paper together. To simplify the network and as they do not modify the communities, we have removed the nodes connected by a single link. This gives a network of 9377 nodes and 24107 edges. The obtained results are qualitatively similar on other networks.

The first metric computed at each time step is the modularity. The results are presented on the figure 3(a). The modularity is in each case growing slowly until a break point where it falls quickly. The Louvain Method performs better than Fast Greedy which is itself better than Walktrap in the sense that the partition found has higher modularity. The order remains the same when considering the speed. Another remark is that the modularity is almost constant between two consecutive steps. Removing random nodes does not modify much the structure of the network and the quality is therefore really stable.

The number of communities in the partition, shown on the figure 2(b), is also stable for the Louvain Method and the Fast Greedy algorithm. Walktrap is less stable during the whole run, but the number of communities does not change very quickly. Thus we are in the case where the partition edit distance is reliable.

The figure 3(b) shows the mutual information between every partition and its predecessor. Walktrap algorithm has values close to 1 and seems really stable. On the opposite, the two other algorithms take many different values of mutual information ranging from 0.75 to 0.98 for Louvain Method, and from 0.65 to 0.97 for Fast Greedy. The distance between partitions varies a lot between different steps. But a value of 0.9 of the mutual information, which is common for Louvain Method, seems to indicate that the partitions are not so different. The partition edit distance, shown on figure 3(c), gives a really different insight: after the removal of only one node among (initially) 9377, between 2000 and 3000 nodes are moved in the community structure with the Fast Greedy algorithm, and between 1500 and 2500 with the Louvain Method. This means that the communities detected at each step are completely different and that both algorithms are extremely instable. Walktrap's results are clearly better, but there are still often 500 moves which represent too many transformations for only one node removed.

Therefore, none of these algorithms is suitable to compute evolving communities due to this instability. We will next propose a new version of the Louvain method which is far more stable.

III. A STABILIZED VERSION OF THE LOUVAIN METHOD

A. Stabilized algorithm

To be able to track communities we propose another much more stable version of the Louvain Method. The idea is to constrain the initial partition in order to force stability. This can be simply done by changing the initialization of the algorithm. Whereas the classical Louvain Method starts with every node in its own community, we will now start the computation at time t by grouping nodes using the partition found at time t 1. We then apply the exact same algorithm, allowing nodes to move if the initial constraint is not pertinent.

The figure 4(a) is similar to the figure 3(c) but with the modified algorithm. The communities are far more stable. Most of the time, the communities are not modified, but there are some pikes where small modifications happen. This is far more satisfactory since the removal of one node does not change the structure of the graph, except for a few central nodes.

The pikes on figure 4(a) can be caused by true events on the network or be artifacts caused by the algorithm. Therefore we have removed each node independently, starting from the initial network and compared the communities obtained with the initial decomposition.

We then tried, for each node, to correlate the distance between partitions and properties of the removed node (degree, pagerank, closeness or betweeness centrality computed on the whole graph or using only the graph inside the removed node community). None of the computed metrics is clearly correlated with the effect on communities' stability. Therefore we are not able at the moment to explain why the removal of some specific nodes generates more modifications of the partition. However, stability is not sufficient to have good partition. The figure 4(b) presents the modularity of Louvain Method, Walktrap and Louvain Method modified. Most of the time, Louvain Method modified is better than Walktrap and competes with Louvain Method. It is only when the network topology has changed a lot, at the end of the run, that Walktrap outpasses Louvain Method modified. As we remove one node, every node in the initial partition is in a community, and we can assume that it is in a good one as it is the result of the algorithm. Thus, the initial partition is a strong constraint for the algorithm and we will next study some possibilities to limit this constraint.

B. A stability vs. quality parameter.

To limit the constraints of the modified algorithm, we choose randomly x% of the nodes and place them alone in their own community instead of putting them in their previous community. The higher x is, the more the algorithm can modify the communities since the nodes placed alone in their communities will be moved (it is always a bad choice to leave a node alone). If x = 100%, the algorithm is the classical Louvain method and if x = 0%, the algorithm is the stabilized version presented before. There is obviously a tradeoff between stability and quality. Figure 4(c) shows the modularity for different values of x. Even low values of x like 2% make an important improvement and change the shape of the plot.

Figure 5(a) shows the average partition edit distance during the first 1000 removals. For small values of x, the stability is only slightly damaged. For larger values, above x = 50%, the stability increases linearly to reach the classical Louvain stability. Using x = 2% seems to be a good compromise here: it gives a good stability and a very high modularity. This parameter depends on the network evolution. For instance, if there are many modifications, using the previous partition can be sufficient. Indeed, the initial partition is not so good and therefore does not impose much constraints. The choice of x depends on the number of modifications between two consecutive snapshots. If snapshots are very similar, x should be increased to give more freedom, but if they are far enough, it may remain set to 0.

C. A real dynamic

As the evolution used before is completely artificial, we have run the same tests on a truly evolving network: a network of blogs. During four months, around five thousands blogs have been monitored to track posts and comments. Let's consider that time 0 corresponds to the beginning of the measurement. The nodes of the network at time t are the blogs which contain a post between time 0 and t. There is a link between two blogs at time t if one of them make a link to the other between time 0 and t. The resolution is of one day, so we have 120 snapshots of the network, one for each day, which all represent the aggregation of the posts and links until the considered day. To simplify community detection and tracking, we take only the largest connected component for each snapshot.

Starting first with an empty network, we applied the same algorithms and tracking techniques than in section II using the modified Louvain Method. As we are only adding nodes and not removing them, we put all new nodes alone when starting the algorithm.

Figure 5(b) shows the modularity of the different decompositions at each time step. The Louvain Method is still the best but the modified version is really close. It performs better than in section III-A since the algorithm has more freedom. Enough nodes are alone or clearly misclassified, so the decomposition here is not too constrained and there is no need of the parameter defined in the previous sub-section. It can be set to 0 without any loss of quality.

The figure 5(c) shows the partition edit distance between each successive partition. The modified Louvain Method is more stable than the others, allowing an easier tracking of the communities. First, the network evolves a lot during its first construction and then stabilizes. There is also a detected event at the time step 40 corresponding to an event in the measurement (some blogs where added to the initial list).

Thus, starting from an empty network, the modified Louvain Method is fast, stable, and produce high quality results. To start with a network more structured and to see how the modified method reacts, we run the same tests starting with the network at time 60, and the results are very similar. The modified Louvain Method is still able to adapt the initial partition to achieve high modularity, with a better stability.

CONCLUSION AND DISCUSSION

We have shown that classical community detection algorithms are very instable. This instability has been precisely evaluated using a partition edit distance which gives understandable values and a matching between partitions. It raises questions about the reliability of the results of these algorithms. They produce many different results, which are all evaluated as good since they have high modularity, but which one is the best? We have no answer to this question, and the proposed solution is a workaround.

The instabilities also forbid to make an effective tracking of the communities at different time steps: everything change, so it becomes impossible to identify trends and events. We have proposed a modification of the Louvain Method which achieves a really good stability without major loss of quality. This modified version also includes a parameter that allows to controll the loss of quality and the stability. If the evolution is tiny, like the removal of one node, setting x to small values like 2% is enough to achieve better modularity with still a good stability. It is one of the first algorithms taking into account the dynamic by using the previous computation and it now allows to track several communities at different time steps.

The gap between partitions cannot be considered as true events but are often due to the algorithm and removing the last artifacts is still a challenge. The possible transitions are also very limited. There is always a one to one matching, with new empty sets if needed. The transitions are still rough because of the lack of overlapping communities. We can imagine that a community does not disappear instantaneously but is slowly absorbed by some other ones and our method cannot handle this kind of transformations.

Figure 1 .

 1 Figure 1. Example of a network with communities.

Figure 2 .

 2 Figure 2. Example of the matching between parts of different partitions and number of communities during one run

Figure 3 .

 3 Figure 3. Modularities during one run and mutual information or partition edit distance between two consecutive partitions.

Figure 4 .

 4 Figure 4. Stability and modularity of the stabilized version of the Louvain Method and modularity using the quality parameter.

Figure 5 .

 5 Figure 5. Average edit distance during the first 1000 removals with different values of the quality parameter. Modularity and partition edit distance of the blogs at each time step

This ensures that the partition found after phase 1 has the same modularity as the partition of the new graph where each node is put in its own community