=Paper=
{{Paper
|id=Vol-1727/ssn16-final9
|storemode=property
|title=Robustness Metrics for Network Analysis
|pdfUrl=https://ceur-ws.org/Vol-1727/ssn16-final9.pdf
|volume=Vol-1727
|authors=Fernando Morales
|dblpUrl=https://dblp.org/rec/conf/ssn/Morales16
}}
==Robustness Metrics for Network Analysis==
https://ceur-ws.org/Vol-1727/ssn16-final9.pdf
Robustness Metrics for Network Analysis
Fernando Morales
Departamento de
Ciencias de la Computación
NIC Chile Research Labs
Universidad de Chile
fernando@niclabs.cl
Abstract
The Internet nowadays is vital for work and
government, Chile is not an exception. Its slim
and extended shape does not allow redun-
dancy in its networks, hence subject to ha-
zards like earthquakes or avalanches. To ob-
tain a clear vision about these risks, the ro-
bustness of the network infrastructure must
be properly measured. This work pretends to
perform an exhaustive review of the scientific
literature about robustness metrics in complex
networks. Afterwards, a metric and improve-
ments recommendations will be presented.
1. Introducción
Chile es un paı́s altamente sı́smico con una geografı́a
Figura 1: Mapa de rutas de Chile1 .
diversa, cuya larga y estrecha forma no hace natural el
tener infraestructura de telecomunicaciones redundan- de la infraestructura Internet (En el 2015, la penetra-
te. La enorme mayorı́a de las fibras ópticas que inter- ción de Internet en Chile alcanza los 64,2 accesos por
conectan el paı́s pasan a metros de la Ruta 5 (Figura cada 100 habitantes2 ), y la enorme penetración de las
1), y la probabilidad de cortes masivos son demasia- redes sociales la hace una infraestructura crı́tica para
do altas. En varias emergencias ya sean naturales o los casos de emergencia. Idealmente, la Internet debie-
artificiales, el paı́s ha presenciado como el servicio de ra estar disponible y operativa el 100 % del tiempo,
Internet y telefónico se ve interrumpido sin aviso en incluso durante un gran desastre, de modo que la gen-
grandes superficies del territorio, dejando aislados a te logre comunicarse, tranquilizarse y organizarse sin
miles de compatriotas. espacio para el pánico que genera el no tener noticias
Actualmente, la ciudadanı́a, el gobierno y las em- de nuestros seres queridos.
presas se han ido volviendo cada vez más dependientes Subtel ha hecho grandes esfuerzos financiando pro-
yectos de telecomunicaciones en todo el paı́s, sin em-
Copyright c 2016 by the paper’s authors. Copying permitted
for private and academic purposes. This volume is published
bargo la necesidad de la población no solo es tener
and copyrighted by its editors. conectividad en tiempos normales, sino que esta sea
This work was partially funded by CORFO 15BPE-47225: ”Es- robusta, que resista con cierto grado de certeza las in-
tudio y recomendaciones sobre la resiliencia de la infraestructura
del internet chileno”. 2 http://www.subtel.gob.cl/estudios-y-estadisticas/
1 http://www.mapas.mop.cl internet/
clemencias propias de nuestra naturaleza. Dado este Este trabajo de tesis busca, en primer lugar, realizar
contexto, es importante estudiar la robustez de nues- un estudio de mapeo sistemático [Kee07], el cual permi-
tra red. En el año 2015 la CORFO aprobó un proyecto ta reconocer en la literatura cientı́fica: Qué métricas
que planea estudiar y evaluar la robustez de la infraes- existen para estudiar la robustez en redes com-
tructura de la Internet chilena. Dentro de los alcances plejas. A partir de este estudio, se realizará un análi-
de este proyecto, se pretende desarrollar una métrica sis de la red chilena dada sus caracterı́sticas (pocos
basada en teorı́a de grafos para medir matemática- proveedores de Internet y redes concentradas) presen-
mente qué tan robusta es la Internet chilena y, en base tando una recomendación de las métricas aplicables.
a esos resultados, proponer mejoras para que nuestro Ası́ el paı́s estará mejor preparado para seguir co-
paı́s entero este más preparado para emergencias. nectado ante emergencias y desastres de toda ı́ndole,
En el ámbito cientı́fico, bajo el tópico de las redes además de contar con infraestructura de alta capaci-
complejas, se han desarrollado diversas métricas que dad en sectores que otorguen redundancia en ruteo de
miden de alguna forma en particular la robustez de datos nacional.
una red [MKF+ 06, DC04, Fre77, DH07, EK10]. Pero
todavı́a no existe una visión global completa y clara de
éstos indicadores. Existen estudios que resumen par- 2. Metodologı́a
cialmente estas métricas, pero todavı́a ningún estudio Con el fin de realizar una revisión imparcial, se desa-
realiza un mapeo a través de varios temas o aplicacio- rrolla un protocolo de estudio de mapeo sistemático.
nes grandes de redes complejas. A modo de ejemplo, Éste consiste en desarrollar una búsqueda objetiva y
en el siguiente cuadro se muestran algunas de estas exaustiva en la literatura ciéntifica acerca de alguna
métricas según dos enfoques [SSSK08]. El clásico, se pregunta planteada. En todo protocolo se definen los
basa en la topologı́a y fundamentos matemáticos de siguientes pasos:
teorı́a de grafos (clique, grado, camino más corto); y
el contemporáneo se refiere a la habilidad de una red
Antecedentes.
para mantener su flujo total (o degradarse suavemen-
te) ante la eliminación de nodos y aristas, tomando en
Preguntas de estudio.
cuenta los posibles servicios de la red.
Estrategia.
Enfoque Nombre
Average Nodal degree (hki) Criterio(s) de selección de estudio.
Node connectivity (κ)
Proceso de selección de estudios.
Link connectivity (ρ)
p
Heterogeneity ( σk2 /hki) Valoración de calidad de los estudios.
Clásico Symmetry ratio (/(D + 1))
Diameter (D) Extracción de datos.
Average shortest-path length (hli)
Análisis de datos.
Assortativity coefficient (r)
knn
Average neighbour connectivity ( ) Método(s) de publicación de los resultados.
|v| − 1
Clustering coefficient (hCi)
Betweenness centrality (hbi) 3. Resultados
Algebraic connectivity (µ|v|−1 ) Como resultado se espera obtener un listado de
Average two-Terminal Reliability (A2TR) métricas que permita agruparlas según su origen y
Elasticity (E) aplicación. Cada métrica estará detallada con su nom-
bre, definición, interpretación, aplicación y origen. Es-
Quantitative Robustness Metric (QNRM)
Contemporáneo to posibilita una clara visión global para el análisis de
Qualitative Robustness Metric (QLRM)
la red chilena. Otro resultado son las recomendaciones
R-value (R) de las métricas propuesto por el análisis mencionado
Viral Conductance (VC) anteriormente.
Una posible extensión de estos resultados, es evaluar
Tabla 1: Metricas de robustez divididas según el enfoque qué tan citada es esta métrica, para medir su popula-
clásico y contemporáneo. ridad y utilidad.
Nombre Definición
Porcentajes de nodos de demanda que tienen acceso al servicio por al menos
Supply Availability
un nodo de servicio.
La cantidad de nodos de la sub-red funcional más grande (es decir, un red la
Network Connectivity
cual todos sus nodos poseen de demanda acceso al servicio).
El recı́proco del promedio del largo de cada camino más corto para cada
Best Delivery Efficiency
nodo de demanda hacia un nodo de servicio.
El promedio de los inversos del largo de cada camino más corto para cada
Average Delivery Efficiency nodo de demanda hacia todos los nodos de servicio, ajustado por un factor
de peso por cada camino.
Tabla 2: Tabla resumen de las métricas basadas en red de servicios.
3.1. Trabajo actual [MKF+ 06] Priya Mahadevan, Dmitri Krioukov, Mari-
na Fomenkov, Xenofontas Dimitropoulos,
Se obtuvieron alrededor de 130 resultados positivos
Amin Vahdat, et al. The internet as-level
en revisión sistemática. Se han estudiado un 33 % de
topology: three data sources and one defi-
los artı́culos seleccionados.
nitive metric. ACM SIGCOMM Compu-
A priori, dada la situación chilena, la métrica reco-
ter Communication Review, 36(1):17–26,
mendada priorizará los servicios de la red de manera
2006.
que el flujo se mantenga con la eliminación de nodos o
aristas. [SSSK08] Ali Sydney, Caterina Scoglio, Phillip
Se destacan unas métricas para el caso chileno ba- Schumm, and Robert E Kooij. Elasticity:
sadas en un enfoque de red de servicios. Estas métricas topological characterization of robustness
mezclan las nociones de robustez con cobertura de la in complex networks. In Proceedings of
red. Es decir, que proporción de nodos son abastecidos the 3rd International Conference on Bio-
con el servicio (En nuestro caso, acceso a Internet) y Inspired Models of Network, Information
qué tan fácil es bloquear este servicio (mediante eli- and Computing Sytems, page 19. ICST
minación de nodos). Zhao et al. [ZKY11] definen 4 (Institute for Computer Sciences, Social-
métricas bajo este concepto, resumidas en el cuadro 2. Informatics and Telecommunications En-
gineering), 2008.
Referencias
[ZKY11] Kang Zhao, Akhil Kumar, and John
[DC04] Anthony H Dekker and Bernard D Col- Yen. Achieving high robustness in
bert. Network robustness and graph to- supply distribution networks by rewiring.
pology. In Proceedings of the 27th Aus- IEEE Transactions on Engineering Mana-
tralasian conference on Computer science- gement, 58(2):347–362, 2011.
Volume 26, pages 359–368. Australian
Computer Society, Inc., 2004.
[DH07] Jun Dong and Steve Horvath. Understan-
ding network concepts in modules. BMC
systems biology, 1(1):24, 2007.
[EK10] David Easley and Jon Kleinberg. Net-
works, crowds, and markets: Reasoning
about a highly connected world. Cambridge
University Press, 2010.
[Fre77] Linton C Freeman. A set of measures of
centrality based on betweenness. Socio-
metry, pages 35–41, 1977.
[Kee07] Staffs Keele. Guidelines for performing
systematic literature reviews in software
engineering. In Technical report, Ver. 2.3
EBSE Technical Report. EBSE. 2007.