Centralidade - PesquisaProic/sna GitHub Wiki

Medidas de centralidade

A centralidade de um determinado ator ou vértice em uma rede está relacionada com sua influência na rede. Suas formas de mensuração mais usuais são as medidas de centralidades de:

Grau (degree); intermediação (betweenness); proximidade (closeness) e autovetor (eigenvector).

Centralidade de grau¹

O grau é o número de ligações que cada nó (vértice) estabelece na rede. Essa medida se desdobra em duas no caso de redes com arestas direcionadas: o grau de entrada e o de saída*. As duas podem ser obtidas somando, respectivamente, o número de "conexões" chegando e saindo do vértice em questão. No caso de redes com matrizes valoradas, essa medida equivale à soma dos valores das relações com o vértice considerado.

Por usar somente informações sobre os vértices adjacentes, a centralidade de grau é considerada uma medida de influência local na rede.

Centralidade de intermediação¹

Centralidade de intermediação de um dado vértice está relacionada com a probabilidade de que esse vértice esteja no menor caminho entre dois vértices aleatoriamente escolhidos. Ela representa a centralidade do vértice na rede como um todo, já que considera toda a rede e não somente os vértices próximos.

Para a obter essa medida, é necessário construir uma tabela com os caminhos mais curtos entre todas os pares possíveis de vértices (com o algoritmo de Floyd-Warshall). Então a centralidade de intermediação de um dado vértice será o número de caminhos que ele aparece, i.e., o número de ocorrências desse vértice na tabela.

Centralidade de proximidade¹

A proximidade de um vértice é o inverso da soma das distâncias deste vértice até todos os outros da rede. Essa medida está relacionada, por exemplo, com o tempo que uma informação levaria para passar desse vértice para o resto da rede.

Centralidade de autovetor²

[AQUI A EXPLICAÇÃO FICOU COMPLEXA - TENTE SIMPLIFICAR DE FORMA TEXTUAL OU COM EXEMPLOS]

É uma medida relativa da influência dos vértices na rede. Para obtê-la, é preciso encontrar o autovetor referente ao autovalor de maior magnitude da matriz de adjacência da rede. As componentes desse autovetor são as medidas de influência de cada vértice, respectivamente segundo a matriz de adjacência.

Devido ao alto custo computacional de se calcular autovetores de matrizes gigantes e esparsas por meio de métodos tradicionais em álgebra linear computacional, esse autovetor é obtido por meio de um algoritmo chamado "Power iteration".

Extensões da Centralidade

Extensões do conceito de centralidade são apresentadas nessa página como nos artigos de Borgatti e Everett6,7,8. A primeira estende as três medidas de centralidade de Freeman para agrupamentos de vértices. Já a segunda foi definida para permitir o cálculo dessas medidas em redes bipartidas (two-mode networks), sem precisar reduzi-la a redes mais simples9,10. A terceira usa o conceito de centralidade para caracterizar a estrutura de núcleo e periferia de uma rede.

Centralidade de grupos

Tradicionalmente a centralidade é um conceito aplicado a indivíduos, mas há muitas situações em que é vantajoso conhecer a influência de grupos de atores, sejam estes definidos por idade, filiação partidária, ocupação ou qualquer outra característica de interesse. Veremos abaixo três formas mais coerentes de se calcular uma medida de centralidade desses grupos do que simplesmente tomar uma função (média, mediana, máximo...) das centralidades de cada elemento.

Outra possibilidade de aplicar esse conceito é na resolução do problema inverso: Criar agrupamentos de vértices de modo que maximize suas centralidades na rede.

Uma propriedade interessante dessas medidas é a de que elas se reduzem às centralidades tradicionais (de Freeman) ao serem calculadas sobre conjuntos unitários de vértices.

Centralidade de grau

Defini-se a centralidade de grau de um certo grupo como o número de atores que possuem ligação com ao menos um elemento do grupo. É necessário normalizar essa medida para comparar atores em diferentes grupos, já que ela pode variar muito de acordo com o tamanho de cada grupo. A normalização é feita dividindo cada medida pelo grau máximo de centralidade, que seria o número de elementos do grafo não pertencentes ao grupo.

