Grado de Centralidad (Medida de Centralidad)

Grado
En teoría de grafos, el grado (o valencia) de un vértice de un gráfico es el número de aristas incidentes en el vértice, con bucles contados dos veces.[1] El grado de un vértice $v$ se denota $\deg(v)$ o $\deg v$ . El grado máximo de un grafo G, denotado por $\Delta$ (G), y el grado mínimo de un grafo, denotado por $\delta$ (G), son el grado máximo y mínimo de sus vértices. En el gráfico de la derecha, el grado máximo es 5 y el grado mínimo es 0. En un gráfico regular, todos los grados son iguales, por lo que podemos hablar del grado del gráfico.

Grado de centralidad
Históricamente, el primero y conceptualmente más simple es el grado de centralidad, que se define como el número de enlaces incidentes en un Node (es decir, el número de enlaces que tiene un Node). El grado se puede interpretar en términos del riesgo inmediato de un Node de atrapar cualquier cosa que fluya a través de la red (como un virus o alguna información). En el caso de una red dirigida (donde los lazos tienen dirección), generalmente definimos dos medidas separadas de centralidad de grado, a saber, grado de entrada y grado de salida. En consecuencia, el grado de entrada es un recuento del número de vínculos dirigidos al Node y el grado de salida es el número de vínculos que el Node dirige a otros. Cuando los lazos se asocian a algunos aspectos positivos como la amistad o la colaboración, el grado interior suele interpretarse como una forma de popularidad y el grado superior como gregarismo.

El grado de centralidad de un vértice $v$ , para un grafo dado $G:=(V,E)$ con $|V|$ vértices y $|E|$ aristas, se define como

$C_{D}(v)=\deg(v)$
Calculating degree centrality for all the nodes in a graph takes $\Theta(V^2)$ in a dense adjacency matrix representation of the graph, and for edges takes $\Theta(E)$ in a sparse matrix representation.

La definición de centralidad a nivel de Node se puede extender a todo el grafo, en cuyo caso estamos hablando de centralización de grafo. Sea $v*$ el Node con mayor grado de centralidad en $G$ . Sea $X:=(Y,Z)$ el $|Y|$ grafo conexo de Nodes que maximiza la siguiente cantidad (siendo $y*$ el Node de mayor grado de centralidad en $X$ ):

$H=\sum _{{j=1}}^{{|Y|}}[C_{D}(y*)-C_{D}(y_{j})]$
Correspondingly, the degree centralization of the graph $G$ is as follows:

$C_D(G)= \frac{\displaystyle{\sum^{|V|}_{i=1}{[C_D(v*)-C_D(v_i)]}}}{H}$
The value of $H$ is maximized when the graph $X$ contains one central node to which all other nodes are connected (a star graph), and in this case

${H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2}$ .

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

import networkx as nx
  
def degree_centrality(G, nodes):
    r"""Compute the degree centrality for nodes in a bipartite network.
  
    The degree centrality for a node `v` is the fraction of nodes 
    connected to it.
  
    Parameters
    ----------
    G : graph
       A bipartite network
  
    nodes : list or container
      Container with all nodes in one bipartite node set.
  
    Returns
    -------
    centrality : dictionary
       Dictionary keyed by node with bipartite degree centrality as the value.
  
    Notes
    -----
    The nodes input parameter must contain all nodes in one bipartite node set,
    but the dictionary returned contains all nodes from both bipartite node
    sets.
  
    For unipartite networks, the degree centrality values are 
    normalized by dividing by the maximum possible degree (which is 
    `n-1` where `n` is the number of nodes in G). 
  
    In the bipartite case, the maximum possible degree of a node in a
    bipartite node set is the number of nodes in the opposite node set
    [1]_.  The degree centrality for a node `v` in the bipartite
    sets `U` with `n` nodes and `V` with `m` nodes is
  
    .. math::
  
        d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
  
        d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
  
  
    where `deg(v)` is the degree of node `v`.        
  
      
    """
    top = set(nodes)
    bottom = set(G) - top
    s = 1.0/len(bottom)
    centrality = dict((n,d*s) for n,d in G.degree_iter(top))
    s = 1.0/len(top)
    centrality.update(dict((n,d*s) for n,d in G.degree_iter(bottom)))
    return centrality

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 grado de un Node.

