Centralidade

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas
v d e

No âmbito da teoria dos grafos e da análise de redes, centralidade é uma medida de importância de um vértice em um grafo. Existem diferentes tipos de medidas de centralidade de um vértice num grafo que determinam a importância relativa, que permitem, por exemplo, estimar o quanto uma pessoa é influente dentro de uma rede social, o quão é importante uma sala dentro de um edifício e como é bem utilizada uma estrada dentro de uma rede urbana. Vários 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.^[1]

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.^[2]

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 de Grau

Centralidade de grau é definida como o número de ligações incidentes de um vértice. O grau pode ser interpretado como a probabilidade que o vértice tem de receber alguma informação da rede. No caso de uma rede orientada (onde os laços tem direção), define-se duas medidas distintas de centralidade de grau: indegree e outdegree. 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.

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

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

Calculando a centralidade de grau para todos os nós num grafo ${\displaystyle \Theta (V^{2})}$ em representação da densa matriz de adjacência do grafo, e para as arestas tem ${\displaystyle \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 ${\displaystyle v*}$ ser o nó com maior centralidade de grau em ${\displaystyle G}$. Deixemos ${\displaystyle X:=(Y,Z)}$ seja o ${\displaystyle Y}$ nó conectado ao grafo que maximiza a seguinte quantidade (Com ${\displaystyle y*}$ sendo o nó com maior grau de centralidade ${\displaystyle X}$):

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

Analogamente, o grau de centralidade do grafo ${\displaystyle G}$ é:

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

O valor de ${\displaystyle H}$ é maximizado quando o grafo ${\displaystyle X}$ contém um nó central ao qual todos os outros nós são ligados (um grafo em estrela), e neste caso ${\displaystyle 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.^[3] 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.^[4]

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.^[5]

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.^[6]

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:^[7]

${\displaystyle 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).^[8]

Centralidade de Intermediação

Ver artigo principal: Intermediação

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

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^[9] como uma medida para quantificar o controlo de um ser humano sobre a comunicação entre outros seres humanos numa rede social.

A intermediação de um vértice ${\displaystyle v}$ num grafo ${\displaystyle G:=(V,E)}$ com ${\displaystyle 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:^[10]

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

Onde, ${\displaystyle \sigma _{st}}$ é o número total de caminhos curtos desde o nó ${\displaystyle s}$ ao nó ${\displaystyle t}$ e ${\displaystyle \sigma _{st}(v)}$ é o número desses caminhos que passam por ${\displaystyle 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 é ${\displaystyle (n-1)(n-2)}$ e para grafos indiretos é ${\displaystyle (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 ${\displaystyle (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 ${\displaystyle \Theta (V^{3})}$ com o algoritmo de Floyd-Warshall.No entanto, em grafos dispersos, o algoritmo de Johnson pode ser mais eficiente, tendo tempo ${\displaystyle O(V^{2}\log V+VE)}$. No caso dos grafos não ponderados os cálculos pode ser feitos com o algoritmo de Brandes^[10] o que leva o tempo ${\displaystyle 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 e contabilizar cada caminho mais curto duas vezes.^[10]

Centralidade de Autovetor

Centralidade de autovetor é 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 autovetor.^[11] Outra medida de centralidade relacionada é a centralidade de Katz.

Utilizando a matriz de adjacência para encontrar a centralidade de autovetor

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

${\displaystyle 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 ${\displaystyle M(v)}$ é um conjunto de vizinhos de ${\displaystyle v}$ e ${\displaystyle \lambda }$ é uma constante. Com um pequeno rearranjo, esta equação pode ser reescrita em notação vetorial como a equação de autovetor.

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

De um modo geral, haverá diversos autovetores ${\displaystyle \lambda }$ para o qual uma solução de autovetor existe. No entanto, o requerimento adicional para todas as entradas do autovetor sejam positivas, implica (pelo teorema de Perron-Frobenius) que somente os maiores resultados do autovetor sejam considerados na medida de centralidade desejada.^[12] O componente ${\displaystyle v^{th}}$ do autovetor relacionado dá-nos então a pontuação da centralidade do vértice ${\displaystyle v}$ na rede. O método das potências é um dos muitos algoritmos do autovetor que pode ser usado para encontrar o autovetor dominante.^[11] 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.

Centralidades Baseadas na Dissimilaridades

Outra metodologia relacionada com a utilização de semelhança (própria da teoria da classificação e extracção de dados) para realimentar centralidade medidas existentes em redes complexas.^[13] Isto é ilustrado com autocentralidad (ou eigenvector centralidade), calculando a centralidade de cada nó, resolvendo o problema de autovetores:

${\displaystyle W\mathbf {c} =\lambda _{\text{máx}}\mathbf {c} }$

onde ${\displaystyle W_{ij}=A_{ij}D_{ij}}$ (e produto coordenada-coordenada) e ${\displaystyle D_{ij}}$ é uma matriz de dissimilaridade arbitrárias definidas pela uma medida de dissimilaridade, por exemplo, dissimilaridade Jaccard:

${\displaystyle D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}}}$

onde ${\displaystyle V^{+}(i)}$ é a vizinhança do vértice ${\displaystyle i}$, incluindo ${\displaystyle i}$. Esta medida nos permite quantificar a contribuição topológica de cada nós o vértice (que é por isso que essas medidas são chamados centralidade da contribuição) em uma determinada rede, tendo mais peso / importância desses vértices com maior dissimilaridade, uma vez que estes permitem uma Eu vértice dado acesso a esses vértices que não podem aceder directamente.

Note que ${\displaystyle W}$ é não negativo sendo que ${\displaystyle A}$ e ${\displaystyle D}$ são não-negativo, para que possamos aplicar o teorema de Perron Frobenius garantir que o problema anterior autovetores tem uma solução não-negativo para ${\displaystyle \lambda =\lambda _{\text{max}}}$, o que nos permite inferir a centralidade de cada vértice na rede. Portanto, a centralidade do i-ésimo vértice é dada por:

${\displaystyle c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\,j=1,\cdots ,n}$

onde ${\displaystyle n}$ é o número de vértices na rede. Várias redes e medidas de dissimilaridade foram testados,^[14] em todos os casos, a obtenção de excelentes resultados.

Centralidade de Katz e sistema de PageRank

A centralidade de Katz^[15] é 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 ${\displaystyle \alpha \in (0,1)}$. Matematicamente, é definido como ${\displaystyle 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 é: ${\displaystyle x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).}$ Comparada com a expressão de centralidade de vetor próprio, ${\displaystyle x_{j}}$ é substituída por ${\displaystyle x_{j}+1}$.

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

O sistema de PageRank satisfaz a seguinte equação: ${\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}$ Onde ${\displaystyle L(j)=\sum _{j}a_{ij}}$ é o número de vizinhos de nó ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{ji}}$.^[17]

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.^[18] 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 ${\displaystyle G}$ and ${\displaystyle H}$ são 2 grafos isomorfos e ${\displaystyle \Phi }$ é o mapeamento a partir do conjunto de vértices ${\displaystyle V(G)}$ de ${\displaystyle G}$ para V(H), então a centralidade do vértice ${\displaystyle v}$ de ${\displaystyle G}$ deverá ser a mesma que a centralidade de ${\displaystyle \Phi (v)}$ em ${\displaystyle H}$. Convencionalmente, quanto maior for o índice da centralidade de um nó, maior será a sua centralidade percebida no grafo.^[19] 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...).^[18] 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.^[20] 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.^[21] 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 ^[21] Assim, a cada medida de centralidade pode ter a sua própria medida de centralização. Definidos formalmente, se ${\displaystyle C_{x}(p_{i})}$ é uma medida de ponto central qualquer ${\displaystyle i}$, se ${\displaystyle C_{x}(p_{*})}$ é a maior medida na rede, e se ${\displaystyle max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}$ é a maior soma das diferenças do ponto central ${\displaystyle C_{x}}$ para qualquer grafo com o mesmo número de nós, em seguida, a centralização da rede é :^[21]

${\displaystyle 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})}}}$

Notas e referências

1. Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.
2. Opsahl, Tore; Agneessens, Filip; Skvoretz, John (2010). «Node centrality in weighted networks: Generalizing degree and shortest paths». Social Networks. 32 (3). 245 páginas. doi:10.1016/j.socnet.2010.03.006 
3. Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581--603.
4. M.E.J. Newman (2005). A measure of betweenness centrality based on random walks|Social Networks. 27. [S.l.: s.n.] pp. 39–54. arXiv:cond-mat/0309045. doi:10.1016/j.socnet.2004.11.009 Papercore summary http://papercore.org/Newman2005.
5. J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
6. Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.
7. Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).
8. Tore Opsahl. «Closeness centrality in networks with disconnected components» 
9. Freeman, Linton (1977). «A set of measures of centrality based upon betweenness». Sociometry. 40: 35–41 
10. Brandes, Ulrik (2001). «A faster algorithm for betweenness centrality». Journal of Mathematical Sociology. 25: 163–177. Consultado em 10 de novembro de 2011  Paperore summary http://papercore.org/Brandes2001
11. http://www.ams.org/samplings/feature-column/fcarc-pagerank
12. M. E. J. Newman. «The mathematics of networks» (PDF). Consultado em 9 de novembro de 2006 
13. Alvarez-Socorro, A. J.; et al. (25 de novembro de 2015). «Eigencentrality based on dissimilarity measures reveals central nodes in complex networks». Scientific Reports (em inglês). 5. PMID 26603652. doi:10.1038/srep17095 
14. «Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks» (Scientific Reports). Nature Publishing Group. Consultado em 29 de dezembro de 2015 
15. Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39-43.
16. Bonacich, P., 1991. Simultaneous group and individual centralities. Social Networks 13, 155–168.
17. «How does Google rank webpages?» (PDF)  20Q: About Networked Life
18. Borgatti, Stephen P.; Everett, Martin G. (2005). «A Graph-Theoretic Perspective on Centrality». Elsevier. Social Networks. 28: 466–484. doi:10.1016/j.socnet.2005.11.005 
19. Koschützki, Dirk; Katharina A. Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, Oliver Zlotowski (2005). «Centrality Indices». In: Ulrik Brandes, Thomas Erlebach. Network Analysis – Methodological Foundations. LNCS 3418. Springer Verlag, Heidelberg, Germany. pp. 16–60. ISBN 978-3-540-24979-5  A referência emprega parâmetros obsoletos |coautor= (ajuda)
20. Stephen P. Borgatti (2005). «Centrality and Network Flow». Elsevier. Social Networks. 27: 55–71 
21. Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.

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