Canal de Vídeos -> https://www.youtube.com/c/LNCCbr/videos
Descrição: [MC-CD01] Ciências de Redes
Professor : Artur Ziviani (LNCC)
Dias e Horários: 01 a 04/02 de 09:00h às 10:30h
Anotações de aula
Ciências de Rede estuda como as coisas são conectadas, as redes reais são representadas matematicamente por um grafo.
Estudo de co-autoria para cooperação interdisciplinares, pode levar até a sugestão de novas cooperações.
Rede define as interações entre os componentes de sistemas complexos.
Leonard Euler, Teoria dos Grafos: Euler demonstrou que pontos com números ímpares de vértices, ou locais com um número ímpar de pontes no mapa, só podem ser o ponto de saída ou de entrada de um grafo. E os quatro locais (as margens e as ilhas) de Konigsberg tinham pontes ímpares.
Vídeo do Nerdologia-> https://youtu.be/YMI3CrChwSk
Fontes:Livro citado no episódio Linked - A nova ciência dos networks de Albert-László Barabási:
http://bit.ly/1j3gErO
Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512. [pdf] http://bit.ly/1jDPUiv
Pastor-Satorras, Romualdo, and Alessandro Vespignani. "Epidemic spreading in scale-free networks." Physical review letters 86, no. 14 (2001): 3200: http://bit.ly/1mCeqAj
Newman, Mark EJ. "Properties of highly clustered networks." Physical Review E 68, no. 2 (2003): 026121:
http://bit.ly/QHJ3uf
Backstrom, Lars, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. "Four degrees of separation." In Proceedings of the 3rd Annual ACM Web Science Conference, pp. 33-42. ACM, 2012: http://bit.ly/1jDPZ5A
Hubs nós extremamente conectados. Quanto mais conectada a rede mais a informação flui.
Detectar comunidades com interesse comuns para sistemas de recomendação.
Barabási, um húngaro radicado nos EUA, autor do livro Network Science.
Processo de inferência de grafos é orientado a dados.
Contribuição computacional em Ciência de Dados: melhoria de algoritmos de análises de dados.
Disciplina GA-054 Ciência de Redes da pós graduação do LNCC. Previsão 3º trimestre (Junho-Setembro 2021) e aceita ouvinte externo.
Ferramentas: NetworkX (python) e iGraph - análise & Gephy (visualização)
Diâmetro da rede, média dos caminhos mínimos
Conectividade: para todo nó x e y, existe um caminho P que liga x a y
Ponte: aresta que se removida torna o grafo desconexo, avalia a robustez do grafo.
Probabilidade de conexão de dois vértices
Fenômeno da percolação !?
The removal of a single node has only limited impact on a network’s integrity. The removal of several nodes, however, can break a network into several isolated components. Obviously, the more nodes we remove, the higher are the chances that we damage a network, prompting us to ask: How many nodes do we have to delete to fragment a network into isolated components? For example, what fraction of Internet routers must break down so that the Internet turns into clusters of computers that are unable to communicate with each other? To answer these questions, we must first familiarize ourselves with the mathematical underpinnings of network robustness, offered by percolation theory.
Grafo fortemente conectado é um grafo direcionado tal que existe uma caminho que liga x e y assim como existe caminho que liga y a x
Componentes fortemente conectados
Existem propostas de aproximação para o cálculo de caminho mínimo pq essa é uma operação custosa para redes muito grandes
Medida de de representação de triângulos: clusterização ou transitividade
Clique: subgrafo completo, ou seja, todos os vértices são ligados entre si
Métrica local, para cada vértice, é o número de arestas entre vizinhos
Métrica global, para o grafo todo, número de cliques de tamanho 3
Triplas centradas em cada nó
Teorema de Euler: se um grafo é conectado e não tem vértices com grau ímpar então existe caminho mas se um grafo tem mais de 2 vértices com grau ímpar então não existe caminho
Ao definir uma regra de representação (modelo) é possível influenciar o grafo e a pergunta a ser respondida com ele.
Exemplos de grafos não direcionados: amigos em redes sociais, co-autoria, interações entre proteínas
Exemplos de grafos direcionados: seguidores em redes sociais, URLs na Web, reações metabólicas
Grau de um nó não direcionado: número de arestas
Grau de um nó direcionado: número de arestas de entrada, de saída. Vértice fonte (entrada = 0) e Sorvedor (saída = 0)
Grafo Completo: todos os nós se ligam a todos os nós
Outros modelos de grafos foram definidos considerando a distribuição dos graus (frequência relativa dos graus) ao invés de média
Grafos Aleatórios: seguem uma distribuição binominal/poison dos graus, o gráfico que representa a distribuição dos graus é um sino
Grafos Scale-Free: seguem uma distribuição power-law, , o gráfico que representa a distribuição dos graus é cauda longa
O pior/maior caminho mínimo ou a média dos caminhos mínimos definem o diâmetro da rede
Centralidade de autovetor, soma das centralidades de seus vizinhos
Algoritmo PageRank da Google para grafos direcionados, se A -> B e o vértice A é importante então B recebe mais pontos, atualmente tem mais critérios
Closeness (proximidade): nó mais próximos de qq outro nó, depende do cálculo do caminho mínimo entre todos os nós
Betweenness (melhor intermediador): é o nó pelo qual o maior número de caminho mínimos passe, depende do cálculo do caminho mínimo entre todos os nós
Se o grafo não conectado então as métricas devem ser calculadas dentro do componente fortemente conectado
Modelos de Grafos para Redes Estáticas
1) G(n,p) onde n é o número de vértices e p a probabilidade de existir uma aresta entre eles (essa probabilidade é igual para todos)
Se p=0 não tem arestas, se p=1 é um grafo completo (todos os nós são conectados entre si)
O valor de p=]0,1[ faz a rede variar de esparsa a densa
C (coeficiente de clusterização) é igual a p
L (diâmetro da rede) aumenta em proporção a n
Nesse modelo o L se aproxima do L das redes reais mas o cálculo do C falha em redes reais
2) Small World: premissa de que empiricamente as redes reais tendem a ter pequeno L e grande C
Parte de uma rede circular ordenada (cada nó está ligado a K vértices vizinhos)
Se p=0 a rede inicial não se altera pq não há troca de arestas, se p=1 a rede se torna uma rede aleatória pq há troca em todas as arestas
Com p=0 a clusterização (C) é alta mas o diâmetro (L) é pequeno
Com p=]0,1[ forma-se uma rede Small-World
3) Scale-Free: poucos vértices com muitas conexões e muitos vértices com poucas conexões
Lei de Potência (cauda longa), o "gama" é o fator de crescimento/inclinação da curva, quanto maior a inclinação maior a diferença
A escolha dos nós para conexão é proporcional ao grau que já possuem assim a tendência é de concentração das conexão nesses nós (aristocráticas na distribuição do grau)
Redes assortativas: tendência a conexão entre vértices similares
Livro NETWORK SCIENCE Barabási, Albert-László e NETWORK, CLOUDS, MARKETS Kleinberg
Revista IEEE Transaction on Network Science and Engineering
Ciência de Dados: cientistas de dados precisam de um pouco de conhecimento do domínio, qualidade de dados para permitir melhores análises
Pesquisa Básica: o problema pode ser encontrado em um cenário de aplicação, modelar o problema em um nível de abstração mais alto (com menos detalhes) de modo a generalizar a solução e permitir a aplicação em outros cenários
Pesquisa Aplicada: uma proposta é testada em um cenário de aplicação
Problemas de pesquisa: Seeding problem (muitos nós baratos, poucos nós caros, onde investir de modo a disseminar por toda rede? nós de custos variados mas quais?), Redes dinâmicas: grafos variantes no tempo - TVG, grafos complexos em camadas (o tempo pode ser uma camada como snapshots), grafo multi aspectos, como calcular o caminho em redes dinâmicas no tempo?, redes semânticas (BD -> KB), gêmeos digitais
1 -> 2 t1 1 -> 2 t1
3 -> 4 t2 Não existe caminho 1 .. 4 2 -> 3 t2 Existe caminho 1 .. 4 = t1, t2, t3
2 -> 3 t3 3 -> 4 t3
Gypscie (Petrobrás)
Comentários
Postar um comentário
Sinta-se a vontade para comentar. Críticas construtivas são sempre bem vindas.