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

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

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

Knowledge graphs: Introduction, history, and perspectives - Leitura de Artigo

Chaudhri, V. K., C. Baru, N. Chittar, X. L. Dong, M. Genesereth, J. Hendler, A. Kalyanpur, D. Lenat, J. Sequeda, D. Vrandečić, and K.Wang 2022. “ Knowledge graphs: Introduction, history, and perspectives. ” AI Magazine 43: 17–29. https://doi.org/10.1002/aaai.12033 Knowledge graphs (KGs) have emerged as a compelling abstraction for organizing the world’s structured knowledge and for integrating information extracted from multiple data sources. KNOWLEDGE GRAPH DEFINITION A KG is a directed labeled graph in which domain-specific meanings are associated with nodes and edges. [ Definição focado no COMO representar, diferente dos KBs ] There are multiple approaches for associating meanings with the nodes and edges. At the simplest level, the meanings could be stated as documentation strings expressed in a human understandable language such as English. At a computational level, the meanings can be expressed in a formal specification language such as first-order logic. An active area of curren...
Postar um comentário
Leia mais