Algoritmos para Grafos | Índice
Este sítio trata de algoritmos eficientes para resolver certos problemas básicos sobre grafos. Se os grafos a processar fossem sempre pequenos, a preocupação com a eficiência dos algoritmos seria supérflua. Ocorre que em muitas aplicações os grafos são gigantescos, com milhares e até milhões de vértices. (A propósito, veja o projeto The Colorado Index of Complex Networks (ICON), coordenado por Aaron Clauset.)
Este capítulo exibe figuras de alguns grafos grandes. Algumas das figuras foram copiadas (sem autorização…) do livro Algorithms, 4th ed. de Sedgewick e Wayne. Outras foram garimpadas, sem muito critério, na Web.
Mas as figuras de grafos grandes têm utilidade muito limitada. Para um grafo com mais de algumas dezenas de vértices, a figura não ajuda a entender a estrutura do grafo e a responder perguntas sobre o grafo…
Cubo de dimensão n. Um cubo de dimensão n é definido assim: os vértices são 0 1 2 … 2n−1 e dois vértices v e w são adjacentes se e somente se as expansões binárias dos números v e w diferem em exatamente um bit. A figura (copiada de https://en.wikipedia.org/wiki/Hypercube) mostra um cubo de dimensão 4.
Grade dirigida aleatória. (Copiada dos slides de Algorithms, 4th ed., de Sedgewick e Wayne.)
Labirinto. Sub&Shy;Grafo de uma grade não-dirigida aleatória. (Copiado dos slides de Sedgewick, 2005.)
Árvore geradora.
Uma árvore geradora de um grafo não-dirigido geométrico
aleatório.
(Copiado de http://mathematica.stackexchange.com/questions/11962/how-to-generate-random-directed-connected-graph.)
Grafo aleatório geométrico.
Os vértices são pontos no plano
e os arco ligam pontos próximos
.
(Copiado de
How to generate random directed connected graph?
na página Mathematica Stack Exchange,
http://mathematica.stackexchange.com/questions/11962/how-to-generate-random-directed-connected-graph.)
Grafo não-dirigido aleatório com 1000 vértices.
Os vértices são pontos
no quadrado [0,1)×[0,1)
e as arestas ligam vértices próximos
.
(Copiado de
How to generate random directed connected graph?
na página Mathematica Stack Exchange,
http://mathematica.stackexchange.com/questions/11962/how-to-generate-random-directed-connected-graph.)
Grafo não-dirigido aleatório com 400 vértices no quadrado [0,1)×[0,1). As arestas foram inseridas aleatoriamente e o número de arestas foi escolhido grande o suficiente para garantir que o grafo resulte conexo. (Copiado da Random Gallery de Nicolas Broutin https://who.rocq.inria.fr/Nicolas.Broutin/gallery.html.)
Grafo não-dirigido aleatório.
Esta é uma versão esparsificada
do grafo anterior
(o grafo continua conexo).
Blogosfera.
A figura seguinte representa o grafo do núcleo
da blogosfera
(em 2006?).
Os vértices são blogs.
As linhas claras são arcos:
v-w significa que
v citou w
(as direções dos arcos não foram indicadas).
As linhas escuras são pares de arcos antiparalelos:
v-w significa que
v citou w e vice-versa.
(Copiado de DataMining: Mapping the Blogosphere
em http://datamining.typepad.com/gallery/blog-map-gallery.html.)
Blogosfera. Uma variante da figura anterior em que as cores dos vértices codificam informações adicionais.
Cytoscape. Não sei o que esse grafo representa. (Copiado de Cytoscape App Store - Randomnetworks http://apps.cytoscape.org/apps/randomnetworks.)
Synthetic Daisies. Não sei o que esse grafo representa. (Copiado de Synthetic Daisies: 12.13 http://syntheticdaisies.blogspot.com.br/2013_12_01_archive.html.)
Rede social.
Grafo (não-dirigido) das conexões de um usuário do Facebook.
Os vértices são usuários do Facebook e as arestas são relações de amizade.
Parece que a figura foi desenhada de modo
que a distância geométrica entre dois vértices seja inversamente proporcional
ao número de amigos que os dois vértices têm em comum.
Dessa forma é possível ver clusters
de amizades,
como os amigos do trabalho, os familiares, etc.
(Contribuição de Ricardo Lira da Fonseca.)
Rede social. Social_Network_Analysis_Visualization.png
Email. Ligações de email entre funcionários de uma corporação (figura do livro de Easley e Kleinberg):
Namoro.
Relações de namoro entre alunos de uma escola
ao longo de alguns anos
(figura do livro de Easley e Kleinberg,
copiada do artigo
High School Dating
de Bearman, Moody, and Stovel, 2004).
Lembra Carlos Drummond de Andrade:
João amava Teresa que amava Raimundo
que amava Maria que amava Joaquim que amava Lili …
Triangulação de um disco. Copiado de http://www.eurecom.fr/~spyropou/NetMod%202013/Lecture%2010.ppt.
Componentes conexas. Esta figura usa uma cor diferente para cada componentes conexa de um grafo não-dirigido. (Copiado de Informations- und Netzwerksicherheit: Ein Überblick, http://www.eurecom.fr/~spyropou/NetMod%202013/Lecture%2010.pptx.)
Quase árvore. Não sei o que esse grafo representa. (Copiado de http://siliconangle.com/blog/2015/02/03/datastax-buys-titandb-developer-enters-red-hot-graph-database-market/.)
Biologia molecular.
Um grafo não-dirigido da biologia molecular:
um montagem de motifs comuns de Escherichia coli.
O grafo-base
aparece no canto superior direito.
(Copiado de
Dynamics and processing in finite self-similar networks
de Simon DeDeo e David C. Krakauer,
http://rsif.royalsocietypublishing.org/content/9/74/2131.)
Python networkx. Não sei qual o significado desse grafo. (Copiado de stackoverflow.com/questions/28910766/python-networkx-set-node-color-automatically-based-on-number-of-attribute-opt.)
Akilleenkanta. Não sei qual o significado desse grafo. (Copiado de akilleenkanta.blogspot.com.br/2014_08_01_archive.html.)
SDLRG. Não sei qual o significado desse grafo. (Copiado de Stochastic dynamics on large random graphs, 2014, https://math.aalto.fi/~lleskela/SDLRG/.)
Balanced. Não sei qual o significado desse grafo. (Copiado de www.yger.net/the-balanced-network/.)
Cybergeography. Não sei qual o significado desse grafo. (Copiado de www.cybergeography-fr.org/atlas/more_topology.php.)
?Pharyngula. Não sei qual o significado desse grafo. Parece uma árvore… (Copiado de scienceblogs.com/pharyngula/2006/05/27/graphing-pharyngula/.)
Cytonca. Não sei qual o significado desse grafo. (Copiado de apps.cytoscape.org/apps/cytonca.)
Large graph. Não sei qual o significado desse grafo. (Copiado de www.hpcwire.com/2013/11/16/sc13-research-highlight-large-graph-processing-without-overhead/.)
Pointeight. Não sei qual o significado desse grafo. (Copiado de www.jonathanjordan.staff.shef.ac.uk/research.html.)
Toroidal. Uma malha de polígonos na superfície de um toro:
Flight patterns (by Aaron Koblin). Flight paths from FAA data drawn algorithmically and colored based on airplane model:
Visualizing Friendships
(by Paul Butler).
…
a visualization that would show which cities
had a lot of friendships between them.
I began by taking a sample of about ten million pairs of friends
from Apache Hive, our data warehouse.
I combined that data with each user's current city
and summed the number of friends between each pair of cities.
Then I merged the data with the longitude and latitude of each city
: