Algoritmos para Grafos  |  Índice

Grafos grandes

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…

Figuras

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.

160px-4-cube_graph.svg.png

Grade dirigida aleatória.  (Copiada dos slides de Algorithms, 4th ed., de Sedgewick e Wayne.)

directed-grid.png

Labirinto.  Sub&Shy;Grafo de uma grade não-dirigida aleatória.  (Copiado dos slides de Sedgewick, 2005.)

find path between two vertices in undirected grid

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

figs/large-graphs/hQteD.png

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

figs/large-graphs/6CM0T.png

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

figs/large-graphs/0CXp2.png
figs/large-graphs/rgg2.png

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

figs/large-graphs/geometric_graph.png

Grafo não-dirigido aleatório.  Esta é uma versão esparsificada do grafo anterior (o grafo continua conexo).

figs/large-graphs/irrigation_graph.png

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

figs/large-graphs/blogosphere-sketch.png

Blogosfera.  Uma variante da figura anterior em que as cores dos vértices codificam informações adicionais.

figs/large-graphs/core.png

Cytoscape.  Não sei o que esse grafo representa.  (Copiado de Cytoscape App Store - Randomnetworks http://apps.cytoscape.org/apps/randomnetworks.)

figs/large-graphs/Screen_shot_2012-05-06_at_5.35.57_PM.png

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

figs/large-graphs/hairball-science.png

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

figs/large-graphs/facebook_social_graph.jpg

Rede social.  Social_Network_Analysis_Visualization.png

figs/large-graphs/Social_Network_Analysis_Visualization.png

Email.  Ligações de email entre funcionários de uma corporação (figura do livro de Easley e Kleinberg):

figs/large-graphs/kleinberg-easley-corporate-communication-adamic-hier.jpg

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 …

figs/large-graphs/kleinberg-and-easley-high-school-dating-addhealth.gif

Triangulação de um disco.  Copiado de http://www.eurecom.fr/~spyropou/NetMod%202013/Lecture%2010.ppt.

figs/large-graphs/colored-graph-images.png

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

figs/large-graphs/images.png

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

figs/large-graphs/Graph-database.png

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

figs/large-graphs/F2.large.jpg

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

figs/large-graphs/vwPkz.png

Akilleenkanta.  Não sei qual o significado desse grafo.  (Copiado de akilleenkanta.blogspot.com.br/2014_08_01_archive.html.)

figs/large-graphs/rand_graph.png

SDLRG.  Não sei qual o significado desse grafo.  (Copiado de Stochastic dynamics on large random graphs, 2014, https://math.aalto.fi/~lleskela/SDLRG/.)

figs/large-graphs/GeometricGraphClustered.jpg

Balanced.  Não sei qual o significado desse grafo.  (Copiado de www.yger.net/the-balanced-network/.)

figs/large-graphs/random_geometric_graph.png

Cybergeography.  Não sei qual o significado desse grafo.  (Copiado de www.cybergeography-fr.org/atlas/more_topology.php.)

figs/large-graphs/gnucleus_graph_large.gif

?Pharyngula.  Não sei qual o significado desse grafo.  Parece uma árvore…  (Copiado de scienceblogs.com/pharyngula/2006/05/27/graphing-pharyngula/.)

figs/large-graphs/i-4155dfd099e252745bdd54e66a61f776-pharyngula_graph.gif

Cytonca.  Não sei qual o significado desse grafo.  (Copiado de apps.cytoscape.org/apps/cytonca.)

figs/large-graphs/ic.jpg

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

figs/large-graphs/image2.jpg

Pointeight.  Não sei qual o significado desse grafo.  (Copiado de www.jonathanjordan.staff.shef.ac.uk/research.html.)

figs/large-graphs/pointeight.gif

Toroidal.  Uma malha de polígonos na superfície de um toro:

figs/large-graphs/absint.jpg

Flight patterns (by Aaron Koblin).  Flight paths from FAA data drawn algorithmically and colored based on airplane model:

figs/large-graphs/aaron-koblin-flight-patterns-2011.jpg

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:

figs/large-graphs/paul-butler-facebook-2010.png