Centralidad de intermediación (medida de centralidad)

Posted on by Rudeus Greyrat

En la teoría de grafos, la centralidad de intermediación es una medida de centralidad en un gráfico basada en los caminos más cortos. Para cada par de vértices en un gráfico conectado, existe al menos un camino más corto entre los vértices, de modo que el número de aristas por las que pasa el camino (para gráficos no ponderados) o la suma de los pesos de los aristas (para gráficos ponderados ) se minimiza. 

La centralidad de intermediación para cada vértice es el número de estos caminos más cortos que pasan por el vértice. La centralidad de intermediación encuentra una amplia aplicación en la teoría de redes: representa el grado en que los Nodes se interponen entre sí. Por ejemplo, en una red de telecomunicaciones, un Node con mayor centralidad de intermediación tendría más control sobre la red, porque pasará más información a través de ese Node. La centralidad de intermediación se concibió como una medida general de centralidad: se aplica a una amplia gama de problemas en la teoría de redes, incluidos problemas relacionados con redes sociales, biología, transporte y cooperación científica. 

Definición 

La centralidad de intermediación de un Node {\ Displaystyle v} v viene dada por la expresión:

 g(v)=\sum _{{s\neq v\neq t}}{\frac {\sigma _{{st}}(v)}{\sigma _{{st}}}}

donde \sigma_{st} es el número total de caminos más cortos de Node  s a Node  t y  \sigma_{st}(v) es el número de esos caminos que pasan por  v . 

Tenga en cuenta que la centralidad de intermediación de un Node escala con el número de pares de Nodes como lo implican los índices de suma. Por lo tanto, el cálculo se puede reescalar dividiendo por el número de pares de Nodes sin incluir  v , de modo que  g\in [0,1] . La división se realiza  (N-1)(N-2) para grafos dirigidos y  (N-1)(N-2)/2 para grafos no dirigidos, donde  N es el número de Nodes en el componente gigante. Tenga en cuenta que esto se escala para el valor más alto posible, donde un Node es cruzado por cada ruta más corta. A menudo, este no es el caso, y se puede realizar una normalización sin pérdida de precisión.

{\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}

lo que resulta en: 

\max(normal)=1

\min(normal)=0

Tenga en cuenta que esto siempre será una escala de un rango más pequeño a un rango más grande, por lo que no se pierde precisión. 

Redes ponderadas 

En una red ponderada, los enlaces que conectan los Nodes ya no se tratan como interacciones binarias, sino que se ponderan en proporción a su capacidad, influencia, frecuencia, etc., lo que agrega otra dimensión de heterogeneidad dentro de la red más allá de los efectos topológicos. La fuerza de un Node en una red ponderada viene dada por la suma de los pesos de sus bordes adyacentes.

s_{{i}}=\sum _{{j=1}}^{{N}}a_{{ij}}w_{{ij}}

Siendo a_{ij} y  w_{ij} siendo arrays de adyacencia y peso entre Nodes  i y  j , respectivamente. De manera análoga a la distribución de grado de la ley de potencia que se encuentra en las redes libres de escala, la fuerza de un Node dado también sigue una distribución de ley de potencia. 

s(k)\approx k^{\beta }

Un estudio del valor promedio  s(b) de la fuerza para vértices con intermediación  b muestra que el comportamiento funcional se puede aproximar mediante una forma de escala

 s(b)\approx b^{{\alpha }} .

A continuación se muestra el código para el cálculo de la centralidad de intermediación del grafo y sus diversos Nodes. 

Implementación:

Python

