Usuário(a):Ruimgnicolau/Testes

Exemplos do mesmo grafo: A) Centralidade de Grau, B) Centralidade de Proximidade, C) Centralidade de Intermediação, D) Centralidade de vetor próprio, E) Centralidade de Katz, F) Centralidade Alpha

Centralidade

No âmbito da teoria dos grafos e da análise de redes, existem diferentes tipos de medidas de centralidade de um vértice num grafo que determinam a importância relativa de um vértice no grafo (isto é, o quanto uma pessoa é influente dentro de uma rede social, ou, na teoria da sintaxe espacial, o quanto é importante uma sala dentro de um edifício ou como é bem utilizada uma estrada dentro de uma rede urbana). Muitos dos conceitos de centralidade foram primeiramente desenvolvidos na análise de redes sociais, e muitos dos termos usados para medir a centralidade refletem a sua origem sociológica.

Existem quatro medidas de centralidade que são amplamente utilizados na análise de rede: centralidade de grau, centralidade de intermediação, centralidade de proximidade e centralidade de vetor próprio. Para uma revisão, bem como generalizações para redes ponderadas, consulte Opsahl et al.(2010).

Centralidade de Grau

Historicamente primeira, a centralidade de grau é conceptualmente a mais simples, a qual é definida como o número de ligações incidentes sobre um nó (por exemplo, o número de ligações que um nó possuí). O grau pode ser interpretado em termos de risco imediato de um nó para capturar tudo o que circula através da rede (por exemplo, um vírus, ou alguma informação) No caso de uma rede orientada (onde os laços tem direção), costumamos definir duas medidas distintas de centralidade de grau, isto é, indegree e outdegree. Consequentemente, indegree é uma contagem do número de ligações direcionadas para o nó e outdegree é o número de ligações que o nó encaminha para outros. Quando os laços estão associados a alguns aspetos positivos, como a amizade ou colaboração, indegree é muitas vezes interpretada como uma forma de popularidade, e outdegree como sociável.

A centralidade de grau de um vértice $v$, para um dado grafo $G:=(V,E)$ com $|V|$ vértices e $|E|$ arestas, é definido como

$C_{D}(v)={\text{deg}}(v)$

Calculando a centralidade de grau para todos os nós num grafo $\Theta (V^{2})$ em representação da densa matriz de adjacência do grafo, e para as arestas tem $\Theta (E)$ numa representação de uma matriz dispersa.

Por vezes, o interesse está em descobrir a centralidade de um grafo dentro de um grafo. A definição da centralidade no nível do nó pode ser estendida para o grafo inteiro. Deixemos $v*$ ser o nó com maior centralidade de grau em $G$. Deixemos $X:=(Y,Z)$ seja o $Y$ nó conectado ao grafo que maximiza a seguinte quantidade (Com $y*$ sendo o nó com maior grau de centralidade $X$):

$H=\displaystyle {\sum _{j=1}^{|Y|}{C_{D}(y*)-C_{D}(y_{j})}}$

De um modo correspondente, o grau de centralidade do grafo $G$ é o seguinte:

$C_{D}(G)={\frac {\displaystyle {\sum _{i=1}^{|V|}{[C_{D}(v*)-C_{D}(v_{i})]}}}{H}}$

O valor de $H$ é maximizado quando o grafo $X$ contem um nó central ao qual todos os outros nós são ligados (um grafo em estrela), e neste caso $H=(n-1)(n-2)$.

Centralidade de Proximidade

Em grafos conectados existe uma distância natural métrica entre todos os pares de nós, definido pelo comprimento de seus caminhos mais curtos. O afastamento de um nó s é definido como a soma de suas distâncias para todos os outros nós, e sua proximidade é definida como o inverso do afastamento. Assim, quanto mais central é o nó, menor é a distância do seu total para todos os outros nós. Proximidade pode ser considerada como uma medida de rapidez, para determinar a velocidade que ela necessitará para difundir informações de s a todos os outros nós sequencialmente.

Na definição clássica de centralidade de proximidade, a disseminação de informações é modelada através da utilização dos caminhos mais curtos. Este modelo pode não ser o mais realista de todos os tipos de cenários de comunicação. Assim, as definições relacionadas foram discutidas para medir proximidade, como a centralidade de proximidade de caminhos aleatórios introduzida por Noh e Rieger (2004). Mede a velocidade com que as mensagens aleatórias chegam a um vértice de fora da rede, digamos que é uma espécie de versão aleatória das mensagens da centralidade de proximidade.

A centralidade da informação de Stephenson e Zelen (1989) é outra medida de proximidade, que tem alguma semelhança com a de Noh e Rieger. Na sua essência, as medidas da duração média harmônica de caminhos que termina num vértice i, que é menor se i tiver muitos caminhos curtos ligando-o a outros vértices.

