Anomaly detection in dynamic networks

Seminario I 2024-I

Andreina Alamo, Zaith Moreno, Diego Useche

Universidad Nacional de Colombia

Introducción

En este estudio se analizan datos sobre interacciones entre hormigas mediante el algoritmo de detección de anomalías en redes dinámicas denominado oddnet.

El conjunto de datos consiste en registros de interacciones entre individuos de una colonia a lo largo del tiempo, se construye una red dinámica donde los nodos representan hormigas y las aristas sus interacciones. Nuestro objetivo es identificar comportamientos anómalos que puedan indicar eventos significativos como enfermedades o cambios en la estructura social.

Algoritmo oddnet

Aplicación

La red dinámica representa una colonia de hormigas. Los autores registraron la posición y orientación de todos los individuos dos veces por segundo para reconstruir el movimiento espacial e inferir todas las interacciones sociales que se produjeron a lo largo de los 41 días que duró el experimento

Datos (insecta-ant-colony4)

Tipo Conjuntos de datos de redes del mundo real procedentes de estudios publicados sobre animales salvajes, cautivos y domesticados.
Nodos y enlaces 102 y 81.6K
Enlace Interacción
Red No dirigida

Interacción

Algunas funciones detrás del código

  1. igraph::count_triangles # de triángulos conectados a c/nodo.
  2. igraph::degree # de aristas conectado a cada nodo.
  3. igraph::edge_density # de aristas observadas/total posibles aristas.
  4. igraph::gsize Total de aristas en \(\mathcal{G}_t\).

  1. igraph::transitivity (amigos de amigos):Proporción de nodos cuyos nodos adyacentes también están conectados.

  2. igraph::assortativity.nominal y igraph::assortativity_degree Medición de la homofilia del grafo, basándose en las etiquetas de los nodos.

  3. igraph::mean_distance calcula la media de todos los caminos entre diferentes nodos.

  1. igraph::diameter Distancia más grande del grafo.

  2. igraph::page_rank Se calcula el PageRank de todos los vértices y se toma el cuantil \(99^ {th }\).

  3. igraph::coreness El núcleo \(k\) de un grafo: subgrafo máximo con un grado mínimo de al menos \(k\). Es decir, cada vértice de un núcleo \(k\) tiene un grado mayor que \(k\). Se calcula coreness para todos los vértices y se incluye el cuantil \(99\).

Otras funciones de igraph: closeness, clusters, global_efficiency, cohesion, betweenness, hub_score y authority_score.

  1. fabletools::model(arima = fable::ARIMA(value)) Ajuste automático de los modelos ARIMA a cada serie.
  2. pcaPP::PCAproj PCA robusto para reducir la dimensión a dos componentes.
  3. lookout::lookout Algoritmo Lookout para detectar anomalías en datos bidimensionales.

  1. igraph:plot.graph: Función para graficar redes con la librería base de R.

  2. ggraph:ggraph: Función para graficar redes con la librería ggplot2.

Grafica de la red dinámica

Aplicación a las redes de hormigas

Code 
networks <- list()
graphs <- list()
for (i in 1:length(ant41_red_list)) {
  gr <- graph_from_data_frame(ant41_red_list[[i]])
  graphs[[i]] <- gr
  networks[[i]] <- as_adjacency_matrix(gr)
}

anom <- anomalous_networks(networks,alpha = 0.05, fast = T)
anom
Leave-out-out KDE outliers using lookout algorithm

Call: lookout::lookout(X = dfpca[, 1:dd], alpha = alpha)

  Outliers Probability
1       12           0

Gráfica de las probabilidades condicionales

Red anómala día 12

Gráfico de las series de tiempo

Conclusiones

El algoritmo propuesto por Sevvandi & Hyndman(2022) resulta efectivo a la hora de detectar algunos cambios en la colonia. En particular detecta inmediatamente la disminución de relaciones entre las hormigas y la reducción de individuos.

Sin embargo, el algoritmo no es capaz de detectar el comportamiento anómalo del individuo que se observa en el día doce, el cuál solo tiene dos aristas, esto es debido a que en el proceso de extracción de características solo se tiene en cuenta cuando el grado se incrementa (cuantil 99) y no cuando disminuye. Por lo que se recomienda adicionar una característica que represente disminución de aristas incidentes de los nodos.

Bibliografía

  • Akoglu, L., Tong, H. & Koutra, D. (2015), ‘Graph based anomaly detection and description: A survey’, Data Mining and Knowledge Discovery 29(3), 626–688.
  • Albert, R. & Barabasi, A.-L. (2002), ‘Statistical mechanics of complex networks’, Reviews of modern physics 74(1), 47.
  • Almquist, Z. W. & Butts, C. T. (2013), ‘Dynamic network logistic regression: A logistic choice analysis of inter- and intra-group blog citation dynamics in the 2004 US presidential election’, Political Analysis 21(4), 430–448.
  • Barabasi, A.-L. & Albert, R. (1999), ‘Emergence of scaling in random networks’, Science 286(5439), 509–512.

¡Gracias!