Como o algoritmo de desdobramento rápido detecta comunidades em grandes redes

Como o algoritmo de desdobramento rápido detecta comunidades em grandes redes

14 de October, 2020 0 By António César de Andrade


A análise de redes sociais envolve o estudo de padrões em grandes redes da vida real que são compostas por milhões de nós. Se você tem um conhecimento básico de teoria dos grafos, você pode realizar essas análises.

O mundo digital abriu uma forma totalmente diferente de criar relacionamentos. Também desencadeou um oceano de dados que podemos analisar para obter uma melhor compreensão do comportamento humano.

Dados de mídia social referem-se a todos os insights brutos e informações coletadas da atividade de mídia social de um indivíduo. Podemos criar redes a partir dessas atividades de mídia social para obter uma melhor percepção desse indivíduo.

Essas redes podem variar amplamente e podem incluir seus amigos do Facebook, os produtos que você comprou recentemente na Amazon, os tweets que você gostou ou retweetou, sua comida favorita que você pediu na Zomato, a pesquisa que você fez no Google ou a imagem que você gostou recentemente no Instagram .

As empresas usam essas redes para classificar seus usuários em diferentes grupos. Isso os ajuda

  • fazer pesquisa de mercado
  • gerar leads
  • melhor servir seus clientes
  • encontrar e compartilhar fotos e vídeos
  • descobrir e discutir o conteúdo de tendência
  • compartilhar informações sobre serviços e restaurantes
  • conectar-se com outras pessoas em torno de um interesse comum ou hobby
  • e mais.

A lista é praticamente interminável.

Antes de entrarmos no assunto, vamos quebrar rapidamente a distinção entre os diferentes componentes de uma rede.

Comunidades em uma rede social

O que é uma rede?

Uma rede é uma teia de relacionamentos pessoais interconectados. Por exemplo, diferentes indivíduos podem se comunicar uns com os outros em um grupo de mídia social por meio de uma rede dinâmica de relacionamentos.

Uma rede é composta por nós (atores individuais, pessoas ou coisas dentro da rede) e o laços, arestas, ou links (relacionamentos ou interações) que os conectam.

O que é um grupo?

Reicher SD em A determinação do comportamento coletivo descreve um grupo como um conjunto de indivíduos que se consideram um grupo. Membros do mesmo grupo têm um conjunto de crenças e comportamentos compartilhados.

De acordo com David W. McMillan (Sentido de Comunidade: Uma Definição e Teoria), a comunidade pode ser definida como o seguinte:

Sentido de Comunidade é um sentimento que os membros têm de pertencer, um sentimento de que os membros são importantes uns para os outros e para o grupo, e uma fé compartilhada de que as necessidades dos membros serão atendidas por meio de seu compromisso de estarem juntos.

Comunidades ou subunidades são as sub-redes em uma rede que são nós altamente interconectados.

A comunidade indica a existência de estruturas internas que possuem características especiais ou desempenham o mesmo papel em uma rede.

Grupos de indivíduos ou objetos altamente conectados dentro dessas redes são comunidades. Geralmente fica no ponto de intersecção da rede e do grupo.

Agora que temos uma ideia clara do que é uma rede, grupo e comunidade, vamos nos aprofundar em como essas redes são divididas em pequenas comunidades.

Vamos olhar para o popular Algoritmo de desdobramento rápido. Vincent C. Blondel e os co-autores do artigo compararam este algoritmo com outros algoritmos de detecção de comunidade. Eles descobriram que esse algoritmo supera todos os outros algoritmos em grandes redes.

O que é o algoritmo de desdobramento rápido?

O Fast Unfolding Algorithm foi usado para identificar comunidades linguísticas em uma rede de telefonia móvel belga de 2,6 milhões de clientes.

Ele também foi usado para analisar um gráfico da web de 118 milhões de nós e mais de um bilhão de links.

Identificar comunidades em uma rede tão grande levou apenas 152 minutos. Portanto, este algoritmo é rápido e eficiente.

Como funciona o algoritmo

O algoritmo funciona em duas fases:

