Um guia para previsão de links - Como prever suas conexões futuras no Facebook

Visão geral

  • Uma introdução para vincular a previsão, como ela funciona e onde você pode usá-la no mundo real
  • Saiba mais sobre a importância da Previsão de Link nas mídias sociais
  • Crie seu primeiro modelo de Predição de Link para um caso de uso do Facebook usando Python

Introdução

Você já se perguntou quem seria sua próxima conexão com o Facebook? Curioso para saber quem é o próximo pedido?

E se eu lhe dissesse que havia uma maneira de prever isso?

Adoro fazer brainstorming e apresentar essas declarações de problemas quando estou navegando na minha conta do Facebook. É uma das vantagens de ter a mentalidade de um cientista de dados!

A maioria das plataformas de mídia social, incluindo o Facebook, pode ser estruturada como gráficos. Os usuários registrados estão interconectados em um universo de redes. E para trabalhar nessas redes e gráficos, precisamos de um conjunto diferente de abordagens, ferramentas e algoritmos (em vez dos métodos tradicionais de aprendizado de máquina).

Portanto, neste artigo, resolveremos um problema de rede social com a ajuda de gráficos e aprendizado de máquina. Primeiro entenderemos os principais conceitos e componentes da previsão de links antes de iniciar um estudo de caso do Facebook e implementá-lo em Python!

Eu recomendo que você leia os artigos abaixo para entender o que são gráficos e como eles funcionam:

Índice

  1. Uma visão geral do Social Network Analytics
  2. Uma cartilha sobre previsão de links
  3. Estratégia para resolver um problema de previsão de links
  4. Estudo de caso: prever conexões futuras entre páginas do Facebook - Compreender os dados - construção de modelo de preparação de conjunto de dados - extração de recursos - construção de modelo: modelo de previsão de link

Uma visão geral do Social Network Analytics

Vamos definir uma rede social antes de mergulharmos no conceito de previsão de link.

Uma rede social é essencialmente uma representação dos relacionamentos entre entidades sociais, como pessoas, organizações, governos, partidos políticos, etc.

As interações entre essas entidades geram quantidades inimagináveis ​​de dados na forma de postagens, mensagens de bate-papo, tweets, curtidas, comentários, compartilhamentos etc. Isso abre uma janela de oportunidades e casos de uso nos quais podemos trabalhar.

Isso nos leva ao Social Network Analytics (SNA). Podemos defini-lo como uma combinação de várias atividades que são realizadas nas mídias sociais. Essas atividades incluem a coleta de dados de sites de mídia social online e o uso desses dados para tomar decisões de negócios.

Os benefícios da análise de redes sociais podem ser altamente gratificantes. Aqui estão alguns dos principais benefícios:

  • Ajuda você a entender melhor seu público
  • Usado para segmentação de clientes
  • Usado para projetar sistemas de recomendação
  • Detecte notícias falsas, entre outras coisas

Uma cartilha sobre previsão de links

A previsão de links é um dos tópicos de pesquisa mais importantes no campo de gráficos e redes. O objetivo da previsão de link é identificar pares de nós que formarão um link ou não no futuro.

A previsão de links é muito utilizada em aplicativos do mundo real. Aqui estão alguns dos casos de uso importantes da previsão de links:

  • Preveja quais clientes provavelmente comprarão quais produtos em mercados online como a Amazon. Pode ajudar a fazer melhores recomendações de produtos
  • Sugerir interações ou colaborações entre funcionários de uma organização
  • Extraia informações vitais de redes terroristas

Neste artigo, exploraremos um caso de uso ligeiramente diferente de previsão de links - previsão de links em uma rede social online!

Estratégia para resolver um problema de previsão de links

Se, de alguma forma, podemos representar um gráfico na forma de um conjunto de dados estruturado com um conjunto de recursos, talvez possamos usar o aprendizado de máquina para prever a formação de links entre os pares de nós não conectados do gráfico.