Note-se que, por definição de distâncias teóricas do grafo, a centralidade de proximidade clássica de todos os nós de um grafo seria 0. Numa obra de Dangalchev (2006) relacionando a vulnerabilidade da rede, a definição de proximidade é modificada de tal modo, que pode ser calculada mais facilidade e podem ser aplicados também aos grafos que falta conectividade:

$C_{C}(v)=\sum _{t\in V\setminus v}2^{-d_{G}(v,t)}.$

Outra extensão de redes com elementos desconectados foi proposta por Opsahl (2010).

Centralidade de Intermediação

Hue (de vermelho para azul = 0 = max) mostra a intermediação nó.

É uma medida de centralidade de um vértice dentro de um grafo (existe também a intermediação das arestas, que não é discutido aqui). Centralidade de intermediação quantifica o número de vezes que um nó age como ponte ao longo do caminho mais curto entre dois outros nós. Foi introduzido por Linton Freeman. como uma medida para quantificar o controlo de um ser humano sobre a comunicação entre outros seres humanos numa rede social. Na sua conceção, vértices que possuem uma alta probabilidade de ocorrer num caminho mais curto escolhido aleatoriamente entre dois vértices também escolhidos aleatoriamente que possuam uma elevada intermediação.

A intermediação de um vértice $v$ num grafo $G:=(V,E)$ com $V$ vértices é calculado como se segue:

1. Para cada par de vértices (s,t), calcular os caminhos mais curtos entre eles.

2. Para cada par de vértices (s,t), determinar a fração de caminhos mais curtos que passam através do vértice em questão (neste caso, vértice v ).

3. Somar esta fração de todos os pares de vértices (s,t).

De forma mais compacta a intermediação pode ser representada como:

$C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}$

Onde, $\sigma _{st}$ é o número total de caminhos curtos desde o nó $s$ ao nó $t$ e $\sigma _{st}(v)$ é o número desses caminhos que passam por $v$. A intermediação pode ser normalizada ao ser dividida pelo número de pares de vértices não incluindo v, que para grafos diretos é $(n-1)(n-2)$ e para grafos indiretos é $(n-1)(n-2)/2$. or exemplo, um grafo indireto em estrela, o vértice central (que está contido em cada caminho mais curto possível) teria uma intermediação de $(n-1)(n-2)/2$ (1, se normalizado) enquanto as folhas (as quais não estão presentes em nenhum caminhos mais curtos) teria uma intermediação de 0.

Do ponto de vista de cálculo, tanto a centralidade de intermediação como a de proximidade de todos os vértices de um grafo envolvem o cálculo dos caminhos mais curtos entre todos os pares de vértices de um grafo, que requer um tempo $\Theta (V^{3})$ com o algoritmo de Floyd-Warshall.No entanto, em grafos dispersos, o algoritmo de Johnson pode ser mais eficiente, tendo tempo $O(V^{2}\log V+VE)$. No caso dos grafos não ponderados os cálculos pode ser feitos com o algoritmo de Brandes o que leva o tempo $O(VE)$. Normalmente, estes algoritmos assumem que os grafos estão sem direção e conectados com a garantia de ciclos e arestas múltiplas. Quando se lidar especificamente com grafos de rede, os grafos estão sem ciclos ou múltiplas arestas para manter relacionamentos simples (onde as arestas representam as ligações entre duas pessoas ou vértices). Neste caso, utilizando o algoritmo de Brandes vai dividir as pontuações finais da centralidade por 2 por 2 e contabilizar cada caminho mais curto duas vezes.

Centralidade de Vetor Próprio

Centralidade de vetor próprio é uma medida da influência de um nó numa rede. Ele atribui pontuações relativas a todos os nós da rede, baseada no conceito de que as ligações para os nós de alta pontuação contribuem mais para a pontuação do nó em questão do que ligações iguais a nós baixa pontuação. O sistema de PageRank do Google é uma variante da medida de centralidade de vetor próprio. Outra medida de centralidade relacionada é a centralidade de Katz.

Utilizando a matriz de adjacência para encontrar a centralidade de vetor próprio

Para um dado grafo $G:=(V,E)$ com $|V|$ o número de vértices e $A=(a_{v,t})$ a matriz de adjacência, ou seja $a_{v,t}=1$ se o vértice $v$ está ligado ao vértice $t$, e $a_{v,t}=0$ de outra forma. A pontuação da centralidade do vértice $v$ pode ser definida como:

$x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}$

Onde $M(v)$ é um conjunto de vizinhos de $v$ e $\lambda$ é uma constante. Com um pequeno rearranjo, esta equação pode ser reescrita em notação vetorial como a equação de vetor próprio.

$\mathbf {Ax} ={\lambda }\mathbf {x}$

De um modo geral, haverá diversos vetores próprios $\lambda$ para o qual uma solução de vetor próprio existe. No entanto, o requerimento adicional para todas as entradas do vetor próprio sejam positivas, implica (pelo teorema de Perron-Frobenius) que somente os maiores resultados do vetor próprio sejam considerados na medida de centralidade desejada. O componente $v^{th}$ do vetor próprio relacionado dá-nos então a pontuação da centralidade do vértice $v$ na rede. O método das potências é um dos muitos algoritmos do vetor próprio que pode ser usado para encontrar o vetor próprio dominante. Por outro lado, isto pode ser generalizado de modo a que as entradas de A possam ser números reais que representem as forças de ligação, tal como uma matriz de probabilidade.

