1 of 57

Estrategias de ataque basadas en centralidad sobre redes complejas

Nahuel Almeira

2 of 57

Esquema

  • Motivación
  • Percolación
  • Medidas de centralidad
  • Ataques basados en centralidad
  • Nuestro aporte
  • Reflexiones finales

​

3 of 57

Motivación

De los sistemas complejos a los ataques en redes

4 of 57

Sistemas complejos

5 of 57

Redes complejas

6 of 57

Ejemplos de redes

Sociales

Biológicas

Tecnológicas

7 of 57

8 of 57

Ataques

Daños dirigidos

Fallas

Daños aleatorios

9 of 57

Robustas pero frágiles

Fallas

Ataques

10 of 57

Percolación

Marco teórico para el estudio de fallas y ataques

11 of 57

Percolación en redes complejas

12 of 57

Parámetro de orden y susceptibilidad

Tamaño relativo de la mayor componente

Tamaño medio de las componentes

13 of 57

Parámetro de orden y susceptibilidad

Tamaño relativo de la mayor componente

Tamaño medio de las componentes

14 of 57

Parámetro de orden y susceptibilidad

Tamaño relativo de la mayor componente

Tamaño medio de las componentes

15 of 57

Distribución de tamaños de componentes

~

16 of 57

Distribución de tamaños de componentes

~

17 of 57

Distribución de tamaños de componentes

~

18 of 57

Distribución de tamaños de componentes

~

19 of 57

Exponentes críticos

20 of 57

Exponentes críticos

Relaciones entre exponentes

21 of 57

Medidas de centralidad

Cuantificando la importancia de cada nodo

22 of 57

Métricas locales

  • Grado
  • h-index
  • Coreness
  • Influencia colectiva

23 of 57

Métricas globales

  • Eigenvector centrality
  • Closeness
  • Betweenness

24 of 57

Dimensiones de las métricas

  • Conceptual
  • Localidad
  • Complejidad computacional
  • Topológica vs dinámica

25 of 57

Ataques basados en centralidad

26 of 57

Clasificación de los ataques

Centralidad

Actualización

  • Inicial
  • Recalculado

​

Elementos a atacar

27 of 57

Algunos resultados

  • Ataque inicial por grado

​

  • Grado y betweenness, inicial y recalculado

​

  • Solución a percolación óptima

​

28 of 57

Estudios comparativos

29 of 57

Estudios comparativos

Eficacia

​

Correlaciones entre ataques

​

Complejidad computacional

30 of 57

Nuestro aporte

31 of 57

Grado

  • Medida local

​

  • Representa conectividad

​

  • Baja complejidad

computacional

  • Medida global

​

  • Interpretación en términos

de flujos

​

  • Alta complejidad

computacional

Betweenness

32 of 57

Estrategias de ataque

Grado

Betweenness

Random (Rnd)

Recalculado (RD)

Recalculado (RB)

Inicial (IB)

Inicial (ID)

33 of 57

Redes espaciales

Triangulación de Delaunay

Redes aleatorias

Modelo de Erdös-Rényi

34 of 57

Redes de Erdös-Rényi

Distribución de grado homogénea

Distribución de betweenness homogénea

  • Modelo simple
  • Sin correlaciones
  • Se pueden obtener resultados analíticos
  • No existen nodos “muy centrales”

35 of 57

Desempeño de los ataques

Betweenness

Grado

Random

36 of 57

Desempeño de los ataques

Betweenness

Grado

Random

37 of 57

Desempeño de los ataques

Betweenness

Grado

Random

38 of 57

Desempeño de los ataques

Betweenness

Grado

Random

39 of 57

Desempeño de los ataques

Betweenness

Grado

Random

40 of 57

Desempeño de los ataques

Betweenness

Grado

Random

41 of 57

Desempeño de los ataques

Betweenness

Grado

Random

42 of 57

Desempeño de los ataques

Betweenness

Grado

Random

43 of 57

Una transición abrupta

44 of 57

¿Transición de primer orden?

45 of 57

Redes de Delaunay

Distribución de grado homogénea

Distribución de betweenness heterogénea

  • Modelo de red planar
  • Densidad máxima (<k> = 6)
  • Comunicación eficiente

46 of 57

Desempeño de los ataques

Betweenness

Grado

Random

47 of 57

Desempeño de los ataques

Betweenness

Grado

Random

48 of 57

Desempeño de los ataques

Betweenness

Grado

Random

49 of 57

Transición de primer orden

Betweenness recalculado

50 of 57

Betweenness acotado

Métrica local

Métrica global

51 of 57

¿Es conveniente recalcular la centralidad?

Betweenness

Grado

Random

52 of 57

¿Es conveniente recalcular la centralidad?

RD

ID

53 of 57

Reflexiones finales

54 of 57

Limitaciones de los modelos

55 of 57

Detección de influencers

56 of 57

Colaboradores

Orlando Billoni

Juan Perotti

Andrés Chacoma

57 of 57

¡Gracias!

Contacto

nalmeira@unc.edu.ar

​

¿Preguntas?