Pular para o conteúdo principal

Festival do Conhecimento - UFRJ - Ciência das Redes x Teoria dos Grafos: Uma Nova Esperança


Data 24/07 - 17h

Ciência das Redes x Teoria dos Grafos: Uma Nova Esperança

Link https://youtu.be/3I8_vHKt9T8

Professores Daniel Ratton Figueiredo, Fábio Botler (COPPE / PESC)

Teoria de Grafos (TG) e Problemas Combinatórios

A TG começou com jogos e passatempos como um ferramental matemático fazem 200 anos (século XVIII). Em 1878 o termo grafo foi citado pela primeira vez em um artigo da Nature sobre um estudo da área de química (detecção de isômeros de cadeias de carbono, ou seja, identificar se dois grafos são isomorfos)

Grafo é uma abstração (modelagem) para muitas aplicações, tem estreita relação com teoria da computação e é um estudo de combinatória com estrutura. São problemas em sua maioria NP-Difíceis para tratar questões como Decomposição de grafos (identificar estruturas indivisíveis), Circuitos Hamiltonianos* (caixeiro viajante) e Coloração de Grafos.

* Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano em G.

Decomposição de grafos quer identificar o quão conexo é um grafo. Quantas arestas precisam ser deletadas para tornar um grafo desconexo.
Orientações de Grafos: 2 elevado a m (arestas) de possibilidades
Coloração de arestas quer identificar como "colorir" as arestas de modo que cada vértice seja "tocado" por no máximo uma aresta de cada cor.

A Ciência de Redes está contida na Ciência de Dados e é uma ciência nova que começou com aplicações da Internet (a Web e a própria estrutura da rede) no final dos anos 90 e faz uso de teoria matemática. A Ciência de Redes procura: (1) identificar qual é a estrutura de uma rede real; (2) o motivo pelo qual a rede apresenta tal estrutura e (3) quais as consequências de tal estruturas se comportarem de tal forma. Muitos problemas se desenvolvem a partir de dados de redes sociais como seguidores no Twitter, comunidades no Facebook, Tracking e trajetos, etc ...

Alguns artigos

- stru2vec: metodologia para representar vértices em uma rede em um espaço euclidiano (2D) para treinamento em algoritmos de ML

Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Daniel R. Figueiredo. 2017. Struc2vec: Learning Node Representations from Structural Identity. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’17). Association for Computing Machinery, New York, NY, USA, 385–394. DOI:https://doi.org/10.1145/3097983.3098061

- identificar ambiguidades (fazer entity linkage entre vértices) em redes sociais para promover a consolidação sem usar atributos como o nome (label), usar somente a estrutura é possível pela forma como o ser humano constrói colaborações

KLING, H. ; GOMIDE, J. ; FIGUEIREDO, D. R. . A simple label-free algorithm for removing ambiguities in collaboration networks. In: NetSci-x, 2015, Rio de Janeiro. International School and Conference on Network Science, 2015.

- coautoria de leis de deputados para identificar homofilia** e assimetria, deputados são vértices e cada lei com coautoria é um vértice

** homofilia pode ser caracterizada como a maior predisposição dos indivíduos de formarem relações baseados na similaridade entre suas características. Por exemplo, indivíduos que frequentaram a mesma universidade tem mais chance de serem amigos no Facebook. Nesse contexto, quanto maior a homofilia maior é a preferência de um indivíduo de se relacionar com seus semelhantes em detrimento a outros indivíduos com características distintas.

ROLIM, Lucas; FIGUEIREDO, Daniel R.. Homofilia e Assimetria na Rede de Coautoria de Proposições de Lei do Congresso Brasileiro. In: BRAZILIAN WORKSHOP ON SOCIAL NETWORK ANALYSIS AND MINING (BRASNAM), 8. , 2019, Belém. Anais do VIII Brazilian Workshop on Social Network Analysis and Mining. Porto Alegre: Sociedade Brasileira de Computação, july 2019 . p. 12-23. ISSN 2595-6094. DOI: https://doi.org/10.5753/brasnam.2019.6544.

- epidemia em redes (não achei no Lattes)

98/99 foi o Big Bang em Ciência de Redes. Artigos de grande impacto e citação na Nature e Science

Barabasi AL, Albert R. Emergence of scaling in random networks. Science. 1999;286(5439):509-512. doi:10.1126/science.286.5439.509

Science em 2009 fez uma publicação de comemoração.

O termo grafo é muito usado em Computação, em outras áreas é mais comum usar o termo redes. Grafos são construções / modelos abstratos e redes são mais próximas da compreensão do mundo real. Os problemas de Redes nascem do mundo real enquanto que a TG resolve problemas que podem AINDA não ter aplicação prática.

Isomorfismo*** é um problema que tem grande interesse das duas áreas e aplicação em vários domínios.

*** Um isomorfismo entre dois grafos G e H é uma bijeção f de V (G) em V (H) tal que dois vértices v e w são adjacentes em G se e somente se f(v) e f(w) são adjacentes em H. Dois grafos G e H são isomorfos se existe um isomorfismo entre eles. Em outras palavras, dois grafos são isomorfos se é possível alterar os nomes dos vértices de um deles de tal modo que os dois grafos fiquem iguais. Para decidir se dois grafos G e H são isomorfos, basta examinar todas as bijeções de V (G) em V (H). Se cada um dos grafos tem n vértices, esse algoritmo consome tempo proporcional a n!. Como n! cresce explosivamente com n, esse algoritmo é decididamente insatisfatório na prática. Infelizmente, não se conhece um algoritmo substancialmente melhor.

Detecção de comunidades é um problema que Redes tem grande interesse e depende de TG para realizar a bisseção do grafo, ou seja, particionar os vértices de modo que tenham mais arestas intra-grupos do que entre grupos.

Outra questão de Redes que dependem de Teoria de Grafos é explicar os padrões observáveis em redes reais que a Natureza e o Homem constroem é um desafio também.

A Ciência pode vir antes da Teoria, como produção e organização do conhecimento baseada em evidência empírica, ou vice-versa, a teoria fornece uma abstração formal para explicar e prever a Ciência baseada em lógica matemática.

Comentários

  1. Como o tema de pesquisa ficou fechado em NoSQL Graph Stores vou continuar prospectando um problema de pesquisa nessa área de grafos. O curso de Verão 2021 do LNCC tem um mini curso sobre Ciência de Redes que já me inscrevi e pretendo fazer esse ano, finalmente!

    ResponderExcluir

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...

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...

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...