Vamos pegar um gráfico fictício para entender essa ideia. Dado a seguir é um gráfico de 7 nós e os pares de nós não conectados são AF, BD, BE, BG e EG:

Gráfico no momento t

Agora, digamos que analisamos os dados e criamos o gráfico abaixo. Algumas novas conexões foram formadas (links em vermelho):

Gráfico no tempo t + n

Precisamos ter um conjunto de variáveis ​​preditoras e uma variável alvo para criar qualquer tipo de modelo de aprendizado de máquina, certo? Então, onde estão essas variáveis? Bem, podemos obtê-lo a partir do próprio gráfico! Vamos ver como é feito.

Nosso objetivo é prever se haveria um link entre dois nós não conectados. Da rede no momento t, podemos extrair os seguintes pares de nós que não têm links entre eles:

  1. AF
  2. BD
  3. ESTAR
  4. BG
  5. POR EXEMPLO

Observe que, por conveniência, considerei apenas os nós com alguns links separados.

O próximo passo para nós é criar recursos para cada par de nós. A boa notícia é que existem várias técnicas para extrair recursos dos nós em uma rede. Digamos que usamos uma dessas técnicas e construímos recursos para cada um desses pares. No entanto, ainda não sabemos qual é a variável de destino. Nada para se preocupar - também podemos obter isso facilmente.

Veja o gráfico no momento t + n. Podemos ver que existem três novos links na rede para os pares AF, BD e BE, respectivamente. Portanto, atribuiremos a cada um deles o valor 1. Os pares de nós BG e EG receberão 0, porque ainda não há links entre os nós.

Portanto, os dados ficarão assim:

Agora que temos a variável de destino, podemos construir um modelo de aprendizado de máquina usando esses dados para realizar a previsão de links.

Portanto, é assim que precisamos usar gráficos sociais em duas instâncias diferentes para extrair a variável de destino, ou seja, a presença de um link entre um par de nós. No entanto, lembre-se de que, em cenários do mundo real, teremos dados apenas do momento atual.

Extrair dados de um gráfico para criar seu modelo

Na seção acima, conseguimos obter rótulos para a variável de destino porque tínhamos acesso ao gráfico no momento t + n. No entanto, em cenários do mundo real, teríamos apenas um conjunto de dados de gráficos em mãos. É isso aí!

Digamos que temos o gráfico abaixo de uma rede social em que os nós são os usuários e as bordas representam algum tipo de relacionamento:

Os pares de nós candidatos, que podem formar um link posteriormente, são (1 e 2), (2 e 4), (5 e 6), (8 e 10) e assim por diante. Temos que construir um modelo que preveja se haveria um link entre esses pares de nós ou não. É disso que se trata a previsão de links!

No entanto, para criar um modelo de previsão de links, precisamos preparar um conjunto de dados de treinamento a partir deste gráfico. Isso pode ser feito usando um truque simples.

Imagine isso - como esse gráfico seria em algum momento do passado? Haveria menos arestas entre os nós porque as conexões em uma rede social são construídas gradualmente ao longo do tempo.

Portanto, mantendo isso em mente, podemos ocultar aleatoriamente algumas das arestas do gráfico fornecido e seguir a mesma técnica explicada na seção anterior para criar o conjunto de dados de treinamento.

Retirar links do gráfico

Ao remover links ou arestas, devemos evitar remover qualquer aresta que possa produzir um nó isolado (nó sem aresta) ou uma rede isolada. Vamos tirar algumas das arestas da nossa rede:

Como você pode ver, as arestas nos pares de nós (1 e 4), (7 e 9) e (3 e 8) foram removidas.

Adicionar etiquetas aos dados extraídos

Em seguida, precisaríamos criar recursos para todos os pares de nós não conectados, incluindo aqueles para os quais omitimos as arestas. As arestas removidas serão rotuladas como '1' e os pares não conectados como '0'.

A variável de destino ficará altamente desequilibrada neste conjunto de dados. É o que você encontrará nos gráficos do mundo real também. O número de pares de nós não conectados seria enorme.

