Centralidade
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.
Imagem: EAJ-PNV · BY-ND · Openverse
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 v {\displaystyle v} , para um dado grafo G := ( V , E ) {\displaystyle G:=(V,E)} com | V | {\displaystyle |V|} vértices e | E | {\displaystyle |E|} arestas, é definido como: Calculando a centralidade de grau para todos os nós num grafo Θ ( V 2 ) {\displaystyle \Theta (V^{2})} em representação da densa matriz de adjacência do grafo, e para as arestas tem Θ ( E ) {\displaystyle \Theta (E)} numa representação de uma matriz dispersa.
Imagem: EAJ-PNV · BY-ND · Openverse
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.
Imagem: EAJ-PNV · BY-ND · Openverse
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 v {\displaystyle v} num grafo G := ( V , E ) {\displaystyle G:=(V,E)} com V {\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: Onde, σ s t {\displaystyle \sigma _{st}} é o número total de caminhos curtos desde o nó s {\displaystyle s} ao nó t {\displaystyle t} e σ s t ( v ) {\displaystyle \sigma _{st}(v)} é o número desses caminhos que passam por v {\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 é ( n − 1 ) ( n − 2 ) {\displaystyle (n-1)(n-2)} e para grafos indiretos é ( n − 1 ) ( n − 2 ) / 2 {\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 ( n − 1 ) ( n − 2 ) / 2 {\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.
Imagem: deusto · BY-NC-SA · Openverse
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. 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 G := ( V , E ) {\displaystyle G:=(V,E)} com | V | {\displaystyle |V|} o número de vértices e A = ( a v , t ) {\displaystyle A=(a_{v,t})} a matriz de adjacência, ou seja a v , t = 1 {\displaystyle a_{v,t}=1} se o vértice v {\displaystyle v} está ligado ao vértice t {\displaystyle t} , e a v , t = 0 {\displaystyle a_{v,t}=0} de outra forma. A pontuação da centralidade do vértice v {\displaystyle v} pode ser definida como: Onde M ( v ) {\displaystyle M(v)} é um conjunto de vizinhos de v {\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.
Imagem: EAJ-PNV · BY-ND · Openverse
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 W i j = A i j D i j {\displaystyle W_{ij}=A_{ij}D_{ij}} (e produto coordenada-coordenada) e D i j {\displaystyle D_{ij}} é uma matriz de dissimilaridade arbitrárias definidas pela uma medida de dissimilaridade, por exemplo, dissimilaridade Jaccard: onde V + ( i ) {\displaystyle V^{+}(i)} é a vizinhança do vértice i {\displaystyle i} , incluindo i {\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.
Imagem: EAJ-PNV · BY-ND · Openverse
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 α ∈ ( 0 , 1 ) {\displaystyle \alpha \in (0,1)} . Matematicamente, é definido como x i = ∑ k = 1 ∞ ∑ j = 1 N α k ( A k ) i j {\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 é: x i = α ∑ j = 1 N a i j ( x j + 1 ) . {\displaystyle 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 {\displaystyle x_{j}} é substituída por x j + 1 {\displaystyle x_{j}+1} . Nesta demonstração em que o principal vetor próprio (associado com o maior valor do vetor próprio de A {\displaystyle A} , a matriz adjacente) é o limite da centralidade de Katz como α {\displaystyle \alpha } aborda 1 / λ {\displaystyle 1/\lambda } por baixo.
Imagem: EAJ-PNV · BY-ND · Openverse
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 {\displaystyle G} and H {\displaystyle H} são 2 grafos isomorfos e Φ {\displaystyle \Phi } é o mapeamento a partir do conjunto de vértices V ( G ) {\displaystyle V(G)} de G {\displaystyle G} para V(H), então a centralidade do vértice v {\displaystyle v} de G {\displaystyle G} deverá ser a mesma que a centralidade de Φ ( v ) {\displaystyle \Phi (v)} em H {\displaystyle 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.
Imagem: deusto · BY-NC-SA · Openverse
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 ) {\displaystyle C_{x}(p_{i})} é uma medida de ponto central qualquer i {\displaystyle i} , se C x ( p ∗ ) {\displaystyle C_{x}(p_{*})} é a maior medida na rede, e se m a x ∑ j = 1 N C x ( p ∗ ) − C x ( p i ) {\displaystyle max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})} é a maior soma das diferenças do ponto central C x {\displaystyle C_{x}} para qualquer grafo com o mesmo número de nós, em seguida, a centralização da rede é :
