Estudio de propiedades topológicas de redes complejas

Abstract

Un grafo o red en su definición más simple es un conjunto de puntos y lineas [57]. El cual tiene propiedades topológicas como son: El diámetro del grafo, el coeficiente de agrupamiento y la distribución de conectividad. El diámetro del grafo, es la distancia más larga de las distancias más cortas de un vértice origen a un destino. Un triángulo esta formado por tres vértices interconectados, entonces el coeficiente de agrupamiento, es la sumatoria de todos los triángulos que tiene un grafo entre todos los triángulos posibles que puede tener el grafo. La distribución de probabilidad se obtiene de la conectividad que tiene cada vértice del grafo. La teoría de grafos aleatorios de Erdós & Rényi, fue desarrollada en 1959, donde la teoría mostraba herramientas para grafos aleatorios sin crecimiento y con crecimiento, las cuales fueron de gran utilidad para hacer estudios más profundos sobre grafos y retomar algunos estudios de los que se quedaron inconclusos, también aparecieron las computadoras que ayudaron a que se procesaran más datos y con ello hacer estudios con mayor volumen de información, como fueron los estudios que se hicieron sobre el Internet, la www y cita de artículos a finales de los 90’s, entonces se demostró que las redes reales no se comportaban como redes aleatorias, ya que mostraban otras propiedades que no tienen las redes aleatorias como son un diámetro corto, una distribución de conectividad en forma ley de potencia, etc. Motivado por estos resultados, el Dr. Barabási en 1999, propone el primer modelo de crecimiento de red compleja, el cual es un modelo de red sencillo con crecimiento por agregación y conectividad preferencial, del cual se pudo obtener una distribución de conectividad en forma de ley de potencia y que sirvió de estímulo para que otros investigadores que se dieron a la tarea de proponer nuevos modelos donde se pudieran mostrar otras propiedades de las redes complejas, y se acercaran a las redes reales, tales como el recableado, aptitud, atractivo inicial, etc. Lo cual los ayudó a entender mejor a las redes, ya que hay redes reales con la propiedad de nacimiento y muerte de enlaces, como es el Internet, www, etc. y también redes reales sin nacimiento ni muerte de enlaces, como son la cita de artículos y la cita de patentes de Estados Unidos, y que, sin embargo, de las redes reales se puede obtener una distribución de conectividad ley de potencia de enlaces entrantes y de enlaces salientes. Para poder contribuir con un granito de arena en estos estudios de redes, se estudiaron muchos modelos ya propuestos hasta ahora y se descubrió que muestran una distribución ley potencia de los enlaces entrantes, y que los modelos que muestran una distribución de los enlaces salientes tienen nacimiento y muerte de enlaces. Se puede explicar como obtener una distribución ley de potencia en los enlaces entrantes debido a la conectividad preferencial, pero no se puede explicar como generar una distribución de enlaces salientes en forma de ley potencia. Por lo tanto, se revisó el modelo de copiado de Krapivsky [47], ya que el copiado podría servir para obtener ese resultado, sin embargo, el resultado que se obtuvo fue una distribución exponencial de los enlaces salientes, también se revisó el modelo propuesto por Ameerah [2], el cual se basa en krapivsky [45] y si se obtiene la distribución ley de potencia en el outdegree, pero artificiosamente se obtiene el número de enlaces salientes del nodo nuevo, lo cual no es natural. De manera que, no existe un modelo de red sin nacimiento y muerte de enlaces, y que se pueda obtener una distribución en forma de ley de potencia de enlaces salientes y entrantes. Por eso mi principal objetivo es proponer un modelo de crecimiento de red compleja donde se pueda obtener una distribución ley de potencia de enlaces entrantes y salientes, y que la red no acepte nacimiento y muerte de enlaces en nodos existentes. Para esto, se creó un modelo de crecimiento de red compleja con probabilidad p, donde con probabilidad p, se selecciona un nodo aleatorio y se copian sus enlaces, y con probabilidad 1 − p, se selecciona un número aleatorio de enlaces, el número aleatorio de enlaces está entre 1 : N nodos, se obtiene como resultado una distribución de enlaces entrantes en forma de ley de potencia cuando la probabilidad p → 1 y en los demás valores de p, una distribución de enlaces entrantes en forma exponencial. Se analizó el grado de los nodos en este modelo, y se observó que se incrementa conforme aumenta el número total de nodos en la red, a este fenómeno se le conoce como aceleración [24] y también produce un efecto en la distribución de enlaces entrantes, en el que de una red 1000 a 10,000 nodos varía el exponente, por ejemplo en este modelo tenemos con probabilidad p = 0.99, en una red de 1000 nodos se obtiene una distribución de enlaces entrantes con exponente γin ≈ 3.3 y con 10,000 nodos se obtiene un exponente γin ≈ 4.3. Para poder comparar los resultados del modelo con redes reales, se revisó los datos de la red cita de patentes de los Estados Unidos (Respaldo de cita de patentes desde el año 1975 a 1999), en la cual cuando se crea una patente, se cita a patentes ya existentes, pero a una patente que ya existe no se le puede agregar o eliminar las citas que haya hecho a otras patentes, por esta razón, esta red no tiene nacimiento ni muerte de enlaces, se obtuvo su distribución de enlaces salientes para 106 nodos y para 2 ∗ 106 nodos y se pudo observar que varia el exponente de la distribución de enlaces salientes en forma de ley de potencia.