Vamos fazer um estudo de caso e resolver o problema de previsão de links usando Python.

Estudo de caso: prever conexões futuras entre páginas do Facebook

É aqui que aplicaremos todas as opções acima em um cenário incrível do mundo real.

Trabalharemos com um conjunto de dados gráficos no qual os nós são páginas do Facebook de populares lanches e chefs de renome de todo o mundo. Se houver duas páginas (nós) iguais, existe uma borda (link) entre elas.

Você pode baixar o conjunto de dados aqui.

Objetivo: criar um modelo de previsão de links para prever futuros links (curtidas mútuas) entre nós não conectados (páginas do Facebook).

Vamos iniciar o nosso Jupyter Notebook (ou Colab)!

Compreendendo os dados

Primeiro importaremos todas as bibliotecas e módulos necessários:

Vamos carregar as páginas do Facebook como nós e curtidas mútuas entre as páginas e as bordas:

Saída: (620, 2102)

Temos 620 nós e 2.102 links. Vamos agora criar um quadro de dados de todos os nós. Cada linha desse quadro de dados representa um link formado pelos nós nas colunas 'node_1' e 'node_2', respectivamente:

fb_df.head ()

Os nós '276', '58', '132', '603' e '398' formam links com o nó '0'. Podemos facilmente representar esse arranjo de páginas do Facebook na forma de um gráfico:

Uau, isso parece bastante. É com isso que vamos lidar - uma malha de páginas do Facebook (pontos azuis). As linhas pretas são os links ou arestas que conectam todos os nós.

Preparação de conjunto de dados para construção de modelo

Precisamos preparar o conjunto de dados a partir de um gráfico não direcionado. Esse conjunto de dados terá recursos de pares de nós e a variável de destino seria de natureza binária, indicando a presença de links (ou não).

Recuperar pares de nós não conectados - amostras negativas

Já entendemos que, para resolver um problema de previsão de link, precisamos preparar um conjunto de dados a partir do gráfico fornecido. Uma parte importante desse conjunto de dados são as amostras negativas ou os pares de nós não conectados. Nesta seção, mostrarei como podemos extrair os pares de nós não conectados de um gráfico.

Primeiro, criaremos uma matriz de adjacência para descobrir quais pares de nós não estão conectados.

Por exemplo, a adjacência do gráfico abaixo é uma matriz quadrada na qual as linhas e colunas são representadas pelos nós do gráfico:

Os links são indicados pelos valores na matriz. 1 significa que há um link entre o par de nós e 0 significa que há um link entre o par de nós. Por exemplo, os nós 1 e 3 têm 0 na junção cruzada na matriz e esses nós também não têm arestas no gráfico acima.

Usaremos essa propriedade da matriz de adjacência para encontrar todos os pares de nós não conectados no gráfico original G:

Vamos verificar a forma da matriz de adjacência:

adj_G.shape

Saída: (620, 620)

Como você pode ver, é uma matriz quadrada. Agora, atravessaremos a matriz de adjacência para encontrar as posições dos zeros. Observe que não precisamos passar por toda a matriz. Os valores na matriz são os mesmos acima e abaixo da diagonal, como você pode ver abaixo:

Podemos pesquisar os valores acima da diagonal (parte verde) ou os valores abaixo (parte vermelha). Vamos procurar os valores diagonais para zero:

Aqui está quantos pares de nós não conectados temos em nosso conjunto de dados:

len (all_unconnected_pairs)

Saída: 19,018

Temos 19.018 pares não conectados. Esses pares de nós atuarão como amostras negativas durante o treinamento do modelo de previsão de link. Vamos manter esses pares em um dataframe:

Remover links de pares de nós conectados - amostras positivas

Como discutimos acima, removeremos aleatoriamente algumas das arestas do gráfico. No entanto, a remoção aleatória das arestas pode resultar no corte de nós e fragmentos fracamente conectados do gráfico. Isso é algo que temos que cuidar. Temos que garantir que, no processo de soltar arestas, todos os nós do gráfico permaneçam conectados.