Centralidade de Katz e sistema de PageRank

A centralidade de Katz é uma generalização da centralidade de grau. Como a centralidade de grau mede o número de vizinhos diretos, a centralidade Katz mede o número de todos os nós que podem ser conectados através de um caminho, enquanto a contribuição de um nó distante é penalizado por um fator de atenuação $\alpha \in (0,1)$. Matematicamente, é definido como $x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ij}$.

Centralidade de Katz pode ser vista como uma variante da centralidade do vetor próprio. Outra forma da centralidade Katz é: $x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).$ Comparada com a expressão de centralidade de vetor próprio, $x_{j}$ é substituída por $x_{j}+1$.

Nesta demonstração em que o principal vetor próprio (associado com o maior valor do vetor próprio de $A$, a matriz adjacente) é o limite da centralidade de Katz como $\alpha$ aborda $1/\lambda$ por baixo.

O sistema de PageRank satisfaz a seguinte equação: $x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},$ Onde $L(j)=\sum _{j}a_{ij}$ é o número de vizinhos de nó $j$ ou o número de ligações externas num grafo direcionado). Comparando a centralidade de vetor próprio e a centralidade de Katz, a grande diferença é o fator de escala $L(j)$. ). Outra diferença entre o sistema PageRank e centralidade de vetor próprio é de que o vetor PageRank tem os índices invertidos no fator $a_{ji}$.

Definição e caracterização dos índices de centralidade

Dos índices de centralidade clássicos já mencionados, existem dezenas de outros índices de centralidade mais especializados. Apesar da sua noção intuitiva ainda não há uma definição ou caracterização de índices de centralidade que que seja comum para todos eles. Uma definição um pouco fraca de índice de centralidade é a seguinte:

Um índice de centralidade é uma função real sobre os nós de um grafo. É um índice estrutural, ou seja, se $G$ and $H$ são 2 grafos isomorfos e $\Phi$ é o mapeamento a partir do conjunto de vértices $V(G)$ de $G$ para V(H), então a centralidade do vértice $v$ de $G$ deverá ser a mesmo que a centralidade de $\Phi (v)$ em $H$. Convencionalmente, quanto maior for o índice da centralidade de um nó, maior será a sua centralidade percebida no grafo. Esta definição inclui todas as medidas de centralidade clássica, mas nem todas as medidas que atendam a esta definição podem ser aceites como índices de centralidade.

Segundo Borgatti e Everett os índices de centralidade medem a posição de um nó ao longo de um conjunto de caminhos predefinido. Eles caracterizam os índices de centralidade ao longo de quatro dimensões: o conjunto de caminhos, se o comprimento ou o número destes caminhos é considerado, a posição do nó nos caminhos (no início = radial; no meio = medial), e como os números atribuídos aos caminhos estão resumidos nas medidas (média, mediana, soma ponderada...). Isto leva a uma caracterização da forma como um índice centralidade é calculado. Numa outra diferente caracterização, Borgatti diferencia os índices de centralidade pelo tipo de caminhos que são considerados e que tipo de fluxo de rede que estes implicam. Este último caracteriza os índices de centralidade pela qualidade com que eles preveem qual o nó mais central para um determinado processo de fluxo de rede. Esta caracterização, portanto, fornece orientação sobre quando usar cada índice de centralidade.

Centralização

A centralização de qualquer rede é uma medida de quão central é o nó mais central, em relação à forma de quão central serão todos os outros nós. A definição geral de centralização para redes não ponderadas foi proposta por Linton Freeman (1979). Centralização mede então: (a) Calcular a soma de diferenças na centralidade entre o nó mais central de uma rede, e todos os outros nós; (b) Dividir esta quantidade pela teoricamente maior soma das diferenças em toda a rede do mesmo grau Assim, a cada medida de centralidade pode ter a sua própria medida de centralização. Definidos formalmente, se $C_{x}(p_{i})$ é uma medida de ponto central qualquer $i$, se $C_{x}(p_{*})$ é a maior medida na rede, e se $max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})$ é a maior soma das diferenças do ponto central $C_{x}$ para qualquer grafo com o mesmo número de nós, em seguida, a centralização da rede é :

$C_{x}={\frac {\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}$

Leitura adicional

• Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.
• Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31 (4), 581-603.
• Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry 40, 35-41.
• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16–61, LNCS 3418, Springer-Verlag.
• Bonacich, P. (1987). Power and Centrality: A Family of Measures, The American Journal of Sociology, 92 (5), pp 1170–1182.

Ligações externas

• https://networkx.lanl.gov/trac/attachment/ticket/119/page_rank.py
• http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html