online read us now
Paper details
Number 2 - June 2019
Volume 29 - 2019
Lyapunov-based anomaly detection in preferential attachment networks
Diego Ruiz, Jorge Finke
Abstract
Network models aim to explain patterns of empirical relationships based on mechanisms that operate under various principles
for establishing and removing links. The principle of preferential attachment forms a basis for the well-known
Barabási–Albert model, which describes a stochastic preferential attachment process where newly added nodes tend to
connect to the more highly connected ones. Previous work has shown that a wide class of such models are able to recreate
power law degree distributions. This paper characterizes the cumulative degree distribution of the Barabási–Albert model
as an invariant set and shows that this set is not only a global attractor, but it is also stable in the sense of Lyapunov. Stability
in this context means that, for all initial configurations, the cumulative degree distributions of subsequent networks remain,
for all time, close to the limit distribution. We use the stability properties of the distribution to design a semi-supervised
technique for the problem of anomalous event detection on networks.
Keywords
network formation models, discrete event systems, stability, anomalous event detection