Change Detection in Large Evolving Networks

Change Detection in Large Evolving Networks

Josephine M. Namayanja, Vandana P. Janeja
Copyright: © 2019 |Pages: 18
DOI: 10.4018/IJDWM.2019040104
(Individual Articles)
No Current Special Offers


This article presents a novel technique for the detection of change in massive evolving communication networks. This approach utilizes a novel hybrid sampling methodology to select central nodes and key subgraphs from networks over time. The objective is to select and utilize a much smaller targeted sample of the network, represented as a graph, without loss of any knowledge derived from graph properties as compared to the entire massive graph. This article uses the targeted samples to detect micro- and macro-level changes in the network. This approach can be potentially useful in the domain of cybersecurity where this article highlights the importance of graph sampling and multi-level change detection in identifying network changes that may be difficult to detect on a larger scale. This article therefore presents a means to audit large networks to establish continuous awareness of network behavior.
Article Preview


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.

Complete Article List

Search this Journal:
Volume 20: 1 Issue (2024)
Volume 19: 6 Issues (2023)
Volume 18: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing