Aprendizado de Máquina Supervisionado na Predição de Links

em Redes Complexas Uma Revisão Sistemática

Orlando da Silva Junior Dra. Ana Carolina Lorena

Contexto

• Redes Complexas são estudadas em diversas áreas do conhecimento – Pesquisa em ciências humanas

– Pesquisa em ciências exatas

• Avanços na pesquisa – Proposição de novas tarefas

– Proposição de novas aplicações

– Proposição de novos estudos

PREDIÇÃO DE LINKS

Contexto

• Predição de Links – Trata do problema das ligações nas redes

• Como fazer aplicações em redes incompletas?

• Por que esses nós não estão conectados?

• Esses nós poderiam se conectar no futuro?

– Técnicas para solucionar esses problemas • Aprendizado de Máquina

– Não-Supervisionado

– Supervisionado

Objetivo do Trabalho

• Investigar como o Aprendizado de Máquina Supervisionado resolve o problema da Predição de Links em Redes Complexas

• Como? Utilizando Revisão Sistemática

– Processo sistemático para realização de revisão bibliográfica

Revisão Sistemática

• Estudo secundário

– Auxilia na definição de uma metodologia para identificar, analisar e interpretar todas as evidências disponíveis em questão de pesquisa específica

• Identificação das

necessidades da revisão

• Definição do protocolo de revisão

Planejamento

• Aplicação do protocolo

• Extração de informações

Condução

• Formato da publicação

• Meios de divulgação

Publicação

Revisão Sistemática

• Objetivos da revisão

– Identificar uma teoria geral sobre Predição de Links;

– Buscar como a abordagem supervisionada é utilizada para resolver o problema da Predição de Links;

– Encontrar bases de dados para benchmarking;

– Identificar a forma como a Predição de Links colabora para a Teoria das Redes.

Revisão Sistemática | Planejamento

• Necessidade: nenhuma outra publicação semelhante encontrada

• Questões de pesquisa

– Como o paradigma da aprendizagem supervisionada resolve o problema da Predição de Links?

– Como funciona a Predição de Links?

Revisão Sistemática | Planejamento

• Pergunta 1: Como o paradigma da aprendizagem supervisionada resolve o problema da Predição de Links?

– Quais são as principais técnicas de Aprendizado Supervisionado utilizadas na

Predição de Links?

– Qual é o tipo de problema supervisionado na Predição de Links?

– Como os conjuntos de dados são estruturados?

– Quais são os principais atributos e métricas utilizados?

– Qual é a metodologia experimental adotada?

– Quais são os algoritmos base usados na comparação de resultados?

Revisão Sistemática | Planejamento

• Pergunta 2: Como funciona a Predição de Links?

– Quais são as bases de dados comumente usadas?

– Que tipo de aplicações tratam do problema da Predição de Links?

Revisão Sistemática | Planejamento

• Aprendizado de Máquina Supervisionado – supervised machine learning – supervised learning – pattern recognition – data mining

• Predição de Links – link prediction – link mining – link analysis

• Redes Complexas – network – networks

Portais de Referências Bibliográficas escolhidos • Portal ACM (ACM Digital Library) • Portal IEEE (IEEE Xplore) • Science Direct • Web of Science • CiteSeerX

• Scopus

Expressão geral de busca

Revisão Sistemática | Planejamento

• Critérios de exclusão – Publicações que não tratam de Predição de Links

• Aplicação ou utilização no tema

– Publicações restritas • Acesso não limitado à UFABC ou UNIFESP

– Publicações com idioma inacessível • Português, inglês ou espanhol

– Restrição por tipo de publicação • Conferências ou periódicos

Revisão Sistemática | Planejamento

Título do Trabalho

• Relação com os tópicos de pesquisa

Resumo

• Referência a Predição de Links

Texto

• Leitura parcial

• Predição de Links com Aprendizado Supervisionado

Extração de Informações • Título do Trabalho • Autores • Tipo de publicação • Local e ano • Portal bibliográfico • Observações

Revisão Sistemática | Condução

• Aplicação do protocolo anterior

– Adaptação da expressão de busca aos portais escolhidos

Portal Bibliográfico Quantidade

Scopus 107

Portal IEEE 76

Web of Science 36

CiteSeerX 25

Portal ACM 12

Science Direct 3

Final: 33

Trabalhos

Revisão Sistemática | Condução

• Pesquisa entre 07/novembro/2012 e 17/novembro/2012

Publicações por ano

Resultados e Discussão

Resultados |Modelagem

• 𝑮(𝒕) é um grafo que sumariza de algum modo a sequência temporal 𝑮 = (𝑮(𝟏), … , 𝑮(𝒕))

• Toda rede em G é do tipo 𝑮 = (𝑽, 𝑬): – 𝑽 é o conjunto de vértices – 𝑬 é o conjunto de arestas, com 𝒆 = (𝒖, 𝒗)

• 𝑮(𝒕 + 𝟏) é rotulado

– Presença de links +1 – Ausência de links -1

• Os vértices u e v pertencem aos grafos 𝑮(𝒕) e 𝑮(𝒕 + 𝟏), mas o par (𝒖, 𝒗) – aresta – só existe em 𝑮(𝒕 + 𝟏)

Problema Binário

Resultados |Conjuntos de Dados

Tipo de Rede Tipo ou Fonte de Dados

Rede Social

DBLP

Facebook

arXiv

Rede de Informação

Enron

CiteSeer

Wikipedia

Rede Biológica KEGG PATHWAY

Proteína-proteína

Rede Tecnológica Chamadas Telefônicas

Utilizadas como Redes Sociais

Principal

Resultados | Métricas

• As métricas são as medidas de Análise de Redes Complexas

– Qualificam a topologia e definem as configurações da rede

• Análise da estrutura da rede sem necessidade de representações gráficas

– Cálculos estatísticos

Rede de interações proteína-proteína em Saccharomyces cerevisiae

(http://www.visualcomplexity.com)

Resultados | Métricas

Métrica Quantidade

+

Vizinhos Comuns (VC) 18

Coeficiente de Adamic-Adar (AA) 16

Coeficiente de Jaccard (JC) 16

Conexão Preferencial (CP) 14

Katz (K) 13

- Caminho Mais Curto (CMC) 9

Graus do Nó (g) 8

𝚪(𝐱) é o conjunto de vizinhos do nó x.

𝑉𝐶 𝑢, 𝑣 = |Γ 𝑢 ∩ Γ 𝑣 |

𝐴𝐴 𝑢, 𝑣 = 1

log |Γ 𝑤 | 𝑤 ∈ Γ(u,v)

𝐽𝐶 𝑢, 𝑣 =|Γ 𝑢 ∩ Γ 𝑣 |

|Γ 𝑢 ∪ Γ 𝑣 |

𝐶𝑃 𝑢, 𝑣 = |Γ 𝑢 | ∙ |Γ 𝑣 | 𝐾 𝑢, 𝑣 = 𝛽𝑙 ∙ 𝑝𝑎𝑡ℎ𝑠 𝑙 𝑢,𝑣

∞

𝑙=1

𝑔 𝑢 = |Γ 𝑢 |

Resultados | Métodos

Técnica Quantidade

Árvore de Decisão 10

SVM 9

Naive Bayes 5

Regressão 6

Rede Neural 3

k-NN 3

Técnica Quantidade

Modelos probabilísticos 7

Ensembles 8

Outras técnicas 5

Proposições 5

Principais

Bons Resultados

Bons Resultados

C4.5

Resultados | Algoritmos de Base

• São algoritmos não-supervisionados utilizados pelos trabalhos a fim de comparar com os algoritmos supervisionados.

• Quais foram os algoritmos? – Comparação entre predidores – Classificador aleatório – Medidas de rede: Katz e Coeficiente de Adamic-Adar

• Mas: nem todos os trabalhos realizaram essa

comparação ou não deixaram claro – Deficiência na literatura de Predição de Links

Resultados | Metodologia

• Como conduzir e avaliar os experimentos? – Amostragem – Avaliação

• Amostragem – Validação Cruzada – 10 subconjuntos

• Avaliação – Área Abaixo da Curva ROC (AUC); ou – Precisão, Acurácia e Revocação

Abordagem Mais Frequente

Alto Desbalanceamento De Classes

Resultados | Aplicações

Aplicações de Segurança

Segurança física

Segurança virtual Academia e Pesquisa

Coautoria

Citações Sistemas de Recomendação

Recomendação de produtos

Recomendação de especialistas

Mineração de Links

Classificação de Objetos

Entity Resolution

Conclusão

• O trabalho investigou como o Aprendizado de Máquina Supervisionado resolve o problema da Predição de Links em Redes Complexas – Revisão Sistemática

• Formulação de questões de pesquisa • Elaboração e execução de protocolo de pesquisa

• Os resultados da pesquisa mostram: – Vantagens e desvantagens da abordagem supervisionada – Método padrão de construção de conjuntos de dados – Principais métricas de redes – Principais bases para benchmarking – Algoritmos mais frequentemente utilizados – Abordagens experimentais mais adotadas

• Trabalhos futuros: redes dinâmicas e métodos de avaliação experimental