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

Knowledge Graphs as a source of trust for LLM-powered enterprise question answering - Leitura de Artigo

J. Sequeda, D. Allemang and B. Jacob, Knowledge Graphs as a source of trust for LLM-powered enterprise question answering, Web Semantics: Science, Services and Agents on the World Wide Web (2025), doi: https://doi.org/10.1016/j.websem.2024.100858. 1. Introduction These question answering systems that enable to chat with your structured data hold tremendous potential for transforming the way self service and data-driven decision making is executed within enterprises. Self service and data-driven decision making in organizations today is largly made through Business Intelligence (BI) and analytics reporting. Data teams gather the original data, integrate the data, build a SQL data warehouse (i.e. star schemas), and create BI dashboards and reports that are then used by business users and analysts to answer specific questions (i.e. metrics, KPIs) and make decisions. The bottleneck of this approach is that business users are only able to answer questions given the views of existing dashboa...
Postar um comentário
Leia mais

Knowledge Graph Toolkit (KGTK)

https://kgtk.readthedocs.io/en/latest/ KGTK represents KGs using TSV files with 4 columns labeled id, node1, label and node2. The id column is a symbol representing an identifier of an edge, corresponding to the orange circles in the diagram above. node1 represents the source of the edge, node2 represents the destination of the edge, and label represents the relation between node1 and node2. >> Quad do RDF, definir cada tripla como um grafo   KGTK defines knowledge graphs (or more generally any attributed graph or hypergraph ) as a set of nodes and a set of edges between those nodes. KGTK represents everything of meaning via an edge. Edges themselves can be attributed by having edges asserted about them, thus, KGTK can in fact represent arbitrary hypergraphs. KGTK intentionally does not distinguish attributes or qualifiers on nodes and edges from full-fledged edges, tools operating on KGTK graphs can instead interpret edges differently if they so desire. In KGTK, e...
1 comentário
Leia mais