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 Graph Embedding with Triple Context - Leitura de Abstract

  Jun Shi, Huan Gao, Guilin Qi, and Zhangquan Zhou. 2017. Knowledge Graph Embedding with Triple Context. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM '17). Association for Computing Machinery, New York, NY, USA, 2299–2302. https://doi.org/10.1145/3132847.3133119 ABSTRACT Knowledge graph embedding, which aims to represent entities and relations in vector spaces, has shown outstanding performance on a few knowledge graph completion tasks. Most existing methods are based on the assumption that a knowledge graph is a set of separate triples, ignoring rich graph features, i.e., structural information in the graph. In this paper, we take advantages of structures in knowledge graphs, especially local structures around a triple, which we refer to as triple context. We then propose a Triple-Context-based knowledge Embedding model (TCE). For each triple, two kinds of structure information are considered as its context in the graph; one is the out...
Postar um comentário
Leia mais

Exploratory Search: From Finding to Understanding - Leitura de Artigo

Gary Marchionini. 2006. Exploratory search: from finding to understanding. Commun. ACM  49, 4 (April 2006), 41–46. https://doi.org/10.1145/1121949.1121979   This article distinguishes exploratory search that blends quer ying and browsing strategies from retrieval that is best served by analytical strategies ...   Exploratory search. Search is a fundamental life activity.   A hierarchy of information needs may also be defined that ranges from basic facts that guide short-term actions (for example, the predicted chance for rain today to decide whether to bring an umbr ella) to networks of related concepts that help us under stand phenomena or execute complex activities (for example, the relationships between bond prices and stock prices to manage a retirement portfolio) to com plex networks of tacit and explicit knowledge that accretes as expertise over a lifetime (for example, the most promising paths of investigation for the sea soned scholar or designer)....
2 comentários
Leia mais