No bloco de código abaixo, primeiro verificaremos se a queda de um par de nós resulta na divisão do gráfico (number_connected_components> 1) ou na redução no número de nós. Se as duas coisas não acontecerem, abandonamos esse par de nós e repetimos o mesmo processo com o próximo par de nós.

Eventualmente, obteremos uma lista de pares de nós que podem ser removidos do gráfico e todos os nós ainda permanecerão intactos:

len (omissible_links_index)

Saída: 1483

Temos mais de 1400 links que podemos remover do gráfico. Essas arestas soltas servirão como exemplos positivos de treinamento durante o treinamento do modelo de previsão de link.

Dados para o treinamento do modelo

Em seguida, anexaremos essas arestas removíveis ao quadro de dados de pares de nós não conectados. Como essas novas arestas são amostras positivas, elas terão um valor alvo de '1':

Vamos verificar a distribuição dos valores da variável de destino:

data ['link']. value_counts ()

0 -19018 1 -1483

Acontece que esses são dados altamente desequilibrados. A proporção de link vs nenhum link é apenas perto de 8%. Na próxima seção, extrairemos recursos para todos esses pares de nós.

Extração de recursos

Usaremos o algoritmo node2vec para extrair recursos do nó do gráfico depois de remover os links. Então, primeiro vamos criar um novo gráfico depois de soltar os links removíveis:

Em seguida, instalaremos a biblioteca node2vec. É bastante semelhante ao algoritmo DeepWalk. No entanto, envolve caminhadas aleatórias tendenciosas. Para saber mais sobre o node2vec, você deve definitivamente conferir este documento node2vec: Aprendizagem de recursos escalável para redes.

Por enquanto, lembre-se de que node2vec é usado para representação vetorial de nós de um gráfico. Vamos instalá-lo:

! pip install node2vec

Pode demorar um pouco para instalar em sua máquina local (é bastante rápido se você estiver usando o Colab).

Agora, treinaremos o modelo node2vec em nosso gráfico (G_data):

Em seguida, aplicaremos o modelo node2vec treinado em cada par de nós no 'data' do quadro de dados. Para calcular os recursos de um par ou uma aresta, adicionaremos os recursos dos nós nesse par:

x = [(n2w_model [str (i)] + n2w_model [str (j)]) para i, j em zip (dados ['node_1'], dados ['node_2'])]

Construindo nosso modelo de previsão de links

Para validar o desempenho do nosso modelo, devemos dividir nossos dados em duas partes - uma para treinar o modelo e a outra para testar o desempenho do modelo:

Vamos ajustar primeiro um modelo de regressão logística:

Agora, faremos previsões no conjunto de testes:

previsões = lr.predict_proba (xtest)

Usaremos a pontuação AUC-ROC para verificar o desempenho do nosso modelo.

roc_auc_score (ytest, previsões [:, 1])

Saída: 0.7817

Obtemos uma pontuação de 0,78 usando um modelo de regressão logística. Vamos ver se podemos obter uma pontuação melhor usando um modelo mais complexo.

O treinamento parou após a 208ª iteração porque aplicamos os critérios de parada precoce. Mais importante ainda, o modelo obteve uma impressionante pontuação de 0,9273 AUC no conjunto de testes. Convido você a dar uma olhada na documentação do lightGBM para aprender mais sobre os diferentes parâmetros.

Notas finais

Existe um enorme potencial nos gráficos. Podemos aproveitar isso para resolver um grande número de problemas do mundo real, dos quais a previsão de links é um deles.

Neste artigo, mostramos como um problema de previsão de link pode ser resolvido usando o aprendizado de máquina e quais são as limitações e os aspectos importantes que devemos ter em mente ao resolver esse problema.

Sinta-se à vontade para fazer qualquer pergunta ou deixar seu feedback na seção de comentários abaixo. Continue explorando!

Publicado originalmente em https://www.analyticsvidhya.com em 16 de janeiro de 2020.