Centralidade de intermediação

A extensão de centralidade de intermediação para um grupo mede a proporção de caminhos mínimos conectando pares de vértices não pertencentes ao grupo.

Assim como na medida anterior, devemos construir uma tabela com os caminhos mais curtos entre todas os possíveis pares de vértices não pertencentes ao grupo (algoritmo de Floyd-Warshall). A centralidade de intermediação de um dado grupo será o número de caminhos em que ao menos um de seus elementos aparece, i.e., o número de ocorrências desse grupo na tabela.

Centralidade de proximidade

Seja D o conjunto de todas as distâncias (tamanho do caminho mais curto) de um vértice x até o conjunto de vértices C. Então podemos definir a distância de x até o conjunto C como uma função de D (como máximo, mínimo, média, mediana, etc.). Assim, a centralidade de proximidade do grupo C será o número de vértices fora deste grupo dividido pela soma das distâncias de C até todos os vértices não pertencentes a C.

A escolha de qual função deverá ser aplicada ao conjunto de distâncias D depende e suas propriedades matemáticas e da natureza da rede social em estudo. Se o grupo for concebido como uma unidade individual, então o mínimo deve ser uma função apropriada. Nesse caso, a centralidade de proximidade novamente está relacionada ao tempo que informações da rede levam para chegar ao grupo em questão. Já o máximo deve ser uma boa escolha caso haja interesse no tempo em que todos os atores do grupo levam para tomar conhecimento de alguma informação da rede social.

Centralidade em redes de duas modalidades

Redes de bipartidas (de duas modalidades) são formadas por duas classes de vértices: Indivíduos e eventos. As arestas nesse tipo de rede conectam somente elementos de diferentes classes (indivíduos a eventos ou eventos a indivíduos).

Uma forma de calcular as centralidades é reduzindo a rede bipartida a sua projeção em uma modalidade para aplicar as medidas tradicionais, assumindo que dois indivíduos estão conectados somente se ambos estão ligados a ao menos um evento em comum. Essa redução será boa quando for razoável supor que existe mesmo a conexão entre indivíduos que frequentaram o mesmo evento, caso contrário as conexões criadas podem ser incoerentes com a realidade. Outra possibilidade seria reduzir a uma modalidade atribuindo conexões com pesos que dependem da quantidade ou do tipo de eventos em comum entre pares de indivíduos (pesos por quantidade: nova matriz de adjacência é a antiga multiplicada por sua transposta se os individuos estiverem nas linhas).

Nos casos em que essa redução a uma modalidade não se aplica, podemos novamente estender as medidas de Freeman.

Assim como a medida original de Freeman, a centralidade de grau será o número de conexões que um vértice possui. Para eventos, isso representa o número de indivíduos presentes. Já para um dado indivíduo, essa medida é o número de eventos em que ele estava presente. A normalização dessa medida é feita dividindo as centralidades dos indivíduos pelo total de eventos no grafo e de modo análogo para eventos.

As centralidade de intermediação e de proximidade [como calcular-se?]

Núcleo e periferia

Referências

1. Freeman, L. C. (1979). Centrality in networks: I. Conceptual clarification. Social Networks, 1:215-39.
2. Bonacich P. (1972). Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2:113-120.
3. Floyd, R. W. (1962). "Algorithm 97." Comm. ACM 5-6, 345.
4. Roy, B. (1959). "Transitivité et connexité." C. R. Acad. Sci. Paris 249, 216-218.

5. Warshall, S. (1962). "A Theorem on Boolean Matrices." J. ACM 9, 11-12.

   6. Borgatti S. P. e Everett M. G. (1997). Network analysis of 2-mode data. Social Networks, 19(3):243-269.

7. Borgatti S. P. e Everett M. G. (1999). Models of core/periphery structure. Social Networks, 21:375-395.
8. Everett M. G. e Borgatti S. P. (1999). The centrality of groups and classes. Journal of Mathematical Sociology, 23(3):181-201.
9. Bonacich P. (1991). Simultaneous group and individual centralities. Social Networks, 13(2):155-168.
10. Faust K. (1997). Centrality in affiliation networks. Social networks, 19(2):157-191.