Barabasi Albert Graph (para modelos sin escala)

El artículo actual trataría los conceptos relacionados con las redes complejas que utilizan la biblioteca Networkx de python. Es un paquete de software en lenguaje Python para la creación, manipulación y estudio de la estructura, dinámica y función de redes complejas. Con NetworkX puede cargar y almacenar redes en formatos de datos estándar y no estándar, generar muchos tipos de redes aleatorias y clásicas, analizar la estructura de la red, construir modelos de red, diseñar nuevos algoritmos de red, dibujar redes y mucho más. El artículo actual se ocuparía del algoritmo para generar redes libres de escala aleatoria para usar el modelo de conexión preferencial. El motivo de interés detrás de este modelo se remonta a la década de 1990, cuando Albert Lazlo Barabasi y Reka Albert presentaron una investigación pionera que describía el modelo seguido por las redes libres de escala en todo el mundo. Sugirieron que se cree que varios sistemas naturales y creados por el hombre, incluidos Internet, la World Wide Web, las redes de citas y algunas redes sociales, son redes aproximadamente libres de escala. Una red sin escala es una red cuya distribución de grados sigue una ley de potencia, al menos asintóticamente. Es decir, la fracción P (k) de Nodes en la red que tienen k conexiones a otros Nodes vale para valores grandes de k como Una red sin escala es una red cuya distribución de grados sigue una ley de potencia, al menos asintóticamente. Es decir, la fracción P (k) de Nodes en la red que tienen k conexiones a otros Nodes vale para valores grandes de k como Una red sin escala es una red cuya distribución de grados sigue una ley de potencia, al menos asintóticamente. Es decir, la fracción P (k) de Nodes en la red que tienen k conexiones a otros Nodes vale para valores grandes de k como Donde  es un parámetro cuyo valor está típicamente en el rango 2 < < 3, aunque en ocasiones puede estar fuera de estos límites y c es una constante de proporcionalidad. El modelo Barabási-Albert es uno de varios modelos propuestos que generan redes sin escala. Incorpora dos conceptos generales importantes: crecimiento y apego preferencial. Tanto el crecimiento como el apego preferencial existen ampliamente en las redes reales. Crecimiento significa que el número de Nodes en la red aumenta con el tiempo. La vinculación preferencial significa que cuanto más conectado está un Node, más probable es que reciba nuevos enlaces. Los Nodes con mayor grado tienen una mayor capacidad para capturar enlaces agregados a la red. Intuitivamente, el apego preferencial puede entenderse si pensamos en términos de redes sociales que conectan a las personas. Aquí, un enlace de A a B significa que la persona A «conoce» o «está familiarizada con» la persona B. Los Nodes fuertemente vinculados representan personas conocidas con muchas relaciones. Cuando un recién llegado ingresa a la comunidad, es más probable que se familiarice con una de esas personas más visibles que con un relativo desconocido. El modelo BA se propuso asumiendo que en la World Wide Web, las nuevas páginas enlazan preferentemente con hubs, es decir, sitios muy conocidos como Google, más que con páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. La siguiente imagen describirá el gráfico del modelo BA con 50 Nodes siguiendo el modelo de apego preferencial. es más probable que se familiarice con una de esas personas más visibles que con un desconocido relativo. El modelo BA se propuso asumiendo que en la World Wide Web, las nuevas páginas enlazan preferentemente con hubs, es decir, sitios muy conocidos como Google, más que con páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. La siguiente imagen describirá el gráfico del modelo BA con 50 Nodes siguiendo el modelo de apego preferencial. es más probable que se familiarice con una de esas personas más visibles que con un desconocido relativo. El modelo BA se propuso asumiendo que en la World Wide Web, las nuevas páginas enlazan preferentemente con hubs, es decir, sitios muy conocidos como Google, más que con páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. La siguiente imagen describirá el gráfico del modelo BA con 50 Nodes siguiendo el modelo de apego preferencial. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. La siguiente imagen describirá el gráfico del modelo BA con 50 Nodes siguiendo el modelo de apego preferencial. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. La siguiente imagen describirá el gráfico del modelo BA con 50 Nodes siguiendo el modelo de apego preferencial.

Modelo BA para 50 Nodes

El gráfico anterior satisface por completo la lógica de que los ricos se vuelven más ricos y los pobres más pobres. Código: El siguiente código es parte de la función que eventualmente implementaremos usando la biblioteca networkx. 

def barabasi_albert_graph(n, m, seed=None):
    """Returns a random graph according to the Barabási–Albert preferential
    Attachment model.
 
    A graph of ``n`` nodes is grown by attaching new nodes each with ``m``
    Edges that are preferentially attached to existing nodes with high degree.
 
    Parameters
    ----------
    n : int
        Number of nodes
    m : int
        Number of edges to attach from a new node to existing nodes
    seed : int, optional
        Seed for random number generator (default=None).
 
    Returns
    -------
    G : Graph
 
    Raises
    ------
    NetworkXError
        If ``m`` does not satisfy ``1 <= m < n``.
 
     
    if m < 1 or  m >=n:
        raise nx.NetworkXError("Barabási–Albert network must have m >= 1"
                               " and m < n, m = %d, n = %d" % (m, n))
    if seed is not None:
        random.seed(seed)
 
    # Add m initial nodes (m0 in barabasi-speak)
    G=empty_graph(m)
    G.name="barabasi_albert_graph(%s,%s)"%(n,m)
    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes=[]
    # Start adding the other n-m nodes. The first node is m.
    source=m
    while source<n:
        # Add edges to m nodes from the source.
        G.add_edges_from(zip(*m,targets))
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend(*m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachment)
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G

El código anterior es parte de la biblioteca networkx que se usa para manejar los gráficos aleatorios de manera eficiente en python. Uno tendrá que instalarlo antes de ejecutar el siguiente código. 

>>> import networkx as nx
>>> G= nx.barabasi_albert_graph(50,40)
>>> nx.draw(G, with_labels=True)

Para mostrar el gráfico anterior, utilicé la biblioteca matplotlib. Necesitamos instalarlo antes de la ejecución de los siguientes códigos. 

>>> import matplotlib.pyplot as plt
>>> plt.show()

Así que el código final parecía: 

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
 
>>> G= nx.barabasi_albert_graph(40,15)
>>> nx.draw(G, with_labels=True)
>>> plt.show()

Producción:

Modelo BA para 40 Nodes

Por lo tanto, me gustaría describir más sobre la biblioteca networkx y sus módulos, centrándome básicamente en la medida de centralidad de una red (especialmente los modelos sin escala). Referencias Puede leer más sobre el mismo en

• https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_modelo
• http://networkx.readthedocs.io/en/networkx-1.10/index.html

.