<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Lyapunov–based Anomaly Detection in Preferential Attachment Networks

Department of Electrical Engineering and Computer Science

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Lyapunov\u2013based Anomaly Detection in Preferential Attachment Networks"}

Network models aim to explain patterns of empirical relationships based on mechanisms that operate under various principles for establishing and removing...

Lyapunov–based Anomaly Detection in Preferential Attachment Networks

Publié en ligne: 04 juil. 2019

Pages: 363 - 373

Reçu: 01 juin 2018

Accepté: 18 janv. 2019

DOI: https://doi.org/10.2478/amcs-2019-0027

Mots clés
network formation models, discrete event systems, stability, anomalous event detection

© 2019 Diego Ruiz et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Lyapunov–based Anomaly Detection in Preferential Attachment Networks

Publié en ligne: 04 juil. 2019

Pages: 363 - 373

Reçu: 01 juin 2018

Accepté: 18 janv. 2019

DOI: https://doi.org/10.2478/amcs-2019-0027

Mots clésnetwork formation models, discrete event systems, stability, anomalous event detection

© 2019 Diego Ruiz et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
network formation models, discrete event systems, stability, anomalous event detection