Ricardo Prudncio Tpicos Avanados em Agentes Inteligentes
Slide 2
Roteiro Introduo Medidas de centralidade Medidas principais
Grau, intermediao e proximidade Medidas alternativas Centralizao
Concluses
Slide 3
Introduo Problema Que ns so importantes dentro de uma rede?
Quais ns so importantes estruturalmente e relevantes para o fluxo
de informao na rede Anlise de centralidade
Slide 4
Centralidade Considere a rede ao lado em formato de estrela
Intuitivamente, o n A o mais central de todos Posio estratgica
considerando a estrutura da rede O que A tem de diferente?! A C D B
G F E
Slide 5
Centralidade (1) N A tem maior nmero de conexes com outros ns
Grau (2) N A est sempre entre dois ns quaisquer Intermediao (3) N A
est mais prximo aos outros ns da rede Proximidade A C D B G F E Trs
propriedades que levam a trs diferentes conceitos de centralidade
Ver (Freeman 1978)
Slide 6
Grau Grau = No. de links adjacentes a um n Em um processo de
comunicao na rede, n de grau alto um canal direto de informao
Popularidade e influncia direta Ns com grande potencial de
atividade dentro de uma rede
Slide 7
Grau Fator de normalizao para comparao entre redes Obs.: n-1 o
grau mximo de uma rede em estrela Nmero de ns adjacentes Obs.:
Redes sem pesos: w kj = 1 se existe link entre ns v k e v j
Slide 8
Grau Em grafos direcionados importante diferenciar graus de
entrada e sada Grau de entrada (in-degree) = no. de links que
chegam a um n E.g., no. de seguidores no Twitter (in-degree) =
prestgio(?) Grau de sada (out-degree) = no. de links que saem de um
n E.g., na relao de manda em, out-degree = alta influncia
Slide 9
Grau - Limitaes Grau uma medida de centralidade local nodes may
be well connected to their immediate neighbors but be part of a
relatively isolated clique (Liu 2008) Dois ns com o mesmo grau
podem no ter a mesma capacidade de influenciar E.g., se grau usado
para medir influncia local, ento poder do n depende de quem so os
seus vizinhos e do tipo de interao E.g., nmero de seguidores no
Twitter no reflete diretamente a influncia dentro da rede (como
nmero de retwittes)
Slide 10
Intermediao Mede a frequncia com que o n aparece no menor
caminho entre dois ns quaisquer Ns com grande potencial de controle
do fluxo de informao na rede A C D B G F E Todas as mensagens na
rede passam por n A!
Slide 11
Intermediao Ns com alto controle: Podem ajudar na coordenao de
processos dentro de um grupo Podem influenciar na comunicao da
rede, atrasando ou perturbao o fluxo de informao The more people
depend on me to make connections with other people, the more power
I have (Hanneman 1998)
Slide 12
Intermediao Potencial para conectar comunidades diferentes
Eliminar ns de alta intermediao pode ter o efeito de desconectar a
rede Propriedade usada em algoritmos de deteco de comunidades
Slide 13
Intermediao : Nmero de caminhos geodsicos entre v i e v j que
passam por v k : Nmero total de caminhos geodsicos entre v i e v j
Soma para todos os pares diferentes de ns v i e v j
Slide 14
Intermediao Medida normalizada para comparao entre redes Grau
de intermediao do n mais central em uma rede em formato
estrela
Slide 15
Rede de contatos de pacientes com Tuberculose Fonte: Andre et
al., Transmission Network Analysis to Complement Routine
Tuberculosis Contact Investigations. American Journal of Public
Health. v. 96, 2006 Alta Intermediao (pontos crticos para
disseminao)
Slide 16
Intermediao Limitaes Menor caminho no o nico caminho que
importa Alternativas: random walk betweeness Custo
computacional
Slide 17
Proximidade Mede quo prximo est um n em relao a todos os outros
ns da rede Medida de eficincia Uma mensagem originada de uma posio
central ir se espalhar por toda rede com um custo mnimo Medida de
independncia Depende de poucos intermedirios, uma vez que pode
alcanar facilmente todos os ns da rede
Slide 18
Proximidade Clculo O nmero de caminhos geodsicos ligando p i a
p k. Somatrio de todos os caminhos geodsicos entre p i e p k
Slide 19
Proximidade Clculo Onde n 1 o tamanho da grafo - 1
Normalizao
Slide 20
Proximidade Limitaes: Mal definida para redes desconectadas Ns
adjacentes a um dado n de alta proximidade tambm tero alta
proximidade Mas no necessariamente sero ns importantes E.g., Redes
de co-autoria
Slide 21
Exemplo de Uso Example: Co-authorship networks (Liu 2008) Grau:
Autores que possuem muitos co-autores publicando artigos.
Proximidade: Autores que esto diretamente conectados a outros
autores bem conectados. Ex: Um estudante supervisionado por um
professor prestigiado. Intermediao: Autores que desempenham um
papel crucial na ligao de diferentes comunidades.
Slide 22
Outras Medidas ndice de Bonacich Alcance Page Rank
Slide 23
ndice de Bonacich Centralidade no significa necessariamente
poder (Hanneman 1998) Por um lado: Actors who have more ties have
greater opportunities because they have choices Por outro lado: the
actors that you are connected to are, themselves, well connected,
they are not highly dependent on you
Slide 24
Alcance Alcance (Reach) Ns de ns alcanados com dois passos
Similar ao grau, mas considera links indiretos
Slide 25
Page Rank Mecanismo de busca google Anlise de ligaes Atribuio
de pesos Centralidade leva em considerao que ns so mais
referenciados
Slide 26
Centralizao Mede o quo uma rede centralizada em torno de poucos
indivduos Exemplo: Freeman centralization (comparao com uma rede em
estrela caso extremo de rede centralizada) O que centralizao
realmente indica? Que maior poder pode ser exercido sobre os
outros? Rich clubs!!!
Slide 27
Concluses - Centralidade e Poder Centralidade tem sido vista
como uma medida de poder Em que situaes centralidade no poder?
Entretanto conceitos devem ser distinguidos: Centralidade Poder
Influncia Prestgio
Slide 28
Concluses - Centralidade e Poder Influncia depende no apenas da
estrutura da rede mas das interaes ao longo do tempo Ver Klout
Score - http://klout.com/home
Slide 29
Material de Estudo Centrality in Social Networks Conceptual
Clarification, by L. Freeman Centrality and Power (in Introduction
to Social Network Methods), by R. Hanneman