Change Detection in Large Evolving Networks

Introduction

A network is described as a set of interconnected nodes, such as a computer network, social network, communication network (Sun, Faloutsos, Papadimitriou & Yu, 2007), to mention a few. This study focuses on modelling the relationship between the network points represented as a graph of the communication on a computer network over a period of time in terms of connectivity, unlike network traffic measurement in the form of packets or their size (bytes). Given that data in computer networks consists of billions of nodes, which are communicating with each other as indicated by the edges, makes it massive. When we consider such data over a period of time, this data becomes even more massive. As a result, the massive size of such network structures makes them vulnerable to various cyberattacks such as Advanced Persistent Threats (APTs) that can be entrenched into the network and stay undetected for long periods of time. Our study therefore leverages from the context of attacks that prevent the normal use of a computer and may cause it and any affiliated resources from being reliable, available or accessible. Furthermore, in real-world networks, large volumes of network traffic pose a challenge in efficiently monitoring them for attack detection and thus creates a need to characterize network behavior to create awareness in order to determine potential vulnerabilities.

The process of change detection in such large evolving networks can be used to establish awareness on a network by monitoring the network to detect shifts (McCulloh, 2009). While changes do occur as graphs evolve over time, certain changes are more significant than others, creating the task to make sense of changes that take place. In the case of massive computer networks that are vulnerable to various cyberattacks, change detection can be used as a trigger for further investigation into the network to determine if changes in the network are associated to a previous, present or potential cyber threat. Therefore, our objective is to conduct a selective analysis of massive network structures in order to mine this massive data efficiently and to accurately make sense out of the knowledge discovered.

Our approach is multifaceted whereby we apply graph sampling to identify and select representative subsets of the network. We consider this as a strategic sampling approach in which we utilize a hybrid methodology that combines sampling, clustering and stratified binning to select key nodes, namely central nodes and key subgraphs associated to the central nodes from a network over time as presented in our preliminary work in (Namayanja & Janeja, 2013, 2014, 2015). We consider a central node to represent a key (critical) node on the network such as a server. Such central nodes are considered important points on a network based on their role in the network that can be defined in terms of their centrality such as degree centrality and betweenness centrality (Freeman, 1979), eigenvector centrality (Bonacich, 1987), PageRank (Page, Brin, Motwani, Winograd, 1999) among others. Determining the role of a node in a network can be useful in threat detection (Scripps, Tan & Esfahanian, 2007) and according to (Shen, Nguyen, Xuan & Thai, 2012), an assessment of network vulnerabilities indicates that an attacker is likely to exploit the weak points such as critical nodes whose corruption greatly affects network performance.