import networkx as nx
G=nx.erdos_renyi_graph(100,0.5)
d=nx.degree_centrality(G)
print(d)

El resultado es el siguiente:

{0: 0.5252525252525253, 1: 0.4444444444444445, 2: 0.5454545454545455, 3: 0.36363636363636365,
4: 0.42424242424242425, 5: 0.494949494949495, 6: 0.5454545454545455, 7: 0.494949494949495,
8: 0.5555555555555556, 9: 0.5151515151515152, 10: 0.5454545454545455, 11: 0.5151515151515152,
12 : 0.494949494949495, 13: 0.4444444444444445, 14: 0.494949494949495, 15: 0.4141414141414142,
16: 0.43434343434343436, 17: 0.5555555555555556, 18: 0.494949494949495, 19: 0.5151515151515152,
20: 0.42424242424242425, 21: 0.494949494949495, 22: 0.5555555555555556, 23: 0.5151515151515152,
24: 0.4646464646464647 , 25: 0.4747474747474748, 26: 0.4747474747474748, 27: 0.494949494949495, 28: 0.5656565656565657, 29
: 0.5353535353535354, 30: 0.4747474747474748, 31: 0.494949494949495,
32: 0.43434343434343436, 33: 0.4444444444444445, 34: 0.5151515151515152, 35: 0.48484848484848486,
36: 0.43434343434343436, 37: 0.4040404040404041, 38: 0.5656565656565657, 39: 0.5656565656565657,
40: 0.494949494949495, 41: 0.5252525252525253, 42: 0.4545454545454546, 43: 0.42424242424242425,
44: 0.494949494949495, 45: 0.595959595959596, 46: 0.5454545454545455, 47: 0.5050505050505051,
48: 0.4646464646464647, 49: 0.48484848484848486, 50: 0.5353535353535354, 51: 0.5454545454545455,
52: 0.5252525252525253, 53: 0.5252525252525253, 54: 0.5353535353535354, 55: 0.6464646464646465,
56: 0.4444444444444445, 57: 0,48484848484848486, 58: 0,5353535353535354, 59: 0,494949494949495,
60: 0.4646464646464647, 61: 0.5858585858585859, 62: 0.494949494949495, 63: 0.48484848484848486,
64: 0.4444444444444445, 65: 0.6262626262626263, 66: 0.5151515151515152, 67: 0.4444444444444445,
68: 0.4747474747474748, 69: 0.5454545454545455, 70: 0.48484848484848486, 71: 0.5050505050505051,
72: 0.4646464646464647, 73: 0.4646464646464647, 74: 0.5454545454545455, 75: 0.4444444444444445,
76: 0.42424242424242425, 77: 0.4545454545454546, 78: 0.494949494949495, 79: 0.494949494949495,
80: 0.4444444444444445, 81: 0.48484848484848486, 82: 0.48484848484848486, 83: 0.5151515151515152,
84: 0.494949494949495, 85: 0,5151515151515152, 86: 0,5252525252525253, 87: 0,4545454545454546,
88: 0.5252525252525253, 89: 0.5353535353535354, 90: 0.5252525252525253, 91: 0.4646464646464647,
92: 0.4646464646464647, 93: 0.5555555555555556, 94: 0.5656565656565657, 95: 0.4646464646464647,
96: 0.494949494949495, 97: 0.494949494949495, 98: 0.5050505050505051, 99: 0.5050505050505051}

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

Referencias
Puede leer más sobre el mismo en

https://en.wikipedia.org/wiki/Centrality#Degree_centrality
http://networkx.readthedocs.io/en/networkx-1.10/index.html

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.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

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

Deja una respuesta Cancelar la respuesta