🚵🏾 🌳 🔫 Identifique comunidades cruzadas no Instagram para identificar os interesses dos usuários ⛄️ 🥙 👧🏼

Quanto um perfil em uma rede social pode dizer sobre uma pessoa? Fotos, postagens, comentários, assinaturas - um campo intocado para análise. Hoje falaremos sobre como determinamos os interesses dos usuários com base em suas assinaturas do Instagram.

Fonte

A abordagem óbvia é categorizar as assinaturas de uma pessoa. Por exemplo, entre as assinaturas do usuário Ivan, encontramos dois autobloggers e três contas com fotos engraçadas, o restante dos perfis não é temático (assumimos que sejam amigos, parentes, colegas etc.). A partir disso, concluímos: Ivan é uma pessoa alegre, que gosta de carros. Lucro Tudo o que precisamos é da correspondência "blogger + tema de conteúdo", mas nem tudo é tão simples aqui.

Quem é um blogueiro? Um blogueiro no Instagram não é diferente de uma conta comum (e, em geral, é algo como um estado de espírito). Idealmente, estamos interessados em contas temáticas com uma grande parcela de uma audiência ao vivo, embora não desejássemos simplesmente cortar o número de assinantes, podemos perder algo.

Onde obter uma boa taxonomia? Se você mesmo criar as categorias, algo interessante certamente se perderá em “coisas diferentes” e, quando tudo estiver pronto, as categorias são muito amplas. Queremos obter uma partição natural e, portanto, agruparemos blogueiros.

Um blogueiro pode pertencer a várias categorias? Assim mesmo! Muitas vezes, ele é simultaneamente um suíço, um ceifador e um cara tocando gajo (assim como viagens, estilo de vida, esposa e mãe).
Portanto, precisamos de um conjunto de dados com um número muito grande de blogueiros e um algoritmo de cluster com clusters que se cruzam na saída.

Como tudo começou

Somos abordados por clientes que desejam colocar seus anúncios com líderes de opinião no Instagram com mais eficiência. Às vezes, há uma lista de blogueiros e, em seguida, resolvemos o problema de otimização - para alcançar mais pessoas por menos dinheiro, e às vezes não há lista e blogueiros relevantes precisam ser encontrados. Dessa vez, eles procuraram perfis de oftalmologistas.

Usamos uma abordagem semelhante a um sistema de recomendação:

Escolha 3-7 perfis adequados com as mãos ("comunidade principal")
Usando a interseção de assinantes, identificamos pessoas interessadas no tópico (“entusiasmadas”)
Estamos à procura de novos médicos nas assinaturas de pessoas "entusiasmadas"
Se necessário, repita as etapas de 1 a 3 (adicionando novos médicos ao "núcleo" ou alterando-o)

Agora, mais um exemplo.

Etapa 1. Usando uma pesquisa no Instagram, selecionamos 6 contas de oftalmologistas de diferentes regiões da Rússia:

A lista é bastante aleatória, mas foi o suficiente para nós que o blog realmente correspondesse ao tópico e que os assinantes não passassem de 1000 pessoas.

Etapa 2. Depois de cruzar todos os assinantes, analisamos a distribuição.

Número de seguidores mútuos	Número de contas
6	2
5	3
4	24
3	102
2	693
1	30025

Viva! Existem cruzamentos.

Além disso, existem duas pessoas inscritas nos seis perfis! Então, agora você precisa determinar quem consideramos oftalmologia “entusiasta”. Decidimos levar todos, começando com três assinaturas. Como se costuma dizer, 1 vez é um acidente, 2 vezes é uma coincidência, 3 é uma regularidade. Assim, foram encontrados 131 (2 + 3 + 24 + 102) usuários “entusiasmados”.

Etapa 3. Faça o download das assinaturas de pessoas “entusiasmadas” e agregue novamente de todas as maneiras possíveis.

Temos uma lista impressionante de contas, das quais selecionaremos agora novos oftalmologistas. A coluna da direita mostra quantas das 131 pessoas que foram selecionadas na segunda etapa estão inscritas no perfil. No topo, havia perfis dos seis originais, o que não é surpreendente. Se agora selecionarmos um limite e dissermos: “Todos os perfis com um valor de contagem superior a dez são novos médicos”, corremos o risco de atribuir contas populares como Olga Buzova a oftalmologistas e, ao mesmo tempo, perdemos perfis pequenos, mas relevantes, então adicione mais um coluna o número de assinantes e calcule a porcentagem de usuários entusiasmados entre os assinantes.

Por conveniência, a fração é multiplicada por 100 (portanto, compartilhar é a porcentagem de fato). Como resultado, com a contagem de condição> = 6 e compartilhamento> = 0,05, 166 novos oftalmologistas receberam. Classe!

