Abstract
This paper explores the use of network centrality and network entropy to identify bifurcation events in dynamic complex networks. A bifurcation represents a qualitative structural shift in response to internal or external changes. By extracting multiple centrality features and applying dimensionality reduction, we track network dynamics on a low-dimensional manifold. Additionally, we employ von Neumann graph entropy (VNGE) to measure information divergence over time, introducing an asymptotically consistent quadratic-complexity estimator to improve scalability. The framework's effectiveness is demonstrated through a real-world cyber intrusion detection application.
Introduction: The Challenge of Network Bifurcations
Dynamic networks, such as cyber infrastructures or biological systems, often reach critical thresholds where minor changes trigger abrupt, qualitative shifts in behavior—a phenomenon known as a first-order bifurcation. Detecting these transitions is difficult due to the high dimensionality of network data and the computational cost of traditional complexity measures. This research addresses these challenges by identifying low-dimensional "signatures" of network health and optimizing entropy calculations for large-scale systems.
Methodology
Centrality-Based Manifold Learning
Rather than analyzing raw adjacency matrices, the proposed approach extracts a suite of centrality features for each node, including Degree, Eigenvector centrality, Betweenness, and the Local Fiedler Vector. These features capture diverse topological properties. Dimensionality reduction (PCA) projects these features onto a low-dimensional manifold. To define "normal" behavior, a Minimum Volume Ellipsoid (MVE) is fitted to the features, establishing a confidence region for anomaly detection.
Efficient Graph Entropy (VNGE)
Von Neumann graph entropy (VNGE) quantifies intrinsic network complexity. However, standard VNGE calculation requires the full eigenspectrum of the graph Laplacian, leading to a cubic complexity of $O(n^3)$. The authors introduce a quadratic approximation ($O(n^2)$) that is proven to be asymptotically consistent. This allows for real-time monitoring of large-scale networks without the prohibitive computational overhead.
Experimental Results: Cyber Intrusion Detection
The framework was evaluated using the UNB intrusion detection dataset, which tracks six days of network traffic. One sequence represents normal activity, while the second introduces Denial of Service (DoS) and infiltration attacks starting on Day 4.
Precise Detection and Visual Divergence
The centrality-based manifold approach successfully identified the bifurcation point. In the PCA-reduced feature space, the "normal" and "abnormal" trajectories diverge sharply at the onset of the attack. Statistical analysis confirmed this shift, with the P-value dropping below the 0.01 threshold by Day 4.
Entropy as a Diagnostic Signal
The results showed that VNGE decreases during an attack. This occurs because attacks like DoS increase network heterogeneity—flooding specific targets while leaving others idle—which reduces overall structural complexity compared to the balanced state of a healthy network. The quadratic approximation of VNGE accurately tracked these shifts with significantly reduced computational cost.
Discussion and Future Work
While the combination of centrality and entropy proves robust for bifurcation detection, the precise mathematical link between these two measures requires further theoretical exploration. Future work will aim to generalize these methods to biological systems, such as cell development, and extend the entropy approximation to directed graph structures.
Summary updated