Back to search

Rowan University

AN EMPIRICAL STUDY ON DETECTING AND EXPLAINING GLOBAL STRUCTURAL CHANGE IN EVOLVING GRAPH USING MARTINGALE

Abstract

dc:description.abstract

There is a growing interest in practical applications involving networks of interacting entities such as sensor networks, social networks, urban traffic networks, and power grids, all of which can be represented using evolving graphs. Changes in these evolving graphs can signify shifts in the behavior of interacting entities or alterations in the patterns of their interactions. Identifying and detecting these changes is crucial for addressing potential challenges or opportunities in various domains. In this study, we propose an approach for detecting structure change in evolving graphs based on the martingale change detection framework on multiple graph features extracted over time. Our research investigates the impact of different graph properties encoded using different feature representations on the evolving graph change detection task. Moreover, performing change detection on multiple graph features allows us to pinpoint which aspects of the graph behavior have changed and provide explanations for identified changes. We demonstrated empirically the robustness of our proposed approach on synthetic evolving graphs generated using different graph-generating algorithms, including scale-free, phase transition, and random small-world evolving graphs. Furthermore, we demonstrate that the proposed martingale approach maintains a desirable false positive bound even when different feature representations are used. Finally, we demonstrate monitoring martingale values for different graph properties on a real-world evolving graph sequence to explain the detected change points.

Degree

thesis:*
Name thesis:degree_name
Master of Science (M.S.) in Computer Science
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kairamkonda, Tarun Teja
Contributors dc:contributor
  • Shen-Shyang Ho, Ph.D.
  • Anthony Breitzman, Ph.D.
  • Guimu Guo, Ph.D.

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://rdw.rowan.edu/etd/3253

Chain of custody

source
Harvested from
Rowan University
Base URL
rdw.rowan.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kairamkonda, Tarun Teja. AN EMPIRICAL STUDY ON DETECTING AND EXPLAINING GLOBAL STRUCTURAL CHANGE IN EVOLVING GRAPH USING MARTINGALE. Thesis thesis, https://rdw.rowan.edu/etd/3253