Etapa 4. 172 contas tornaram-se o novo "núcleo" da comunidade, o que ajudou a encontrar cerca de 500 novos oftalmologistas, mas o resultado já foi transferido para contas estrangeiras.

Contas semelhantes nas recomendações do Instagram

Tudo isso é interessante, é claro, e agora sabemos como encontrar contas semelhantes, mas ainda sonhamos em dividir todos os instaladores em categorias. E então surgiu a idéia de analisar as recomendações prontas do instagram.

O fato é que as contas temáticas têm recomendações, mas as pessoas comuns não. Aqui está a resposta para a pergunta de quem considerar os blogueiros e menos uma dor de cabeça. Viva!

Nas recomendações, um blogueiro tem até 80 perfis semelhantes. Tínhamos uma lista de 1000 blogs russos, começamos com ela. Eles pegaram similares, depois similares, então ... bem, você entende :)

O plano era que algum dia esse processo terminasse, pois pequenos perfis com algumas centenas de assinantes não serão incluídos nas recomendações, mas paramos quando a paciência terminou. Você sempre pode continuar coletando o conjunto de dados, mas até agora ele não foi útil, com uma alta probabilidade de cobrirmos quase todos os blogueiros russos e tudo bem.

Agora, temos um gráfico com 3.428.453 vértices (blogueiros) e 96.967.974 arestas (semelhança de dois blogueiros entre si).

É assim que nosso gráfico se parece com uma amostra muito pequena

A propósito, verificou-se que não fomos os primeiros a escolher essa abordagem.

Aparentemente, as recomendações no Instagram são formadas com base em quem os seguidores deste perfil ainda estão seguindo, para que o médico de Bryansk tenha contas populares de Bryansk e outros médicos nas recomendações. Isso é semelhante à nossa busca por oftalmologistas, mas agora podemos levar em consideração todas as comunidades às quais o blogueiro pertence ao mesmo tempo. Além disso, a velocidade de processamento aumenta significativamente, porque não há necessidade de analisar todos os assinantes do blogueiro, basta apenas 80 contas recomendadas.

Seleção e descrição do algoritmo

Ótimo! Os dados foram preparados, agora precisamos escolher uma ferramenta e um algoritmo que possam lidar com um gráfico tão grande, de preferência em um tempo adequado. Deixe-me lembrá-lo de que, na saída, queremos obter um conjunto de comunidades onde um blogueiro pode pertencer a várias delas.

Optamos pela biblioteca do SNAP (Stanford Network Analysis Platform)

A Stanford Network Analysis Platform (SNAP) é uma biblioteca de mineração de gráficos e análise de rede de uso geral. Ele é escrito em C ++ e é facilmente escalável para redes massivas com centenas de milhões de nós e bilhões de bordas. Ele manipula eficientemente grandes gráficos, calcula propriedades estruturais, gera gráficos regulares e aleatórios e suporta atributos em nós e arestas.

Chamamos a atenção para o algoritmo AGMfit (AGM - Affilated Graph Model) e, como resultado, usamos o BIGCLAM (Cluster Affiliation Model for Big Networks). Eles diferem apenas no primeiro caso, o problema de otimização é resolvido combinatoriamente, o que o torna menos escalável, e o segundo apenas permite alimentar gráficos como o nosso.

A idéia principal e bastante intuitiva: quanto mais dois nós tiverem comunidades em comum, maior a probabilidade de comunicação entre esses dois nós. Os dois algoritmos são baseados no Affilated Graph Model, então vamos falar mais detalhadamente:

Suponha que tenhamos um gráfico bipartido em que os picos redondos são comunidades (

A

$A$ e

B

$B$ ) e square - usuários da rede social e cada pessoa (

u

$u$ ) refere-se a diferentes comunidades com pesos específicos (

F_{u A}

$F_ {uA}$ e

F_{u B}

$F_ {uB}$ ) Quanto maior o peso, maior a probabilidade de o participante estar conectado (familiarizado) com outros membros da comunidade.

Exemplo: colegas que estudaram na mesma universidade se seguem no Instagram. Ambos são graduados da mesma universidade (comunidade 1) e trabalham na mesma empresa (comunidade 2), não sabemos o que causou a “amizade” na rede e quando eles se conheceram. Se alguém se formar na universidade e conseguir um emprego, e o segundo se formar há cinco anos e estiver trabalhando na empresa esse tempo todo, o peso de pertencer à primeira comunidade 1 será maior e a comunidade 2 menor e vice-versa.

Para cada comunidade comum de duas pessoas, temos uma chance independente de nos familiarizar:

1 - e x p (- F_{u c} c d o t F_{v c})

$1 - exp (-F_ {uc} \ cdot F_ {vc})$

Assim, quanto mais comuns as comunidades, maior a probabilidade de elas se conhecerem:

1 - e x p (- s u m_{c} F_{u c} c d o t F_{v c})

$1 - exp (- \ sum_c F_ {uc} \ cdot F_ {vc})$