def betweenness_centrality(G, k=None, normalized=True, weight=None,
                        endpoints=False, seed=None):
    r"""Compute the shortest-path betweenness centrality for nodes.
 
    Betweenness centrality of a node $v$ is the sum of the
    fraction of all-pairs shortest paths that pass through $v$
 
    .. math::
 
    c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}
 
    where $V$ is the set of nodes, $\sigma(s, t)$ is the number of
    shortest $(s, t)$-paths, and $\sigma(s, t|v)$ is the number of
    those paths passing through some node $v$ other than $s, t$.
    If $s = t$, $\sigma(s, t) = 1$, and if $v \in {s, t}$,
    $\sigma(s, t|v) = 0$ [2]_.
 
    Parameters
    ----------
    G : graph
    A NetworkX graph.
 
    k : int, optional (default=None)
    If k is not None use k node samples to estimate betweenness.
    The value of k <= n where n is the number of nodes in the graph.
    Higher values give better approximation.
 
    normalized : bool, optional
    If True the betweenness values are normalized by `2/((n-1)(n-2))`
    for graphs, and `1/((n-1)(n-2))` for directed graphs where `n`
    is the number of nodes in G.
 
    weight : None or string, optional (default=None)
    If None, all edge weights are considered equal.
    Otherwise holds the name of the edge attribute used as weight.
 
    endpoints : bool, optional
    If True include the endpoints in the shortest path counts.
 
    Returns
    -------
    nodes : dictionary
    Dictionary of nodes with betweenness centrality as the value.
 
     
    Notes
    -----
    The algorithm is from Ulrik Brandes [1]_.
    See [4]_ for the original first published version and [2]_ for details on
    algorithms for variations and related metrics.
 
    For approximate betweenness calculations set k=#samples to use
    k nodes ("pivots") to estimate the betweenness values. For an estimate
    of the number of pivots needed see [3]_.
 
    For weighted graphs the edge weights must be greater than zero.
    Zero edge weights can produce an infinite number of equal length
    paths between pairs of nodes.
 
     
    """
    betweenness = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
    if k is None:
        nodes = G
    else:
        random.seed(seed)
        nodes = random.sample(G.nodes(), k)
    for s in nodes:
 
        # single source shortest paths
        if weight is None: # use BFS
            S, P, sigma = _single_source_shortest_path_basic(G, s)
        else: # use Dijkstra's algorithm
            S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
 
        # accumulation
        if endpoints:
            betweenness = _accumulate_endpoints(betweenness, S, P, sigma, s)
        else:
            betweenness = _accumulate_basic(betweenness, S, P, sigma, s)
 
    # rescaling
    betweenness = _rescale(betweenness, len(G), normalized=normalized,
                        directed=G.is_directed(), k=k)
    return betweenness

La función anterior se invoca usando la biblioteca networkx y una vez que la biblioteca está instalada, eventualmente puede usarla y el siguiente código debe escribirse en python para la implementación de la centralidad de intermediación de un Node. 

Python

>>> import networkx as nx
>>> G=nx.erdos_renyi_graph(50,0.5)
>>> b=nx.betweenness_centrality(G)
>>> print(b)

El resultado de esto es: 

{0: 0.01220586070437195, 1: 0.009125402885768874, 2: 0.010481510111098788, 3: 0.014645690907182346, 
4: 0.013407129955492722, 5: 0.008165902336070403, 6: 0.008515486873573529, 7: 0.0067362883337957575, 
8: 0.009167651113672941, 9: 0.012386122359980324, 10: 0.00711685931010503, 11: 0.01146358835858978, 
12 : 0.010392276809830674, 13: 0.0071149912635190965, 14: 0.011112503660641336, 15: 0.008013362669468532,
16: 0.01332441710128969, 17: 0.009307485134691016, 18: 0.006974541084171777, 19: 0.006534636068324543, 
20: 0.007794762718607258, 21: 0.012297442232146375, 22: 0.011081427155225095, 23: 0.018715475770172643,
24: 0.011527827410298818 , 25: 0,012294312339823964, 26: 0,008103941622217354, 27: 0,011063824792934858,
28: 0.00876321613116331, 29: 0.01539738650994337, 30: 0.014968892689224241, 31: 0.006942569786325711,
32: 0.01389881951343378, 33: 0.005315473883526104, 34: 0.012485048548223817, 35: 0.009147849010405877,
36: 0.00755662592209711, 37: 0.007387027127423285, 38: 0.015993065123210606, 39: 0.0111516804297535,
40: 0.010720274864419366, 41: 0.007769933231367805, 42: 0.009986222659285306, 43: 0.005102869708942402,
44: 0.007652686310399397, 45: 0.017408689421606432, 46: 0.008512679806690831, 47: 0.01027761151708757, 
48: 0.008908600658162324, 49: 0.013439198921385216}

El resultado anterior es un diccionario que representa el valor de la centralidad de intermediación de cada Node. Lo anterior es una extensión de mi serie de artículos sobre las medidas de centralidad. Sigan haciendo networking!!! 

Este artículo es una contribución de Jayant Bisht . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *