OptimizaciOptimizacióón de las mn de las méétricastricas
estructurales de grafosestructurales de grafosIng. Perla
Elizabeth CantIng. Perla Elizabeth Cantúú Cerda*, Dra. Cerda*, Dra.
SatuSatu Elisa Elisa SchaefferSchaeffer**
Universidad AutUniversidad Autóónoma de Nuevo Lenoma de Nuevo
Leóónn
Programa de Posgrado en IngenierPrograma de Posgrado en
Ingenieríía de Sistemasa de Sistemas
Vivimos en un mundo de sistemas, por ejemplo la Internet,
las neuronas de nuestro cerebro y hasta el metabolismo de
una célula. En los sistemas cada uno de sus elementos
están representados por vértices y las interacciones entre
ellos por aristas.
Un grafo G=(V,A), es una abstracción matemática de
situaciones donde se pueden representar los elementos y
sus relaciones. Por tanto un sistema se puede representar a
través de un grafo .
Debido a la complejidad que presentan algunos sistemas se
dicen que son redes complejas. Una red compleja se refiere
a un grafo con un gran número de elementos o vértices, que
se caracterizan por tener una estructura topológica no
trivial.
Redes sociales:
Redes de terroristas
Redes políticas
Redes académicas
Redes de tecnológicas:
Internet
Telecomunicaciones
Redes biológicas:
Cadenas alimenticias
Redes de proteínas,
genéticas y metabólicas
Realizar una investigación que muestre que combinación de
factores determinan la calidad, eficiencia y/o
vulnerabilidad
en la topología de una red compleja, y posteriormente
desarrollar una herramienta de software que ayude a
determinar la calidad en diferentes estructuras y
aplicaciones de grafos; a través del estudio de las
propiedades y métricas de los grafos.
Algunas de las características o propiedades que son
relevantes en la estructura topológica de un grafo son
[1,3]:
• Asortatividad (Assortativity)
• Intermediación (Betweenness Centrality)
• Eficiencia
• Robustez
• Vulnerabilidad
El objetivo de utilizar métricas o medidas de calidad, es
para
cuantificar las propiedades estructurales de un grafo.
Algunas métricas son [5]:
• Coeficiente de agrupamiento
• Diámetro de la red
• Distancia promedio
• Distribución del grado
Para más información, o bien si le gustaría unirse a nuestro
grupo de trabajo, contáctanos en:
Correo: [email protected]
[email protected]
Web: http://yalma.fime.uanl.mx/~perla
http://yalma.fime.uanl.mx/~elisa
PISIS: http://yalma.fime.uanl.mx/~pisis/
El Posgrado en Ingeniería de Sistemas (PISIS), de la
Universidad
Autónoma de Nuevo León (UANL), ofrece estudios de maestría y
doctorado en ingeniería de sistemas con concentración en
modelaje,
análisis y solución de problemas de la investigación de
operaciones.
Para poder estudiar la estructura topológica de un grafo,
varios modelos se han desarrollado en base a sus
propiedades estructurales, tales como:
Redes Aleatorias.
Las aristas se distribuyen aleatoriamente y por tanto los
vértices tienen el mismo grado esperado. La distribución del
grado sigue una distribución de Poisson
Redes Scale-Free ó Power-Law.
Independientemente del número de nodos, la distribución
del grado no cambia. Aquí se encuentra la Internet, redes de
proteínas y de metabolismo.
Redes Small-World
Un fenómeno que se presenta en las redes complejas.
Tienen un alto coeficiente de agrupamiento y una distancia
pequeña entre vértices. Ejemplos de estas redes son la red
eléctrica de los Estados Unidos y las redes sociales. Las
enfermedades se difunden mucho mas rápido [6].
Redes Exponenciales
La distribución del grado presenta un pico en “k” y después
cae exponencialmente para valores grandes de “k”. Entre
estas redes se encuentra la red de energía del sur de
California y la red de ferrocarriles de la India. En estas
redes
si un vértice falla, toda la red fallará.
Estudiar la estructura topológica de un grafo es de suma
importancia porque a través de este se puede:
• Responder a ataques o fallas en una red [2].
• Actuar a tiempo en desastres naturales.
• Se puede mejorar el drenaje pluvial, el tránsito de las
principales avenidas ó mejorar las capacidades ó flujo de
cualquier tipo de red [2].
• Actuar a tiempo en la propagación de enfermedades [4].
[1] A.H. Dekker y B.D. Colbert. Network robustness and
graph topology. In Proceedings of the 27th Australasian
conference on Computer science, vol.26, pp. 359–368,
Darlinghurst, Australia, 2004. Australian Computer Society,
Inc.
[2] J. Xu. Topological Structure and Analysis of
Interconnection Networks. Kluwer Academic Publishers,
2001.
[3] Da F. Costa, A. Rodrigues, G. Travieso, y P. R. Villas
Boas. Characterization of complex networks: A survey of
measurements. Inf. cond-mat/0505185, 2005.
[4] S.N. Dorogovtsev y J. Ferreira Mendes. Evolution of
Networks: From Biological Nets to the Internet and World
Wide Web. Oxford University Press, Oxford, UK, Enero 2003.
[5] W. Najjar y J.-L. Gaudiot. Network resilience: a measure
of network fault tolerance. Transactions on Computers,
39(2):174–181, 1990
[6] Duncan J. Watts y Steven H. Strogatz. Collective
dynamics of “small world” network. Nature, 393(6684): 440-
442, Junio 1998
La estructura topológica de una red o
simplemente la topología, consiste en
patrón que forman los vértices y las
aristas.
