Mineração de Redes e Grafos

Prévia do material em texto

Mineração de Redes
Cristiano Carvalho
Grafos - Redes 
Complexas
Network Mining
O que são grafos?
Um grafo é definido formalmente como G = (V, E), 
onde V é o conjunto de vértices (entidades) 
conectados por E arestas (relacionamento)
A
B
D
E
FC
O que são grafos?
Rede Direcional
A B
D
E
F
C
O que são grafos?
Não Direcional
A B
D
E
F
C
O que são grafos?
Pesos nas conexões
A B
D
E
F
C
5
1
3
8
9
2
O que são grafos?
Exemplo de representação - Mídias sociais
A B
(RTs, shares, comments, likes ...)
Users
Por que estudar grafos/redes?
Importante ferramenta matemática com aplicação 
em diversas áreas do conhecimento 
Existem centenas de problemas computacionais 
que usam grafos com sucesso.
Por que estudar grafos/redes?
Identificar a habilidade de comunicação entre duas 
entidades em uma rede
Criar heurísticas ótimas/sub-rotinas para realizar 
busca de padrões em redes reais
Que tipo de dado você 
poderia modelar como 
um grafo?
Mineração de Redes
Cristiano Carvalho
Modelagem em 
Grafos
Internet
Sistema de Metrô
Contatos Sexuais
Colaboração entre Cientistas
Partidos Políticos
Interações Proteicas
Referências
Internet Mathematics - Further Directions
http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture5/lecture5.html
Sistema De Transporte Colectivo (metro)
https://www.taringa.net/posts/turismo/9228455/Sistema-De-Transporte-Colectivo-metro.html
The structure and function of complex networks
http://www.cin.ufpe.br/~rbcp/taia/structure-complex-networks.pdf
Grafo de partidos políticos
https://www.instagram.com/p/BhKJBeAFRRj/?utm_source=ig_web_copy_link
Yeast protein interaction network
https://services.math.duke.edu/~rtd/RGD/RGD.html
https://www.taringa.net/posts/turismo/9228455/Sistema-De-Transporte-Colectivo-metro.html
http://www.cin.ufpe.br/~rbcp/taia/structure-complex-networks.pdf
https://www.instagram.com/p/BhKJBeAFRRj/?utm_source=ig_web_copy_link
Métricas em Redes 
Complexas
Cristiano Carvalho
Medidas de 
Centralidade
Medidas de Centralidade
Grau
Closeness (Proximidade)
Betweenness (Intermediação)
Grau do Nó (Vértice)
É uma medida relativa aos vértices de um grafo
O grau de um vértice é dado pelo número de 
arestas que lhe são incidentes
Exemplo:
Grau 3 = A, B, D
Grau 2 = C, E 
Grau 1 = F
A
B
D
E
FC
Closeness - Proximidade
É definida pelo comprimento de caminhos mais 
curtos
Caminhos mais curtos representam a menor 
distância entre pares de vértices
Caminho
Em um grafo sem arestas ponderadas o caminho é 
definido pelo número de arestas de um ponto a 
outro
Exemplo:
A - F = (A-C-B-E-D-F) (5)
(A-B-E-D-F) (4) 
(A-D-F) (2)
A
B
D
E
FC
Caminho
Em um grafo sem arestas ponderadas o caminho é 
definido pelo número de arestas de um ponto a 
outro
Exemplo:
A - F = (A-C-B-E-D-F) (5)
(A-B-E-D-F) (4) 
(A-D-F) (2)
A
B
D
E
FC
Caminho mais curto
Em um grafo sem arestas ponderadas o caminho é 
definido pelo número de arestas de um ponto a 
outro
Exemplo:
A - F = (A-C-B-E-D-F) (5)
(A-B-E-D-F) (4) 
(A-D-F) (2)
A
B
D
E
FC
Closeness - Proximidade
Quanto mais central é o vértice menor é a 
distância total para todos os outros vértices
Exemplo: 
F = 11
1-D 
A
B
D
E
FC
Closeness - Proximidade
Quanto mais central é o vértice menor é a 
distância total para todos os outros vértices
Exemplo: 
F = 11
1-D + 2-E 
A
B
D
E
FC
Closeness - Proximidade
Quanto mais central é o vértice menor é a 
distância total para todos os outros vértices
Exemplo: 
F = 11
1-D + 2-E + 2-A
A
B
D
E
FC
Closeness - Proximidade
Quanto mais central é o vértice menor é a 
distância total para todos os outros vértices
Exemplo: 
F = 11
1-D + 2-E + 2-A + 
3-B + 3-C = 11
A
B
D
E
FC
Closeness - Proximidade
Quanto mais central é o vértice menor é a 
distância total para todos os outros vértices
Exemplo: 
D = 7
1-F + 2-E + 2-A + 
2-B + 2-C = 7
A
B
D
E
FC
Betweenness – Intermediação (Vértice)
● Define o número de vezes que um vértice age 
como ponte ao longo do caminho mais curto 
entre dois outros vértices
Betweenness – Intermediação (Vértice)
● Para cada par de vértices calcular os caminhos 
mais curtos entre eles
● Para cada par de vértices determinar a fração 
de caminhos mais curtos que passam através
do vértice em questão
● Somar esta fração de todos os pares de vértices
Betweenness – Intermediação (Vértice)
Exemplo: 
D = A – E 
A – F 
C – F A
B
D
E
FC
Betweenness – Intermediação (Vértice)
A
B
D
E
FC
Exemplo: 
D = A – E
A – F
C – F
Betweenness – Intermediação (Vértice)
A
B
D
E
FC
Exemplo: 
D = A – E
A – F 
C – F
Betweenness – Intermediação (Aresta)
A
B
D
E
FC
Exemplo: 
A - D = A – E
A – F
Betweenness – Intermediação (Aresta)
A
B
D
E
FC
Exemplo: 
A - D = A – E
A – F
Métricas em Redes 
Complexas
Cristiano Carvalho
Medidas de 
Importância
Medidas de Importância
PageRank
Hits
PageRank
PageRank procura expressar a probabilidade de 
um caminhante aleatório no grafo chegar a um 
vértice P
PageRank
Considera o quanto um vértice é referenciado (Ex: 
B)
Se quem aponta para o vértice também é 
importante (Observe C)
PageRank
A importância de um vértice P é dada pela seguinte 
equação:
PR(i) - PR do vértice i que aponta para A
Probabilidade inicial de todas = 1/N
L(i) - quantidade de links de saída em i
Desafios - Vértices sem ligações
A não recebe links de ninguém e passa a ter PR=0
B recebe 0 de A
Desafios - Ciclos 
Cálculo do PageRank fica "preso" no ciclo infinito
Em cada iteração o valor de PageRank é transmitido 
de um vértice para outro do ciclo e não há 
convergência
PageRank - Dump Factor
● d - dump factor (geralmente entre 0.1 e 0.9) 
○ Probabilidade de continuar seguindo os links.
○ Do contrário acontecerá um “teletransporte” 
para qualquer outro vértice
● N - Total de páginas
HITS - Hubs e Autoridades
● Um bom hub é uma página que aponta para 
boas autoridades
● Uma boa autoridade é uma página apontada por 
bons hubs.
HITS
Utiliza valores de hub e autoridade para definir a 
reputação de uma página P.
Hub de uma página “P”– é dado em função dos 
valores de autoridade das páginas para onde ela 
aponta.
Autoridade de uma página “P”– é dada em função 
dos valores de hub das páginas que apontam para P
Referências
PageRank
https://pt.m.wikipedia.org/wiki/Ficheiro:PageRank-hi-res.png
https://es.wikipedia.org/wiki/PageRank#/media/File:PageRanks-
Example.svg
https://pt.m.wikipedia.org/wiki/Ficheiro:PageRank-hi-res.png
Métricas em Redes 
Complexas
Cristiano Carvalho
KNIME: Análise de 
Influentes
Análise em Redes Sociais
❖ Selecionando os principais tweets
3
Uma vez que você tenha os tweets coletados o primeiro passo é extrair 
os principais tweets da base, ou seja aqueles que foram compartilhados
(retweets).
Análise em Redes Sociais
❖ Limpar tweets sem retweets
4
Com isso é possível diminuir 
o número de conexões a 
serem analisadas, focando 
apenas nos posts que 
existem conexões na rede
Análise em Redes Sociais
❖ Contar interações conexões entre usuários
5
Em seguida, vamos encontrar as conexões entre os usuários através dos 
seus compartilhamentos. Assim você tem dados para formar um grafo 
conectado de usuários e retweets.
Análise em Redes Sociais
❖ Agrupar usuários por retweets
6
Através da aba Manual 
Aggregation, conte (Count) 
quando (Time) um usuário 
retuitou outro usuário
(Agrupe Users e Retweet from)
Análise em Redes Sociais
❖ Resultado da contagem de conexões entre usuários
7
Observe que:
DannOfThursday_ retuitou ColonoGamer 1 vez
MailloLeandro retuitou nadyagospel 2 vezes
Análise em Redes Sociais
❖ Criando Grafo ou Rede de Conexões
8
Com o Object Inserter definimos 
quem serão os vértices (Nodes) a 
serem conectados, o que identifica 
as arestas (Edge) se haverá um peso 
para cada conexão (Weight Column)
Análise em Redes Sociais
❖ Rede de retweets (influenciadores)
9
Análise em Redes Sociais❖ Vamos enriquecer a rede com outros atributos
10
Análise em Redes Sociais
❖ E até outros formatos de visualização
11
Coleta em Redes Sociais
❖ Buscando informações de usuários no Twitter
12
Com o node Twitter Users 
buscamos informações de cada 
usuário. 
Precisamos da lista de usuários
a serem buscados. 
Análise de Redes
❖ Informações de Vértices
13
O Node (no sentido de Vértice) Table gera uma tabela com os vértices 
da rede
Podemos buscar informações 
já filtradas apenas para essa 
rede específica.
Com o Node Table extraímos 
os ids dos vértices da rede, ou 
seja nomes de usuários.
Análise de Redes
❖ Busca de dados de usuários
14
Agora podemos fornecer o ID 
dos usuários no node Twitter 
Users e buscar informações no 
Twitter.
Análise de Redes
15
❖ Agora temos dados para enriquecer a rede e suas respectivas conexões
Análise em Redes Sociais
❖ Inserindo atributos na rede
16
Com o node Multi Feature 
Inserter inserimos os dados 
na rede.
Quais entradas do node?
Análise em Redes Sociais
❖ Inserindo atributos na rede
17
Nesse exemplo estamos 
inserindo a foto do usuário e 
o número de followers. 
Porém em possível selecionar 
diversos atributos da lista
Análise em Redes Sociais
❖ Inserindo o foto no perfil na rede
18
Em Node Layout configuramos o 
campo Icon para utilizar a coluna
“Profile Image” com fotos que 
coletamos de cada usuário.
Coleta em Redes Sociais
❖ Customize o layout do grafo através das abas General
19
Métricas em Redes 
Complexas
Cristiano Carvalho
KNIME: Top Vértices
❖ Métricas
3
Leitura habitual 
da rede com o 
Network Reader
O Network Analyzer permite calcular várias métricas.
➢ Vamos calcular o grau do vértice, ou seja, o número total de ligações de cada 
vértice possui
➢ Além disso o grau de entrada e saída separadamente
Análise de Redes
❖ Métricas
4
Resultado do 
Network Analyzer
Análise de Redes
❖ Filtrando os top 5 vértices de maior grau total
5
Ordene os vértices por grau 
decrescente e filtre os 5 
maiores
Análise de Redes
❖ Retirando vértices
6
Com o Node Name Filter
podemos excluir da rede os 
vértices por nome. Nesse caso 
vamos incluir na rede apenas os 
vértices que filtramos 
anteriormente.
Obs: é preciso conectar também 
a rede original
Nota:
Não esqueça que “Node” em grafos significa vértice ou nó da rede e não um node do knime
Análise de Redes
❖ Hiperarestas
7
Com o Edge Degree Filter
eliminamos hiperarestas, 
ou seja selecionamos 
arestas que conectam no 
máximo dois vértices
Isso é necessário pois o visualizador 
do knime não aceita hipergrafos
Análise de Redes
❖ Grafo formado pelos 5 vértices de maior grau de entrada
8
Análise de Redes
❖ Grafo formado pelos 5 vértices de maior grau de entrada
(Resultado)
9
Análise de Redes
Métricas em Redes 
Complexas
Cristiano Carvalho
KNIME: Menor 
Caminho
❖ Qual o menor caminho entre Schwarzenegger e Isótopo?
3
A medida do menor caminho é implementada pelo node Shortest Path
Análise de Redes
❖ Qual o menor caminho entre Schwarzenegger e Isótopo?
4
Para visualizar uma 
rede utilizamos o 
Network Viewer
Análise de Redes
❖ Como assim? Jurassic Park easter egg
5
Análise de Redes
http://screencrush.com/lost-world-jurassic-park-easter-egg/
Expressões Regulares
Cristiano Carvalho
KNIME: Regex
❖ Expressões Regulares ou Regex (notações)
3
Extração de Texto por Regras
Semelhante aos wildcards as expressões regulares permitem a criação 
de diversos tipos de regras para tratar o texto.
http://turing.com.br/material/regex/introducao.html
❖ Exemplos simples (referência)
4
Extração de Texto por Regras
➢ A RegEx [c9] reconhece o padrão c e o padrão 9
➢ A RegEx [A-Z] reconhece todas as letras maiúsculas
➢ A RegEx [A-Z0-9] reconhece todas as letras maiúsculas e números
➢ A classe \d é equivalente à classe [0-9]
http://aprenda.vidageek.net/aprenda/regex
Pré-processamento
❖ Exemplo em pré-processamento
Adicionando o Regex Filter é possível filtrar o texto a partir de 
regras. Com “.*[\d\W]+.*” eliminamos strings que possuem 
dígitos (\d) e caracteres que não são letras (\W)
5
Pré-processamento
❖ Como filtrar por número específico de caracteres
A regra “\d{4}” especifica o padrão de quatro dígitos
Podemos ter o mesmo resultado utilizando “[0-9]{4}”
Explore mais exemplos http://aprenda.vidageek.net/aprenda/regex
e teste no KNIME, com o Row Filter sobre uma coluna de String fica bem 
facinho :)
6
http://aprenda.vidageek.net/aprenda/regex
Referências
Expressões regulares: introdução
http://turing.com.br/material/regex/introducao.html
Aprenda RegEx
http://aprenda.vidageek.net/aprenda/regex