Lyapunov-based anomaly detection in preferential attachment networks

Ruiz, Diego ; Finke, Jorge

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 2, pp. 363-373.

Résumé

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.

Détail

Keywords: network formation model, discrete event system, anomalous event detection
Mots-clés : model tworzenia sieci, układ zdarzeń dyskretnych, wykrywanie anomalii

Bibliographie

[1] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks, Science 286(5439): 509–512.

[2] Barabási, A.-L. and Pósfai, M. (2016). Network Science, Cambridge University Press, Cambridge.

[3] Bianconi, G. and Barabási, A. L. (2001). Competition and Multiscaling in evolving networks, Europhysics Letters 54(4): 436–442.

[4] Burgess, K. and Passino, K. (1995). Stability analysis of load balancing systems, International Journal of Control 61(2): 357–393.

[5] Caldarelli, G., Capocci, A., De Los Rios, P. and Muñoz, M.A. (2002). Scale-free networks from varying vertex intrinsic fitness, Physical Review Letters 89(25): 258702.

[6] Chandola, V., Banerjee, A. and Kumar, V. (2009). Anomaly detection: A survey, ACM Computing Surveys 41(3): 15:1–15:58.

[7] Chen, Q. and Shi, D. (2004). The modeling of scale-free networks, Physica A: Statistical Mechanics and Its Applications 335(1): 240–248.

[8] Choromanski, K., Matuszak, M. and Miekisz, J. (2013). Scale-free graph with preferential attachment and evolving internal vertex structure, Journal of Statistical Physics 151(6): 1175–1183.

[9] Dorogovtsev, S.N., Mendes, J.F.F. and Samukhin, A.N. (2000). Structure of growing networks with preferential linking, Physical Review Letters 85(21): 4633–4636.

[10] Gogoi, P., Bhattacharyya, D., Borah, B. and Kalita, J.K. (2011). A survey of outlier detection methods in network anomaly identification, The Computer Journal 54(4): 570–588.

[11] Hirose, S., Yamanishi, K., Nakata, T. and Fujimaki, R. (2009). Network anomaly detection based on eigen equation compression, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, pp. 1185–1194.

[12] Host-Madsen, A. and Zhang, J. (2018). Coding of graphs with application to graph anomaly detection, 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA, pp. 1829–1833.

[13] Jackson, M.O. and Rogers, B.W. (2007). Meeting strangers and friends of friends: How random are social networks?, American Economic Review 97(3): 890–915.

[14] Khalil, H. (2001). Nonlinear Systems, 3rd Edn., Pearson, Upper Saddle River, NJ.

[15] Koutra, D., Shah, N., Vogelstein, J.T., Gallagher, B. and Faloutsos, C. (2016). DELTACON: Principled massive-graph similarity function with attribution, ACM Transactions on Knowledge Discovery Data 10(3): 28:1–28:43.

[16] Kudĕlka, M., Zehnalová, Š., Horák, Z., Krömer, P. and Snášel, V. (2015). Local dependency in networks, International Journal of Applied Mathematics and Computer Science 25(2): 281–293, DOI: 10.1515/amcs-2015-0022.

[17] Lee, C.-Y. (2006). Correlations among centrality measures in complex networks, arXiv: 0605220.

[18] Moriano, P. and Finke, J. (2012). Power-law weighted networks from local attachments, Europhysics Letters 99(1): 18002.

[19] Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C. and Samatova, N.F. (2015). Anomaly detection in dynamic networks: A survey, WIREs Computational Statistics 7(3): 223–247.

[20] Ruiz, D. and Finke, J. (2013). Invalidation of dynamic network models, Proceedings of the American Control Conference, Washington, DC, USA, pp. 138–143.

[21] Savage, D., Zhang, X., Yu, X., Chou, P. and Wang, Q. (2014). Anomaly detection in online social networks, Social Networks 39(C): 62–70.

[22] Segarra, S. and Ribeiro, A. (2016). Stability and continuity of centrality measures in weighted graphs, IEEE Transactions on Signal Processing 64(3): 543–555.

[23] Shao, Z.-G., Zou, X.-W., Tan, Z.-J. and Jin, Z.-Z. (2006). Growing networks with mixed attachment mechanisms, Journal of Physics A: Mathematical and General 39(9): 2035.

[24] Shoubridge, P., Kraetzl, M., Wallis,W.D. and Bunke, H. (2002). Detection of abnormal change in a time series of graphs, Journal of Interconnection Networks 3(01n02): 85–101.

[25] Tong, J., Hou, Z., Zhang, Z. and Kong, X. (2009). Degree correlations in the group preferential model, Journal of Physics A: Mathematical and Theoretical 42(27): 275002.

[26] Valente, T.W., Coronges, K., Lakon, C. and Costenbader, E. (2008). How correlated are network centrality measures?, Connections 28(1): 16–26.

[27] Yu, R., Qiu, H.,Wen, Z., Lin, C.-Y. and Liu, Y. (2016). A survey on social media anomaly detection, SIGKDD Explorations 18(1): 1–14.