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.Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.
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.
thumb|right|300px|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 , para um dado grafo com vértices e arestas, é definido como:
Calculando a centralidade de grau para todos os nós num grafo em representação da densa matriz de adjacência do grafo, e para as arestas tem 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 ser o nó com maior centralidade de grau em . Deixemos seja o nó conectado ao grafo que maximiza a seguinte quantidade (Com sendo o nó com maior grau de centralidade ):
Analogamente, o grau de centralidade do grafo é:
O valor de é maximizado quando o grafo contém um nó central ao qual todos os outros nós são ligados (um grafo em estrela), e neste caso .
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.Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581--603. 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.Papercore summary http://papercore.org/Newman2005.
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.J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
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.Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.
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:Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).
Outra extensão de redes com elementos desconectados foi proposta por Opsahl (2010).
Centralidade de Intermediação
240px|right|thumb|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 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 num grafo com 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: Paperore summary http://papercore.org/Brandes2001
Onde, é o número total de caminhos curtos desde o nó ao nó e é o número desses caminhos que passam por . 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 é e para grafos indiretos é . 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 (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 com o algoritmo de Floyd-Warshall.No entanto, em grafos dispersos, o algoritmo de Johnson pode ser mais eficiente, tendo tempo . No caso dos grafos não ponderados os cálculos pode ser feitos com o algoritmo de Brandes o que leva o tempo . 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.
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.http://www.ams.org/samplings/feature-column/fcarc-pagerank 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 com o número de vértices e a matriz de adjacência, ou seja se o vértice está ligado ao vértice , e de outra forma. A pontuação da centralidade do vértice pode ser definida como:
Onde é um conjunto de vizinhos de e é uma constante. Com um pequeno rearranjo, esta equação pode ser reescrita em notação vetorial como a equação de autovetor.
De um modo geral, haverá diversos autovetores 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. O componente do autovetor relacionado dá-nos então a pontuação da centralidade do vértice na rede. O método das potências é um dos muitos algoritmos do autovetor que pode ser usado para encontrar o autovetor 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.
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. Isto é ilustrado com autocentralidad (ou eigenvector centralidade), calculando a centralidade de cada nó, resolvendo o problema de autovetores:
onde (e produto coordenada-coordenada) e é uma matriz de dissimilaridade arbitrárias definidas pela uma medida de dissimilaridade, por exemplo, dissimilaridade Jaccard:
onde é a vizinhança do vértice , incluindo . 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 é não negativo sendo que e 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 , o que nos permite inferir a centralidade de cada vértice na rede. Portanto, a centralidade do i-ésimo vértice é dada por:
onde é o número de vértices na rede. Várias redes e medidas de dissimilaridade foram testados, em todos os casos, a obtenção de excelentes resultados.
Centralidade de Katz e sistema de PageRank A centralidade de KatzKatz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39-43. é 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 . Matematicamente, é definido como .
Centralidade de Katz pode ser vista como uma variante da centralidade do vetor próprio. Outra forma da centralidade Katz é: Comparada com a expressão de centralidade de vetor próprio, é substituída por .
Nesta demonstração Bonacich, P., 1991. Simultaneous group and individual centralities. Social Networks 13, 155–168. em que o principal vetor próprio (associado com o maior valor do vetor próprio de , a matriz adjacente) é o limite da centralidade de Katz como aborda por baixo.
O sistema de PageRank satisfaz a seguinte equação: Onde é o número de vizinhos de nó 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 . ). Outra diferença entre o sistema PageRank e centralidade de vetor próprio é de que o vetor PageRank tem os índices invertidos no fator . 20Q: About Networked Life
Definição e caracterização dos índices de centralidade