Pular para o conteúdo principal

Mining social network graphs - Livro Mining Massive Datasets do J. Ullman

 Apresentação da disciplina de Big Data do Casanova - grupo sobre Grafos

Clusterização dos nós do grafo para identificação de comunidades, técnicas de clusterização tradicional não são adequadas.

Grafos de redes sociais tem um conjunto de entidades com um ou mais tipos (Pessoas, Organizações) que formam os nós e relações entre os nós que podem ser direcionais (A segue B) ou bidirecionais (A é amigo de B e B é amigo de A) e rotuladas que formam os arcos (ou arestas). Os k tipos de nós podem formar k conjuntos disjuntos em um grafo k-partido. 

A formação de comunidades pode se dar por nós do mesmo tipo que compartilham Interesses Comuns (curtiram ou seguem a mesma página, amigos em comum, etc ...). Em caso de grafos de redes de Colaboração Científica as comunidades podem ser formadas por Autores que publicam artigos de um tópico em particular ou por Publicações sobre um tópico em particular.

Medidas de similaridade são necessárias para identificação de clusters.

Algoritmo de Girvan-Newman

    Repetir até não haver mais arcos:
        Calcula betweenness dos arcos (usando BFS)
        Remove arcos com maior betweenness

Outras abordagens: contagem de cliques (qualquer subgrafo completo, ou seja, com nós totalmente conectados) e Grafo Bipartido Completo (grandes itemsets frequentes). Cliques são úteis para achar comunidades pequenas (o q seria pequeno?)

Simrank para similaridade entre nós, principalmente em grafos com diferentes tipos de nós.

Contagem de triângulos (cliques de tamanho 3)

Particionamento de Grafos: minimizar o número de arestas que conectam componentes diferentes (bom corte). 

Matriz Laplaciana L = Matriz de Grau D - Matriz de Adjacência A

Comunidades raramente são disjuntas. 

Slides do capítulo 10 do Livro 

http://www.mmds.org/mmds/v2.1/ch10-graphs1.pdf

http://www.mmds.org/mmds/v2.1/ch10-graphs2.pdf

Livro completo online http://infolab.stanford.edu/~ullman/mmds/book.pdf

Vídeo inicial da série https://youtu.be/MiKecKWbJhM

Site para linkar todo o material do livro e curso de Standford http://www.mmds.org/

Marcadores:

Comentários

Postar um comentário

Sinta-se a vontade para comentar. Críticas construtivas são sempre bem vindas.

Postagens mais visitadas deste blog

Connected Papers: Uma abordagem alternativa para revisão da literatura

Durante um projeto de pesquisa podemos encontrar um artigo que nos identificamos em termos de problema de pesquisa e também de solução. Então surge a vontade de saber como essa área de pesquisa se desenvolveu até chegar a esse ponto ou quais desdobramentos ocorreram a partir dessa solução proposta para identificar o estado da arte nesse tema. Podemos seguir duas abordagens:  realizar uma revisão sistemática usando palavras chaves que melhor caracterizam o tema em bibliotecas digitais de referência para encontrar artigos relacionados ou realizar snowballing ancorado nesse artigo que identificamos previamente, explorando os artigos citados (backward) ou os artigos que o citam (forward)  Mas a ferramenta Connected Papers propõe uma abordagem alternativa para essa busca. O problema inicial é dado um artigo de interesse, precisamos encontrar outros artigos relacionados de "certa forma". Find different methods and approaches to the same subject Track down the state of the art rese...
3 comentários
Leia mais

KnOD 2021

Beyond Facts: Online Discourse and Knowledge Graphs A preface to the proceedings of the 1st International Workshop on Knowledge Graphs for Online Discourse Analysis (KnOD 2021, co-located with TheWebConf’21) https://ceur-ws.org/Vol-2877/preface.pdf https://knod2021.wordpress.com/   ABSTRACT Expressing opinions and interacting with others on the Web has led to the production of an abundance of online discourse data, such as claims and viewpoints on controversial topics, their sources and contexts . This data constitutes a valuable source of insights for studies into misinformation spread, bias reinforcement, echo chambers or political agenda setting. While knowledge graphs promise to provide the key to a Web of structured information, they are mainly focused on facts without keeping track of the diversity, connection or temporal evolution of online discourse data. As opposed to facts, claims are inherently more complex. Their interpretation strongly depends on the context and a vari...
2 comentários
Leia mais

Aprendizado de Máquina Relacional

 Extraído de -> https://www.lncc.br/~ziviani/papers/Texto-MC1-SBBD2019.pdf   Aprendizado de máquina relacional (AMR) destina-se à criação de modelos estatísticos para dados relacionais (seria o mesmo que dados conectados) , isto é, dados cuja a informação relacional é tão ou mais impor tante que a informação individual (atributos) de cada elemento.    Essa classe de aprendizado tem sido utilizada em diversas aplicações, por exemplo, na extração de informação de dados não estruturados [Zhang et al. 2016] e na modelagem de linguagem natural [Vu et al. 2018].   A adoção de técnicas de aprendizado de máquina relacional em tarefas de comple mentação de grafo de conhecimento se baseia na premissa de existência de regularidades semânticas presentes no mesmo . Modelos grafos probabilísticos  Baseada em regras / heurísticas que não podem garantir 100% de precisão no resultado da inferência mas os resultados podem ser explicados. Modelos de características de ...
Postar um comentário
Leia mais