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

Aula 12: WordNet | Introdução à Linguagem de Programação Python *** com NLTK

 Fonte -> https://youtu.be/0OCq31jQ9E4 A WordNet do Brasil -> http://www.nilc.icmc.usp.br/wordnetbr/ NLTK  synsets = dada uma palavra acha todos os significados, pode informar a língua e a classe gramatical da palavra (substantivo, verbo, advérbio) from nltk.corpus import wordnet as wn wordnet.synset(xxxxxx).definition() = descrição do significado É possível extrair hipernimia, hiponimia, antonimos e os lemas (diferentes palavras/expressões com o mesmo significado) formando uma REDE LEXICAL. Com isso é possível calcular a distância entre 2 synset dentro do grafo.  Veja trecho de código abaixo: texto = 'útil' print('NOUN:', wordnet.synsets(texto, lang='por', pos=wordnet.NOUN)) texto = 'útil' print('ADJ:', wordnet.synsets(texto, lang='por', pos=wordnet.ADJ)) print(wordnet.synset('handy.s.01').definition()) texto = 'computador' for synset in wn.synsets(texto, lang='por', pos=wn.NOUN):     print('DEF:',s...
2 comentários
Leia mais

truth makers AND truth bearers - Palestra Giancarlo no SBBD

Dando uma googada https://iep.utm.edu/truth/ There are two commonly accepted constraints on truth and falsehood:     Every proposition is true or false.         [Law of the Excluded Middle.]     No proposition is both true and false.         [Law of Non-contradiction.] What is the difference between a truth-maker and a truth bearer? Truth-bearers are either true or false; truth-makers are not since, not being representations, they cannot be said to be true, nor can they be said to be false . That's a second difference. Truth-bearers are 'bipolar,' either true or false; truth-makers are 'unipolar': all of them obtain. What are considered truth bearers?   A variety of truth bearers are considered – statements, beliefs, claims, assumptions, hypotheses, propositions, sentences, and utterances . When I speak of a fact . . . I mean the kind of thing that makes a proposition true or false. (Russe...
1 comentário
Leia mais

DGL-KE : Deep Graph Library (DGL)

Fonte: https://towardsdatascience.com/introduction-to-knowledge-graph-embedding-with-dgl-ke-77ace6fb60ef Amazon recently launched DGL-KE, a software package that simplifies this process with simple command-line scripts. With DGL-KE , users can generate embeddings for very large graphs 2–5x faster than competing techniques. DGL-KE provides users the flexibility to select models used to generate embeddings and optimize performance by configuring hardware, data sampling parameters, and the loss function. To use this package effectively, however, it is important to understand how embeddings work and the optimizations available to compute them. This two-part blog series is designed to provide this information and get you ready to start taking advantage of DGL-KE . Finally, another class of graphs that is especially important for knowledge graphs are multigraphs . These are graphs that can have multiple (directed) edges between the same pair of nodes and can also contain loops. The...
Postar um comentário
Leia mais