Se calcularmos a probabilidade de uma conexão entre cada par de usuários, na saída obteremos um gráfico em que os vértices são pessoas e as arestas entre elas são um fato de conhecimento ou assinatura um do outro.

Assim, da vista à esquerda, passamos para a foto à direita.

Agora vamos entender como esse modelo é usado na descoberta da comunidade.

Temos um gráfico de blogueiros semelhantes e nosso objetivo é descobrir

K

$K$ comunidades usando o modelo descrito acima, selecionando a matriz de peso mais apropriada

F

$F$ (sua dimensão

N

$N$ nós em

K

$K$ comunidades) para que o gráfico obtido na saída seja semelhante ao gráfico original. Isso é feito maximizando a função de probabilidade.

l (F) = l o g P (G | F)

$l (F) = log P (G | F)$

E, no entanto, tudo isso pode ser representado como uma decomposição de matriz não negativa, o que apenas fornece uma vantagem na escalabilidade do algoritmo BIGCLAM em comparação com o AGMfit.

Leia mais aqui e aqui .

Numeração e lançamento da comunidade

No BIGCLAM, você pode especificar o número exato de comunidades e o intervalo. O algoritmo seleciona 20% dos pares de nós por teste e 80% é o ajuste do modelo com um número diferente de comunidades.

Formamos um arquivo de entrada com uma lista de arestas e executamos:

./bigclam -o:bloggers -i:query_graph_all.edgelist -c:-1 -nc:20 -mc:50000 -xc:200000 -nt:10

Os parâmetros permitem especificar o número de tentativas, o número mínimo e máximo de comunidades (ou exato, se necessário), o número de encadeamentos para paralelização e o prefixo dos arquivos de saída. No nosso caso, definimos o intervalo de 50 a 200 mil comunidades com 20 tentativas em 10 threads. Todo esse esplendor foi contado em cinco dias na 2 CPU Intel® Xeon® Gold 6150 a 2,70GHz. A saída recebeu dois arquivos, um para Gephi, o segundo texto, no qual cada linha é uma comunidade.

De fato, executamos o algoritmo duas vezes e, pela primeira vez, atingimos o limite superior de 50 mil comunidades, o resultado não foi ruim, mas as comunidades mistas geralmente se deparavam. Dessa vez, atingimos novamente o valor máximo de 200 mil comunidades, mas elas eram muito melhores, e paramos por isso. Você provavelmente poderia obter o resultado ainda melhor, mas duzentas mil comunidades sem nome assustaram nossa imaginação.

Bela imagem

O que fazer agora com tudo isso?

Por um lado, as comunidades resultantes nos ajudam a procurar rapidamente grupos restritos de blogueiros (como os oftalmologistas na época). Se houver alguns blogueiros como exemplo, pegamos todas as comunidades às quais pertencem, descartamos as desnecessárias e é isso. Você pode usar uma pesquisa por nome, por exemplo, em uma das comunidades sobre decoração e design de interiores:

Por outro lado, para determinar os interesses dos usuários, todas essas comunidades devem ser chamadas de alguma forma significativas. Ou talvez nem tudo seja necessário.

CRank

Infelizmente, nem todas as comunidades recebidas são igualmente boas e, para encontrar as mais interessantes, decidimos tentar usar o método de priorização CRank da mesma biblioteca SNAP. Ele foi projetado para corresponder automaticamente à classificação de cada comunidade com base na estrutura do gráfico: quanto maior o valor, melhor a comunidade.

Na entrada do programa, enviamos as comunidades que encontramos anteriormente, para cada uma delas são calculadas as métricas prioritárias (4 peças), depois são agregadas e obtemos uma estimativa.

Marcação manual para coloração e resultados.

Para resolver o problema de colorir os usuários por interesses, também analisamos os textos das postagens e queríamos ver onde o resultado é melhor / mais interessante (em textos ou assinaturas) e se há alguma correspondência. Para uma pequena amostra de pessoas, cerca de 800 comunidades tiveram que ser rotuladas de forma independente. Ficamos mais do que satisfeitos com o resultado e decidimos que essa abordagem deveria ser desenvolvida. O método de detecção da comunidade permite que você encontre categorias de interesse muito estreitas e incomuns, por exemplo, assinando perfis de ratos (no sentido de pequenos roedores cinza) e outras coisas incríveis, você pode descobrir em que tipo de esporte uma pessoa supostamente está interessada e não colocar tudo na categoria "extrema" e assim por diante

Provavelmente não marcaremos todas as 200 mil comunidades, mas talvez brincemos com os resultados do CRank e deixemos apenas comunidades com alta velocidade, e talvez as marcemos como necessárias. Tais coisas :)

Obrigada

Este artigo foi escrito em conjunto com meu supervisor Artyom Korolev ( korolevart ) P&D Dentsu Aegis Network Russia

Fonte