Fase 1

  1. Atribua uma comunidade diferente a cada nó em uma rede.
  2. Então, para cada nó, Eu considera nó j e avalia o ganho em modularidade removendo o nó Eu de sua comunidade e colocá-lo na comunidade de j.
  3. O nodo Eu é colocado na comunidade para a qual ganha modularidade máxima, mas o ganho deve ser positivo. Se o ganho for negativo, o nó Eu permanece na mesma comunidade.

Fase 2

  1. A segunda fase do algoritmo consiste na construção de uma nova rede cujos nós agora são as comunidades encontradas na primeira fase. Portanto, construímos nós mesclando todos os nós da comunidade como um único nó.
  2. Os pesos da ligação entre os nós são dados pela soma dos pesos das ligações entre os nós nas duas comunidades correspondentes.
  3. A ligação entre nós da mesma comunidade leva a auto-laços para a comunidade na nova rede.
  4. Repetir Fase 1 até que nenhuma melhoria adicional possa ser alcançada.

Como o ganho na modularidade é calculado

A Qualidade da Partição (Q) é medido pelo Modularidade (também conhecido como modularidade de partição). É um valor escalar entre -1 e 1 e mede a densidade dos links dentro das comunidades em comparação com os links entre as comunidades.

o Ganho na Modularidade (∆Q) obtido movendo um nó isolado Eu em uma comunidade C pode ser facilmente calculado por:

Σin é a soma dos pesos dos links dentro de C.

Σtot é a soma dos pesos dos links incidentes aos nós em C.

ki é a soma dos pesos dos links de Eu para o nó em C.

m é a soma dos pesos de todos os links da rede.

O ganho na modularidade é avaliado removendo Eu de sua comunidade e, em seguida, movê-lo para uma comunidade vizinha. Se o ganho for positivo, esse nó é colocado na comunidade vizinha.

Trabalho de algoritmo de desdobramento rápido

Teste do algoritmo

Na rede à esquerda (15 nós), primeiro atribuímos uma comunidade única para cada nó. Em seguida, avaliamos a modularidade de cada nó e reatribuímos a comunidade com base no ganho. Isso é chamado Otimização de Modularidade.

Na próxima fase, construímos nós mesclando todos os nós dessa comunidade em um único nó. Na comunidade verde, temos um total de 5 nós e um total de 7 arestas entre eles.

Então depois Agregação da Comunidade, o peso do loop automático do nó verde será 14 (7 * 2, pois é um link bidirecional). Da mesma forma, o peso do self-loop do nó vermelho será 16, o nó azul será 4 e o nó azul claro será 2.

O peso da aresta entre o nó verde e azul será 4, pois há um total de 4 arestas entre a comunidade verde e azul após a Otimização da Modularidade.

Na próxima etapa, reavaliamos a modularidade para os novos nós e fazemos o mesmo processo novamente.

Finalmente, temos duas comunidades, Verde e Azul claro. A comunidade verde tem 26 self-loops, pois há um total de 13 arestas entre os nós da comunidade verde. E temos 12 arestas na comunidade azul claro, um total de 24 auto-loops.

Detecção de comunidade na rede

Vantagens do algoritmo

  1. Suas etapas são intuitivas e fáceis de implementar e o resultado não é supervisionado.
  2. O algoritmo é extremamente rápido. Simulações de computador em redes modulares muito grandes sugerem que sua complexidade é linear nos dados típicos e esparsos. Isso pode ser porque o ganho na modularidade é fácil de calcular e o número de comunidades diminui drasticamente depois de apenas algumas passagens.

Limitações do algoritmo

  1. A otimização da modularidade falha em identificar comunidades menores do que uma determinada escala. Portanto, isso causa um limite de resolução na comunidade calculada usando uma abordagem de otimização de modularidade pura.
  2. Para redes pequenas, a probabilidade de que duas comunidades separadas possam ser unidas movendo cada nó é muito baixa.

Conclusão

Se você aguentou todo esse tempo … obrigado! Espero que tenha havido informações valiosas para você.

Agora você sabe como funciona o algoritmo de desdobramento rápido e que ele é extremamente eficiente para detectar comunidades em redes muito grandes.

A maneira como ele calcula o ganho na modularidade faz com que o algoritmo supere todos os outros algoritmos existentes. Deixe-me um recado se achar útil ou se tiver alguma dúvida.

Obrigado por ler!



Fonte

Click to rate this post!
[Total: 0 Average: 0]