Network data streams oer an abstraction of complex systems from the real-world, which can be seen as producers of unbounded sequences of complex data generated at high speed. Many complex systems evolve according to stochastic processes which remain unknown to the interested users. As a consequence, changes happen in an unpredictable manner and may involve various portions of the observed complex systems. In this scenario, an interesting problem concerns the identication and characterization of the changes that may concern both the whole structure of a complex system and small parts of it. We conjecture that the former can be explained by the latter and conversely, the latter can trigger the former. This type of problem requires a quite holistic strategy that traditional approaches often do not carry out because they focus on either the whole network or on some portions only. In this discussion paper, we describe a descriptive data mining approach based on frequent pattern discovery that we designed for recent research work. It combines frequent pattern with automatic time-window setting, in order to identify and characterize macroscopic changes and microscopic changes as changes that have an impact on a substantial part of the network or on specic portions, respectively. We provide arguments of the viability to real-world applications through two case studies, more precisely, telecommunication networks and geo-sensor networks.
The dissemination of technologies able to unceasingly record information from
real-world applications has lead to the development of systems based on data
stream models. Often such systems work in highly dynamic and complex
domains where data are naturally interconnected. This is the case of social networks
and telecommunication infrastructures. Analyzing data continuously generated
Copyright c 2019 for the individual papers by the papers’ authors. Copying
permitted for private and academic purposes. This volume is published and copyrighted
by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
in these elds requires data stream mining algorithms that operate on network
data. In this scenario, a natural and interesting problem is that of analyzing data
streams in order to identify the changes in the network interactions over time.
However, in the domains in which human supervision or reference knowledge are
not promptly available we cannot learn models able to recognize changing
behaviors, and therefore the supervised approaches give way to those unsupervised.
The descriptive data mining techniques and, in particular, the pattern-based
approaches are gaining great attention thanks to their peculiarities to provide
arguments to the change-related discoveries through statistical evidence. In [
We addressed the critical points of the aforementioned works through a
method, described in detail in [
As for the methodological approach, we resort to the frequent pattern
mining framework to generate a summarizing form of the network data on which
identifying evolutions. Therefore, frequent subnetworks are not the primary
objective of the paper, but the means to capture two kinds of changes. By using
pattern-subnetworks, we can search for changes in an abstract description of the
network [
As for the algorithmic solution, the hypothesis on the absence of labeling
of the changes suggest us to monitor data streams and decide when new data
snapshots exhibit a change, that is, when the network diers from the past. To
this end, we use two time-windows, one to collect data snapshots of the
"recent past" and the other to collect new data snapshots. This way, we capture
the status of the network in two distinct time-windows, keep patterns and their
statistical properties updated, and adapt the search strategy to the variations
of the underlying data distribution. The combined use of time-windows and
frequent subnetworks suggests us to search for i) macroscopic changes as variations
between sets of frequent subnetworks discovered on two time-windows, and ii)
microscopic changes as punctual variations of frequent subnetworks occurring at
the level of data snapshots. The use of two windows ("recent past" and "new
snaphosts") has been studied also for predictive tasks [
In the following, we provide some basic concepts as well as the notions of change
of interest for this work. A network data stream is the time-ordered sequence D =
hG1; G2; : : :i of network snapshots Gi observed at time-point ti. Each snapshot
Gi is labeled graph with labeled edges Gi N N L, where N is the set of nodes
and L is set of edge labels. In particular a landmark window W = [ti; tj] of width
jW j = j i + 1 is the sequence of consecutive snapshots fGi; : : : ; Gjg. Following
[
The proposed approach relies on the frequent pattern mining framework. In particular, we i) restrict the pattern language to subnetworks in which there exists a path between any two nodes, and ii) mine frequent subnetworks from snapshots of a window W . The support of a subnetwork S in W is dened as sup(S; W ) = jfGi2W jS Gigj . A subnetwork S is frequent in W if sup(P; W ) jW j minSU P , where minSU P 2 [0; 1]. Then, FW denotes the set of all the frequent subnetworks discovered from the window W . We consider two types of changes: Denition 1 (Macroscopic change). Given minM C 2 [0; 1], a macroscopic change is found if M C(W; W 0) = jFW0 FW j+jFW FW0 j > minM C.
jFW j+jFW0 FW j Denition 2 (Microscopic change).
Given minGR 2 [1; +1), a subnetwork minGR if S 2 (FW FW 0 ), or ii) ssuupp((SS;;WW0)) minGR if S 2 (FW 0
FW ). where, W = [ti; tn] and W 0 = [ti; tm] are two successive windows, FW and FW 0 are the sets of frequent subnetworks mined on W and W 0, respectively.
In these terms, the problem of identifying and characterizing macroscopic and microscopic changes in a network data stream D = hG1; G2; : : :i can be interpreted as the search for pairs of successive windows ( W , W 0), in which the i) quantication of the variations between FW and FW 0 exceeds the threshold minM C and ii) quantication of the variations the support of S (either S 2 (FW FW 0 ) or S 2 (FW FW 0 )) exceeds the threshold minGR.
In this discussion paper, we discuss the KARMA algorithm proposed in [
2 init. W with rst block of D new block from D 3 8
W = W 0
FW = FW 0 W 0 = W [ 7
W = FW = F 4 6
update FW 0 and FW micro. changes in (W; W 0)
minM C 5
evaluate M C(W; W 0) > minM C
The algorithm relies on the frequent subgraph mining framework, which is intractable for massive datasets due to the combinatorial explosion of the frequent subgraphs. For this reason, the sets FW and FW 0 are kept updated and not recomputed from scratch upon the arrival of new transactions. Algorithmically, this is done by means of incremental solutions of frequent pattern mining. When a new block of network snapshots is acquired, KARMA builds the window W 0 (W 0 = W [ ) and checks if there is a macroscopic change by matching W 0 against W . To do that, KARMA oers two peculiarities: i) identication of relevant changes on a summary of the data (the set of frequent subnetworks) rather than on the raw data, and ii) quantication of the changes in terms of the dierences between the set FW of frequent subnetworks discovered on W and the set FW 0 of frequent subnetworks discovered on W 0. It is desirable to seek for changes on data by looking at frequent subnetworks in order to avoid false alarms, thus achieving higher robustness to noisy data. In this scenario, a single noisy network snapshot (e.g. a noisy outlier) would not aect the set of frequent subnetworks, depending on the minimum support minSU P . In fact, the main assumption behind the macroscopic change is that the whole network does not exhibit a change between W and W 0 if the frequent subnetworks, FW and FW 0 , do not signicantly change. To measure the amount of change, KARMA computes the macroscopic change (MC) as M C(W; W 0) = jFW 0 FW j+jFW FW 0 j . jFW j+jFW 0 FW j Where W and W 0 are two successive landmark windows, jFW FW 0 j denotes the number of subnetworks which are frequent in W and infrequent in W 0, and jFW 0 FW j is the number of subnetworks which are frequent in W 0 and infrequent in W . The formula quanties the fraction of subnetworks which have crossed the minimum support threshold minSU P , that is, those which were frequent (infrequent) in W and become infrequent (frequent) in W 0, and which therefore indicate a relevant change in the underlying network data distribution. 3.2
Microscopic change mining
S, ssuupp((SS;;WW0))
In KARMA, the discovery of microscopic changes is performed only when a
macroscopic change is spotted. Indeed, a microscopic change accounts for the
contribution that each subnetwork, which crosses the minimum support
threshold minSU P , gives to the macroscopic change. To do that, we resort the
notion of emerging pattern [
S 2 (FW minGR if S 2 (FW 0 FW )). Every emerging subnetwork S satisfying the growth-rate inequality denotes a single microscopic change. The minGR threshold is a tradeo between the completeness and the simplicity of the descriptive model. Low values of minGR lead to expressive models, while high values lead to synthetic models about the change.
3.3
KARMA at work We show the applicability of KARMA for the analysis of a real-world network by discussing some discoveries and commenting on their actionability with respect to facts and events occurred in the domain. In the following, we discuss two case studies: the rst39 in the domain of telecommunication networks (NODOBO dataset), and the second in the domain of geo-sensor networks (NOAA dataset).
The NODOBO 1 dataset concerns a communication network and contains telecommunication transactions gathered during a study of the mobile phone usage of 27 students of a Scottish state high-school, from September 2010 to February 2011. The students communicate by phone calls, text messages (SMS) and Bluetooth connectivity. When building the network, the nodes represent the students, while the edges represent the dierent modalities of communication. 1 http://nodobo.com/release.html
The dataset NOAA2 was developed in the context of the Reanalysis project by the National Center for Environmental Prediction and the National Center for Atmospheric Research. The project aimed at providing new atmospheric analysis by gathering daily measurements of various meteorological quantities (e.g. relative humidity and air temperature) by means of geo-localized sensors equally distributed over space. In this work, we built the network with the measurements of relative humidity of the time-interval January, 1st 1990 - December, 31st 2010, recorded daily on an area that roughly covers North-Central America. The nodes of the network represent the sensors, while the edges are nominal values denoting the relative humidity values measured on the two linked sensors.
As for the analysis of NODOBO, in Figure 2, we see a succession of points with a decreasing trend, which has the peak on October 26th, 2010 and the lowest number of microscopic changes on December 6th, 2010. To give a practical interpretation to this behavior, it is useful to say that in Scottish state highschools there is a holiday period which covers the second and third week of October, thereafter the school activities continue. So, the projection of Figure 2 reveals that, when the school activities resume, there is high variability (many microscopic changes) in the modalities of communication, which, as time goes by, tends to decrease. This may provide indications on the use of mobile phone of the students, which can be exploited, for instance, to plan the school policies and to improve the mobile network services in the area.
Among the microscopic changes associated to the peak, we nd the pattern P ={(student_14, student_0, bluetooth ), (student_18, student_0, bluetooth ), (student_2, student_0, high_length )}. It is involved in the strongest macroscopic change (quantied as 0.94), which starts on October 26th 2010 at 3:00 (the time-point after the window [2010 Oct 25-22:00, 2010 Oct 26-2:55]) and terminates on October 26th 2010 at 7:55. Specically, P denotes the doubling 2 https://coastwatch.pfeg.noaa.gov/erddap/griddap/esrlNcepRe.html (growth-rate equals to 2.0) of the occurrences of the associated subnetwork from the window [2010 Oct 25-22:00, 2010 Oct 26-2:55] to the window [2010 Oct 25-22:00, 2010 Oct 26-7:55]. On the contrary, (we veried) P does not appear in the set of microscopic changes corresponding to the successive macroscopic change detected between the landmark windows [2010 Dec 05-22:10, 2010 Dec 06-3:05] and [2010 Dec 05-22:10, 2010 Dec 06-8:05], which may indicate that the modalities of interaction among the three students become stable.
As for the NOAA domain (Figure 3), there are several macroscopic changes, those which have a greater impact on the network are characterized by more than 150 microscopic changes. In particular, there are two macroscopic changes with the highest number, they start on October 17th, 1995 and August 2008, 9th respectively. We deepened the microscopic changes corresponding to the two points and spotted several emerging subnetworks in common, one is P ={(<10,300>, <10,305>, from_70_to_80 ), (<10,300>, <7.5,297.5>, from_80_to_90 ), (<12.5,297.5>, <7.5,297.5>, from_80_to_90 )}.
By mapping the nodes of P into a geodesic space, we see they identify two regions, both cover approximately the area of the state of Venezuela and part of the Caribbean sea, where there are small dierences in terms of relative humidity (the edge labels refer to consecutive ranges). This meteorological scenario becomes less frequent (the growth-rate decreases) over the window [1995 Oct 17, 1995 Nov 30] and [2008 Aug 09, 2008 Sep 22] respectively, which suggests the possibility of dierent behavior, in the same geographic area, occurred before or after those two macroscopic changes. 4
In this discussion paper, we have investigated the problem of identifying relevant
changes in network data streams, where the changes can be distinguished in two
categories: macroscopic changes and microscopic changes. The system presented
in the paper, called KARMA, is able to simultaneously extract macroscopic
changes and microscopic changes by exploiting the fact that they are inevitably
related to each other. Two case studies have shown the usefulness and the
actionability of the changes in the domain of geo-sensor networks and
telecommunication networks. An extensive discussion on the inuence of the parameters
(minSUP, minMC, minGR) on the results can be found in [
For future work, we plan to investigate two main research directions: i) use
of solutions of big data analytics to detect changes in very large networks, and
ii) study of the closed patterns [