{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Redes Complexas (continuação)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assortatividade de graus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"Assortatividade\" é o nome dado à tendência de vértices se ligarem com vértices \"similares\". Por exemplo, numa sociedade segregada por classes, se construimos um grafo das relações de amizades entre pessoas, com as pessoas sendo os vértices a uma relação de amizade sendo uma aresta, então é de se esperar que exista assortatividade em termos de classe, com indivíduos de uma classe tendendo mais frequentemente a se associar com indivíduos da mesma classe.\n",
    "\n",
    "Para definir a assortatividade, precisamos definir qual a característica do vértice que queremos usar para avaliar assortatividade. Em princípio, podemos usar qualquer rótulo associado a vértices do grafo.\n",
    "\n",
    "No momento, vamos considerar apenas a **assortatividade de graus**, que usa como característica para verificar assortatividade o grau dos vértices. Neste caso, queremos saber se os vértices de grau mais alto tendem a se associar predominantemente a outros vértices com grau alto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coeficiente de assortatividade"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma forma de quantificar a assortatividade de graus é considerando que no fundo queremos encontrar uma correlação entre os graus dos dois lados de uma aresta.\n",
    "\n",
    "Podemo então usar o coeficiente de Pearson, onde as variáveis aleatórias são os graus nos dois lados de cada uma das arestas no grafo.\n",
    "\n",
    "Esta é o **coeficiente de assortatividade**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gex = nx.read_gml('exemplo.gml')\n",
    "gex = nx.convert_node_labels_to_integers(gex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(gex, pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_assortativity_coefficient(gex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grau médio dos vizinhos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Outra forma de avaliar a assortatividade é plotar um gráfico com o grau médio dos vizinho de todos os vértices para cada grau no grafo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "avneigh = nx.average_neighbor_degree(gex)\n",
    "max_degree = max(k for _, k in gex.degree)\n",
    "knn = np.zeros(max_degree+1)\n",
    "nnn = np.zeros(max_degree+1)\n",
    "for node, k in gex.degree:\n",
    "    knn[k] += avneigh[node]\n",
    "    nnn[k] += 1\n",
    "knn / nnn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_degree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centralidade de autovetor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quando usamos o grau para quantificar a importância de um vértice, não distinguimos entre ligações com vértices mais importantes ou menos importantes.\n",
    "\n",
    "Podemos então definir a importância de um vértice $i$ através de uma centralidade $e_i$ que leva em conta a centralidade dos vizinhos:\n",
    "$$ e_i = \\frac{1}{\\lambda}\\sum_j a_{ij}e_j,$$\n",
    "onde $\\lambda$ é usado para normalização. Isto pode ser reescrito como\n",
    "$$\\lambda \\mathbf{e} = \\mathbf{A}\\mathbf{e},$$ que é uma equação de autovalor, indicando que $\\mathbf{e}$ é o autovetor de $\\mathbf{A}$ associado com o autovalor $\\lambda$. Nesta aplicação, o importante é o autovalor associado com o maior autovalor de $\\mathbf{A}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.eigenvector_centrality(gex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centralidade de intermediação (_betweenness centrality_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos também indicar como importantes os vértices que servem para fazer ligações eficientes entre outros vértices. Aqui definimos uma ligação eficiente como uma ligação por caminho mais curto.\n",
    "\n",
    "Definimos a centralidade de intermediação como a fração dos caminhos mais curtos entre um par de vértices que passa por esse vértice:\n",
    "$$b_i = \\sum_{jk}\\frac{n(j, i, k)}{n(j,k)},$$\n",
    "onde $n(j,k)$ é o número de caminhos mais curtos existentes entre os vértices $j$ e $k$ e $n(j, i, k)$ é o número de caminhos mais curtos de $j$ para $k$ que passam por $i$.\n",
    "\n",
    "Muitas vezes é usada alguma normalização, mas não existe uma padronização."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.betweenness_centrality(gex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cliques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma **clique** é um subconjunto de vértices tais que existem arestas entre todos os pares de vértices nesse subconjunto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for clq in nx.find_cliques(gex):\n",
    "    print(clq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## k-cores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma forma de determinar quanto o vértice é central no grafo é através do $k$-core. Um $k$-core é um subgrafo definido da seguinte forma:\n",
    "\n",
    "- Retiramos todos os vértices com grau menor do que $k$.\n",
    "- Depois reanalizamos o grafo e repetimos o processo de remoção de vértices com grau restante menor do que $k$, até que todos os vértices restantes tenham grau maior ou igual a $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(nx.k_core(gex, 0), pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(nx.k_core(gex, 1), pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(nx.k_core(gex, 2), pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(nx.k_core(gex, 3), pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_networkx(nx.k_core(gex,4), pos=nx.get_node_attributes(gex, 'pos'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Com base no $k$-core, podemos definir o número de _core_ de um vértice como o maior valor de $k$ para o qual o vértice pertence ao $k$-core do grafo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.core_number(gex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modelos: Erdos e Rényi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No modelo de Erdös-Rényi, consideramos grafos construidos aleatoriamente da seguinte forma:\n",
    "\n",
    "- Fixamos o número de vértices $n$.\n",
    "- Para cada uma das $n(n-1)/2$ arestas possíveis, criamos a aresta com uma probabilidade $p$ fixa, independente das outras arestas.\n",
    "\n",
    "Os parâmetros $n$ e $p$ fixamo o modelo, e portanto esse grafo é geralmente denominado $G(n,p)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ger1 = nx.erdos_renyi_graph(16, 0.1)\n",
    "nx.draw_circular(ger1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ger2 = nx.erdos_renyi_graph(16, 0.2)\n",
    "nx.draw_circular(ger2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ger3 = nx.erdos_renyi_graph(16, 0.4)\n",
    "nx.draw_circular(ger3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O grau médio desse tipo de grafo pode ser calculado facilmente: Como cada vértice pode se ligar com $n-1$ outros vértices, e como cada ligação é feita com probabilidade $p$, o grau médio de um vértice nesse modelo, considerando todas as possíveis realizações do modelo com suas probabilidades, é dado por\n",
    "$$\\langle k \\rangle = p(n-1).$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_repetitions = 1000\n",
    "num_vertices = 100\n",
    "p = 0.03\n",
    "k_med = p * (num_vertices - 1)\n",
    "k_med_rep = np.zeros(num_repetitions)\n",
    "for i in range(num_repetitions):\n",
    "    g = nx.erdos_renyi_graph(num_vertices, p)\n",
    "    k_med_rep[i] = 2 * g.number_of_edges() / g.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(k_med_rep, bins=20);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(k_med)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}