Date Approved

6-20-2024

Embargo Period

6-24-2024

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Computer Science

Department

Computer Science

College

College of Science & Mathematics

Advisor

Shen-Shyang Ho, Ph.D.

Committee Member 1

Anthony Breitzman, Ph.D.

Committee Member 2

Guimu Guo, Ph.D.

Keywords

Change-point Detection; Machine Learning; Non-parametric Statistics; Probabilistic Algorithm

Subject(s)

Graph theory; Networks

Disciplines

Applied Mathematics | Computer Sciences

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.

Download

Share

COinS