Encontros06e07.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Encontros 6 e 7: Pequeno Mundo\n",
    "\n",
    "Entre as décadas de 50 e 80, [Stanley Milgram](https://en.wikipedia.org/wiki/Stanley_Milgram) e outros pesquisadores realizaram uma série de experimentos que ficaram conhecidos em conjunto como\n",
    "[experimento do pequeno mundo](https://en.wikipedia.org/wiki/Small-world_experiment). Seus resultados sugerem que, na rede de relacionamentos da sociedade, o caminho entre quaisquer dois indivíduos é relativamente curto, ou seja, o comprimento médio dos caminhos do grafo é baixo.\n",
    "\n",
    "Cerca de 40 anos depois, os alunos no sexto perído da Engenharia de Computação do Insper realizaram experimentos que sugerem a existência de uma estrutura análoga no serviço online de músicas *Spotify.* Foi constatado que, seguindo o sistema de *Artistas Relacionados*, é possível sair de um artista contemporâneo popular e chegar em um artista clássico consagrado usando de oito a dez passos.\n",
    "\n",
    "Como podemos caracterizar essas *redes pequeno mundo*? Como podemos afirmar que um grafo é pequeno mundo e outro não?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Módulos necessários.\n",
    "\n",
    "from random import shuffle\n",
    "from statistics import mean\n",
    "from itertools import combinations\n",
    "\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "import networkx as nx\n",
    "\n",
    "import socnet as sn\n",
    "\n",
    "\n",
    "# Parâmetros ajustáveis.\n",
    "\n",
    "NUM_NODES = 16\n",
    "MAX_NODES = 64\n",
    "\n",
    "NUM_TIMES = 32\n",
    "\n",
    "AVG_DEGREE = 8\n",
    "\n",
    "\n",
    "# Configuração de visualização.\n",
    "\n",
    "sn.node_size = 10\n",
    "\n",
    "sn.edge_width = 1\n",
    "\n",
    "\n",
    "# Função de conveniência para mostrar grafos.\n",
    "\n",
    "def show_graph(g):\n",
    "    sn.reset_node_colors(g)\n",
    "    sn.reset_edge_colors(g)\n",
    "\n",
    "    sn.show_graph(g)\n",
    "\n",
    "\n",
    "# Função de conveniência para plotar agregados.\n",
    "\n",
    "def plot(xlabel, xdata, ylabel, ydata):\n",
    "    df = pd.DataFrame({xlabel: xdata, ylabel: ydata})\n",
    "\n",
    "    sns.relplot(data=df, x=xlabel, y=ylabel, kind='line')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Caminhos relativamente curtos\n",
    "\n",
    "Primeiramente, precisamos evitar caracterizações baseadas em algum \"número mágico\" como [seis](https://en.wikipedia.org/wiki/Six_degrees_of_separation). A diferença entre os comprimentos médios obtidos pelo Milgram e os comprimentos médios obtidos do Spotify exigem uma caracterização mais genérica.\n",
    "\n",
    "Informalmente, a definição de pequeno mundo já foi estabelecida: um grafo cujos caminhos são *relativamente curtos*. Nosso objetivo é formalizar o suficiente essa definição para poder usá-la em um teste de hipótese.\n",
    "\n",
    "Um primeiro passso natural é tentar visualizar uma rede pequeno mundo para obter *insights* sobre a \"cara\" dela.\n",
    "\n",
    "Nas lousinhas, as duplas Graicer/Tirta e Fred/Rapha apresentaram propostas baseadas em *árvore*. Uma árvore é uma *rede conexa sem circuitos*, ou seja, é um grafo com as seguintes propriedades:\n",
    "\n",
    "* entre quaisquer dois nós, existe um caminho;\n",
    "* esse caminho é o único entre esses nós.\n",
    "\n",
    "O módulo *NetworkX* possui uma função pronta para gerar uma árvore aleatória com dado número de nós."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Gera uma árvore aleatória.\n",
    "g = nx.random_tree(NUM_NODES)\n",
    "\n",
    "# Atribui posições aos nós.\n",
    "sn.set_spring_positions(g)\n",
    "\n",
    "# Mostra o grafo.\n",
    "show_graph(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Os caminhos desse grafo são de fato relativamente curtos..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...mas há uma pequena \"trapaça\" envolvida: os caminhos são curtos *supondo esse dado número de nós*.\n",
    "\n",
    "Vamos ver o que acontece com o comprimento médio conforme variamos esse número."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera uma árvore aleatória...\n",
    "        g = nx.random_tree(x)\n",
    "\n",
    "        # ... e registra o par (número de nós X comprimento médio).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_shortest_path_length(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'comprimento médio', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Xi, o comprimento médio cresce quase linearmente em função do número de nós... ou seja, a estrutura de árvore não parece modelar um pequeno mundo em redes maiores.\n",
    "\n",
    "As duplas Sabrina/Leo e Ale/Paulo pensaram em uma proposta alternativa: um anel de nós com \"atalhos\" adicionados especificamente para encurtar os caminhos. Esse tipo de aresta, que \"atravessa\" um circuito, é conhecido como *corda*.\n",
    "\n",
    "A função abaixo constrói uma rede desse tipo, mas com uma restrição: além do número de nós, ela exige que você especifique qual é o *grau médio* que o grafo deve ter. O *grau* de um nó é o número de arestas que estão ligadas a ele, portanto, o grau médio é proporcional à *densidade* do grafo, ou seja, ao número total de arestas.\n",
    "\n",
    "Por que estamos impondo essa restrição? Para evitar uma \"segunda trapaça\": queremos uma caracterização *estrutural* de pequeno mundo, que permita comparar grafos com *mesmo número de nós* e *mesma densidade*. Essa proposta de anel com cordas só pode ser considerada promissora se parar em pé sem o \"migué\" de ficarmos adicionando atalhos à vontade até os caminhos ficarem curtos o suficiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chorded_ring(num_nodes, avg_degree):\n",
    "\n",
    "    # Gera um grafo circular.\n",
    "    g = nx.cycle_graph(num_nodes)\n",
    "\n",
    "    # Prepara uma lista de pares de nós para sorteio.\n",
    "    edges = [(n, m) for n, m in combinations(g.nodes, 2)]\n",
    "    shuffle(edges)\n",
    "\n",
    "    # Calcula limite de arestas a partir do grau médio.\n",
    "    # Você consegue enxergar porque essa relação vale?\n",
    "    max_edges = int((num_nodes * avg_degree) / 2 + 0.5)\n",
    "\n",
    "    # Para cada par de nós sorteado...\n",
    "    for n, m in edges:\n",
    "\n",
    "        # ...se a aresta correspondente não existe...\n",
    "        if not g.has_edge(n, m):\n",
    "\n",
    "            # ...cria a aresta, ou seja, adiciona o \"atalho\"...\n",
    "            g.add_edge(n, m)\n",
    "\n",
    "            # ... e, se atingir o limite, para.\n",
    "            if g.number_of_edges() == max_edges:\n",
    "                break\n",
    "\n",
    "    return g\n",
    "\n",
    "\n",
    "# Gera um anel com cordas.\n",
    "g = chorded_ring(NUM_NODES, AVG_DEGREE)\n",
    "\n",
    "# Atribui posições aos nós.\n",
    "sn.set_circle_positions(g)\n",
    "\n",
    "# Mostra o grafo.\n",
    "show_graph(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Os caminhos desse grafo são de fato relativamente curtos..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...então vamos verificar se a \"trapaça\" anterior não está se repetindo.\n",
    "\n",
    "Vamos ver o que acontece com o comprimento médio conforme variamos o número de nós."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um anel com cordas...\n",
    "        g = chorded_ring(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós X comprimento médio).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_shortest_path_length(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'comprimento médio', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Opa, isso é promissor! Temos um comportamento quase logaritmico, ou seja, parece que o comprimento médio praticamente estabiliza a partir de um certo número de nós. Isso parece ser uma boa proposta de pequeno mundo! Mas...\n",
    "\n",
    "## O teste do macaco\n",
    "\n",
    "As duplas Elisa/Bruna e Isabella/Hugo repararam que esse tipo de comportamento logaritmico também parece ser verdade para um grafo *aleatório*. O que significa grafo aleatório? Imagine um grafo que começa vazio, sem nenhuma aresta, e aos poucos um macaco vai colocando arestas aleatoriamente.\n",
    "\n",
    "Esse modelo de construção é conhecido como [Erdos-Renyi](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) e sua formalização é simples: existe uma probabilidade $p$ tal que, para quaisquer dois nós $n$ e $m$, a probabilidade da aresta $\\{n, m\\}$ existir é $p$.\n",
    "\n",
    "É fácil adaptar uma função pronta do *NetworkX* para gerar grafos Erdos-Renyi com dado número de nós e dado grau médio esperado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def erdos_renyi_graph(num_nodes, avg_degree):\n",
    "    if num_nodes == 1:\n",
    "        return nx.empty_graph(num_nodes)\n",
    "\n",
    "    # Calcula limite de arestas a partir do grau médio.\n",
    "    # Você consegue enxergar porque essa relação vale?\n",
    "    max_edges = int((num_nodes * avg_degree) / 2 + 0.5)\n",
    "\n",
    "    # A partir desse limite de arestas, calculamos o p.\n",
    "    p = max_edges / (num_nodes * (num_nodes - 1))\n",
    "\n",
    "    # Agora podemos usar a função pronta, baseada em p.\n",
    "    return nx.erdos_renyi_graph(num_nodes, p)\n",
    "\n",
    "\n",
    "# Gera um grafo aleatório.\n",
    "g = erdos_renyi_graph(NUM_NODES, AVG_DEGREE)\n",
    "\n",
    "# Atribui posições aos nós.\n",
    "sn.set_spring_positions(g)\n",
    "\n",
    "# Mostra o grafo.\n",
    "show_graph(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Novamente, vamos ver o que acontece com o comprimento médio conforme variamos o número de nós."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um grafo aleatório...\n",
    "        g = erdos_renyi_graph(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós X comprimento médio).\n",
    "        xdata.append(x)\n",
    "        lengths = []\n",
    "        for n, m in combinations(g.nodes, 2):\n",
    "            try:\n",
    "                length = nx.shortest_path_length(g, n, m)\n",
    "            except nx.NetworkXNoPath:\n",
    "                length = 0\n",
    "            lengths.append(length)\n",
    "        ydata.append(mean(lengths) if lengths else 0)\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'comprimento médio', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Er... algo de errado não está certo... a proposta do anel com cordas antes parecia promissora, mas agora estamos vendo que ela é um pouco melhor mas não muito diferente do grafo do macaco! E, considerando os exemplos reais que conhecemos, o grafo do macaco definitivamente não é um pequeno mundo!\n",
    "\n",
    "Na verdade, pequenos mundos são caracterizados por mais do que simplesmente a média dos caminhos.\n",
    "\n",
    "## O coeficiente de transitividade *(clustering coefficient)*\n",
    "\n",
    "Lembram da pequena demonstração feita em sala?\n",
    "\n",
    "* A partir de Mozart, podemos ir para Chopin, Beethoven, Grieg, Bach, Puccini, Brahms, Dvorak, Debussy, Vivaldi...\n",
    "* A partir de Chopin, podemos ir para Beethoven, Grieg, Debussy, Brahms, Dvorak, Mozart, Bach, Vivaldi...\n",
    "* A partir de Beethoven, podemos ir para Grieg, Brahms, Debussy, Bach, Mozart, Dvorak, Vivaldi...\n",
    "\n",
    "Aparentemente temos uma \"panelinha\", ou *clique* na terminologia de grafos: um conjunto de nós tal que todos estão conectados com todos. É essa presença de cliques que não vemos nem no anel com cordas e nem no grafo aleatório.\n",
    "\n",
    "Um *verdadeiro* pequeno mundo possui, ao mesmo tempo, caminhos relativamente curtos e alta presença de cliques. Essa é a caracterização completa! Mas como quantificar isso?\n",
    "\n",
    "Podemos observar que uma alta presença de cliques está diretamente relacionada ao fenômeno de *transitividade*, ou seja, dados três nós $n, m ,l$, temos que, se $n, m$ estão conectados e $m, l$ estão conectados, então há uma grande chance de $n, l$ estarem conectados.\n",
    "\n",
    "O *coeficiente de transitividade* de um nó $n$ é\n",
    "\n",
    "$$\\mathcal{C}(n) = \\frac{\\textrm{quantidade de pares de vizinhos de }n\\textrm{ que estão conectados entre si}}{\\textrm{quantidade total de pares de vizinhos de }n}$$\n",
    "\n",
    "e o coeficiente de transitividade de uma rede é a média dos coeficientes de transitividade de seus nós. Esse valor pode ser usado como métrica da presença de cliques em um grafo! Vejamos sua variação para o anel com cordas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um anel com cordas...\n",
    "        g = chorded_ring(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós X coeficiente de transitividade).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_clustering(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'coeficiente de transitividade', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A presença de cliques *cai* conforme o número de nós cresce! Vejamos a variação para o grafo aleatório."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um grafo aleatório...\n",
    "        g = erdos_renyi_graph(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós x coeficiente de transitividade).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_clustering(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'coeficiente de transitividade', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos confirmar que, infelizmente, o anel com cordas não está oferecendo muito de pequeno mundo além do que o macaco pode oferecer, pois ambos perdem cliques conforme crescem... Mas essa investigação nos deu informações valiosas!\n",
    "\n",
    "## A necessidade de um benchmark\n",
    "\n",
    "Podemos perceber, pelos resultados acima, que obter uma métrica não basta: precisamos também de uma *referência* para podermos interpretar o que o valor obtido significa. Fizemos isso no primeiro encontro, lembram? Sabíamos que a rede de citações era desigual por que tínhamos uma referência de igualdade: a *distribuição normal*.\n",
    "\n",
    "Então qual seria nosso benchmark de \"mundo-pequenez\"? A dupla Isabella/Hugo fez uma sugestão interessante: usar grafos que são reconhecidamente pequeno mundo para deduzir um benchmark a partir deles. Seríamos a favor dessa sugestão se:\n",
    "\n",
    "1. tivéssemos o acesso a um grande volume desses grafos e a confiança de que o reconhecimento de pequeno mundo foi preciso;\n",
    "2. esta fosse uma disciplina voltada a *Machine Learning*. :)\n",
    "\n",
    "Infelizmente, não podemos supor isso, então temos que procurar algo mais simples...\n",
    "\n",
    "Note que o grafo aleatório é uma boa referência de *comprimento médio desejado* mas *coeficiente de transitividade indesejado*. O mínimo que se espera de uma rede pequeno mundo é que tenha um coeficiente de transitividade melhor que o do grafo aleatório.\n",
    "\n",
    "Será que existe uma boa referência de *coeficiente de transitividade desejado* mas *comprimento médio indesejado*? Sim! Tudo o que precisamos fazer é um \"anel de cliques\". Observe a função abaixo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def caveman_graph(num_nodes, avg_degree):\n",
    "    if avg_degree % 2 != 0:\n",
    "        raise ValueError('grau médio deve ser par')\n",
    "\n",
    "    # Gera um grafo circular.\n",
    "    g = nx.cycle_graph(num_nodes)\n",
    "\n",
    "    # Calcula o limite de arestas que\n",
    "    # cada nó dispara para cada lado.\n",
    "    max_edges = avg_degree // 2\n",
    "\n",
    "    # Prepara uma lista de nós para percorrer por índice.\n",
    "    nodes = list(g.nodes)\n",
    "\n",
    "    # Para cada nó...\n",
    "    for i in range(len(nodes)):\n",
    "        n = nodes[i]\n",
    "\n",
    "        # ...e cada aresta a disparar...\n",
    "        for shift in range(2, max_edges + 1):\n",
    "            j = (i + shift) % len(nodes)\n",
    "            m = nodes[j]\n",
    "\n",
    "            # ...dispara a aresta.\n",
    "            g.add_edge(n, m)\n",
    "\n",
    "    return g\n",
    "\n",
    "\n",
    "# Gera um anel de cliques.\n",
    "g = caveman_graph(NUM_NODES, AVG_DEGREE)\n",
    "\n",
    "# Atribui posições aos nós.\n",
    "sn.set_circle_positions(g)\n",
    "\n",
    "# Mostra o grafo.\n",
    "show_graph(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vejamos a variação do comprimento médio..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um anel de cliques...\n",
    "        g = caveman_graph(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós X comprimento médio).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_shortest_path_length(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'comprimento médio', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...e a variação do coeficiente de transitividade."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xdata = []\n",
    "ydata = []\n",
    "\n",
    "# Repete o experimento várias vezes.\n",
    "for t in range(NUM_TIMES):\n",
    "\n",
    "    # Para cada número de nós possível...\n",
    "    for x in range(1, MAX_NODES + 1):\n",
    "\n",
    "        # ...gera um anel de cliques...\n",
    "        g = caveman_graph(x, AVG_DEGREE)\n",
    "\n",
    "        # ... e registra o par (número de nós X coeficiente de transitividade).\n",
    "        xdata.append(x)\n",
    "        ydata.append(nx.average_clustering(g))\n",
    "\n",
    "    print('repetição {}'.format(t + 1))\n",
    "\n",
    "# Plota resultado agregado dos experimentos.\n",
    "plot('número de nós', xdata, 'coeficiente de transitividade', ydata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Conclusão: o mínimo que se espera de uma rede pequeno mundo é que tenha um comprimento médio melhor que o do anel de cliques.\n",
    "\n",
    "Entendeu todos os *grafos* e *gráficos* acima? Está na hora de redigir a hipótese."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}