GraphFrames-Actors.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Procesamiento de Grafos / Redes Sociales: Kevin Bacon\n",
    "[https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon#Bacon_numbers](https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon#Bacon_numbers)\n",
    "\n",
    "You are given a network of actors, where there is an edge between two actors if they have played together in some movie between 1995 and 2004"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Una primer mirada a los data sets que vamos a utilizar\n",
    "\n",
    "Tenemos dos data sets:\n",
    "\n",
    "- **imdb_actors_key_noheader.tsv:** Informacion sobre los actores (id, nombre, cantidad de peliculas actuadas, generos por peliculas, etc).\n",
    "- **imdb_actor_edges.tsv:** Network propiamente dicha (relaciones de actor a actor por id y cantidad de veces que actuaron juntos). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cantidad de Actores:\n",
      "17577\n"
     ]
    }
   ],
   "source": [
    "# carga de raw data\n",
    "# tsv: tab separated value\n",
    "actors = sc.textFile('data/imdb_actors_key_noheader.tsv', 8)\n",
    "print('Cantidad de Actores:')\n",
    "print(actors.count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(u'15629',\n",
       "  u'\"Rudder, Michael (I)\"',\n",
       "  u'12',\n",
       "  u'Thriller',\n",
       "  u'Action:1,Comedy:1,Drama:1,Fantasy:1,Horror:1,NULL:2,Romance:1,Sci-Fi:1,Thriller:2,War:1'),\n",
       " (u'5026',\n",
       "  u'\"Morgan, Debbi\"',\n",
       "  u'16',\n",
       "  u'Drama',\n",
       "  u'Comedy:2,Documentary:1,Drama:6,Horror:2,NULL:3,Romance:2'),\n",
       " (u'11252',\n",
       "  u'\"Bellows, Gil\"',\n",
       "  u'33',\n",
       "  u'Drama',\n",
       "  u'Comedy:6,Documentary:1,Drama:7,Family:1,Fantasy:1,Horror:1,Mystery:2,NULL:2,Romance:6,Short:2,Thriller:4')]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# realizas splits de las tuplas por \\t (tab)\n",
    "actors.map(lambda x: tuple(x.split('\\t')))\\\n",
    "      .take(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cantidad de Aristas/Edges:\n",
      "287074\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(u'17776', u'17778', u'6'), (u'5578', u'9770', u'3'), (u'5578', u'929', u'2')]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# la red tiene nodos de la forma (actor1, actor2, veces_que_actuaron_juntos)\n",
    "network = sc.textFile('data/imdb_actor_edges.tsv')\n",
    "print 'Cantidad de Aristas/Edges:'\n",
    "print network.count()\n",
    "\n",
    "network.map(lambda x: tuple(x.split('\\t')))\\\n",
    "      .take(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inicializando los RDDs\n",
    "\n",
    "Vamos a inicializar los RDDs que utilizaremos\n",
    "\n",
    "**Nota** Dado que estaremos usando estos RDDs en muchos casos de forma iterativa, realizaremos la operacion ``.cache()`` sobre los mismos, asegurandonos de que esa forma una vez que es calculado al haberse aplicado una accion cada nodo mantenga en memoria la particion que calculo.\n",
    "\n",
    "Esto es importante al realizar algoritmos iterativos, dado que permite hasta una mejora de velocidad de 10x.\n",
    "\n",
    "Para mas referencia: [https://spark.apache.org/docs/latest/programming-guide.html#rdd-persistence](https://spark.apache.org/docs/latest/programming-guide.html#rdd-persistence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# inicializamos algunos rdds que vamos a utilizar en conjunto con nuestro network\n",
    "\n",
    "# de la informacion de actores nos quedamos con su identificados y nombre\n",
    "actors_key = actors.map(lambda x: tuple(x.split('\\t')))\\\n",
    "                    .map(lambda x:(int(x[0]),x[1]))\\\n",
    "                    .cache()\n",
    "\n",
    "actors_key_cat = actors.map(lambda x: tuple(x.split('\\t')))\\\n",
    "                    .map(lambda x:(int(x[0]),(x[1],x[3])))\\\n",
    "                    .cache()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ejemplo de actores de actors_key:\n",
      "[(15629, u'\"Rudder, Michael (I)\"'), (5026, u'\"Morgan, Debbi\"'), (11252, u'\"Bellows, Gil\"'), (5150, u'\"Dray, Albert\"'), (4057, u'\"Daly, Shane (I)\"')]\n"
     ]
    }
   ],
   "source": [
    "# actors_key tiene nodos de la forma (actor_id, nombre_actor)\n",
    "print(\"Ejemplo de actores de actors_key:\")\n",
    "print actors_key.take(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ejemplo de actores de actors_key_cat:\n",
      "[(15629, (u'\"Rudder, Michael (I)\"', u'Thriller')), (5026, (u'\"Morgan, Debbi\"', u'Drama')), (11252, (u'\"Bellows, Gil\"', u'Drama')), (5150, (u'\"Dray, Albert\"', u'Comedy')), (4057, (u'\"Daly, Shane (I)\"', u'Drama'))]\n"
     ]
    }
   ],
   "source": [
    "# actors_key_cat tiene nodos de la forma (actor_id, \n",
    "# (nombre_actor, nombre_categoria_mas_frecuente))\n",
    "print(\"Ejemplo de actores de actors_key_cat:\")\n",
    "print actors_key_cat.take(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nuestro Heroe:\n",
      "[(3257, (u'\"Bacon, Kevin\"', u'Drama'))]\n"
     ]
    }
   ],
   "source": [
    "# Verificamos que podamos realizar algo con todos esto :)\n",
    "KEVIN_BACON_ID=3257\n",
    "kevin = actors_key_cat.filter(lambda x:x[0]==KEVIN_BACON_ID)\n",
    "print \"Nuestro Heroe:\"\n",
    "print kevin.collect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "287074\n"
     ]
    }
   ],
   "source": [
    "# inicializamos el RDD de la network\n",
    "network = sc.textFile('data/imdb_actor_edges.tsv')\n",
    "print network.count()\n",
    "network = network.map(lambda x:tuple(x.split('\\t')))\\\n",
    "                 .map(lambda x:(int(x[0]),int(x[1]),int(x[2])))\\\n",
    "                 .cache()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ejemplo de 5 tuplas del network RDD:\n",
      "[(17776, 17778, 6), (5578, 9770, 3), (5578, 929, 2), (5578, 9982, 2), (1835, 6278, 2)]\n"
     ]
    }
   ],
   "source": [
    "# network tiene nodos de la forma (actor1, actor2, cantidad_de_veces_que_actuaron_juntos)\n",
    "print \"Ejemplo de 5 tuplas del network RDD:\"\n",
    "print network.take(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Estructuras para un Grafo\n",
    "\n",
    "Las representacion posibles que tenemos son:\n",
    "\n",
    "- **Lista de Aristas**\n",
    "    - Una tupla por arista del tipo (nodo1, nodo2).\n",
    "    - Puede incluir algun otro tipo de informacion relevante para la relacion.\n",
    "- **Lista de Adyacencias**\n",
    "    - Una tupla por nodo del tipo (nodo, [lista de vecinos])\n",
    "    \n",
    "    \n",
    "Inicialmente trabajaremos con el grafo como una lista de aristas, luego para atacar otros problemas trabajaremos en spark con una lista de adyacencias.\n",
    "\n",
    "Sin embargo podemos ver alguna informacion interesante respecto al grafo con el que estaremos trabajando."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cantidad Nodos (Actores): 17577\n",
      "Cantidad de Aristas (Conexiones): 287074\n"
     ]
    }
   ],
   "source": [
    "print 'Cantidad Nodos (Actores): ' + str(actors_key.count())\n",
    "print 'Cantidad de Aristas (Conexiones): ' + str(network.count())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analizando Algunas propiedades de los Datos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[u'Mystery',\n",
       " u'Romance',\n",
       " u'Drama',\n",
       " u'Action',\n",
       " u'',\n",
       " u'Fantasy',\n",
       " u'Horror',\n",
       " u'Comedy',\n",
       " u'Animation',\n",
       " u'Music',\n",
       " u'Sci-Fi',\n",
       " u'Adventure',\n",
       " u'War',\n",
       " u'Adult',\n",
       " u'Musical',\n",
       " u'Western',\n",
       " u'Thriller',\n",
       " u'Family',\n",
       " u'Crime']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# cuales son los generos posibles\n",
    "actors_key_cat.map(lambda x: x[1][1])\\\n",
    "              .distinct()\\\n",
    "              .collect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mystery 66\n",
      "Romance 1027\n",
      "Drama 7302\n",
      "Action 537\n",
      " 68\n",
      "Fantasy 137\n",
      "Horror 171\n",
      "Comedy 2928\n",
      "Animation 284\n",
      "Music 631\n",
      "Sci-Fi 421\n",
      "Adventure 63\n",
      "War 69\n",
      "Adult 1811\n",
      "Musical 21\n",
      "Western 24\n",
      "Thriller 947\n",
      "Family 359\n",
      "Crime 711\n"
     ]
    }
   ],
   "source": [
    "# cuantas personas tenemos por generos posibles\n",
    "actors_per_usual_category = \\\n",
    "    actors_key_cat.map(lambda x: (x[1][1],1))\\\n",
    "                  .reduceByKey(lambda x,y: x+y)\\\n",
    "                  .collect();\n",
    "\n",
    "for actor in actors_per_usual_category:\n",
    "    print str(actor[0]) + ' ' + str(actor[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10 actores que trabajaron con a mayor cantidad de personas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "mn = network.flatMap(lambda x:[(x[0],1),(x[1],1)])\n",
    "mn = mn.reduceByKey(lambda x,y:x+y)\n",
    "mn = mn.join(actors_key_cat)\n",
    "mn = mn.filter(lambda x: x[1][1][1] != 'Adult')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"Hanks, Tom\"(457 personas) Genero:Family\n",
      "\"Jackson, Samuel L.\"(427 personas) Genero:Drama\n",
      "\"Lopez, Jennifer (I)\"(410 personas) Genero:Music\n",
      "\"Goldberg, Whoopi\"(398 personas) Genero:Comedy\n",
      "\"Stiller, Ben\"(382 personas) Genero:Comedy\n",
      "\"Berry, Halle\"(376 personas) Genero:Family\n",
      "\"Diaz, Cameron\"(361 personas) Genero:Drama\n",
      "\"Myers, Mike (I)\"(345 personas) Genero:Comedy\n",
      "\"Spears, Britney\"(341 personas) Genero:Music\n",
      "\"Cruise, Tom\"(336 personas) Genero:Music\n"
     ]
    }
   ],
   "source": [
    "top_actors = mn.takeOrdered(10,lambda x:-x[1][0])\n",
    "for actor in top_actors:\n",
    "    print actor[1][1][0]+'('+str(actor[1][0]) + ' personas) Genero:' + str(actor[1][1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Kevin Bacon trabajo con 101 personas\n"
     ]
    }
   ],
   "source": [
    "# Que pasa con Kevin Bacon?\n",
    "bm = mn.filter(lambda x:x[0]==KEVIN_BACON_ID).take(1)\n",
    "print \"Kevin Bacon trabajo con \" + str(bm[0][1][0]) + \" personas\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# One Degree of Kevin Bacon\n",
    "\n",
    "Queremos conocer las personas que se encuentra a un grado de separacion de Kevin Bacon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8087, 6895, 708, 8982, 10966, 2662, 7105, 519, 7762, 8578, 3169, 8996, 8999, 9386, 5612, 3160, 4248, 3242, 3133, 1064, 3143, 9079, 2896, 3308, 3305, 3306, 481, 3884, 701, 8334, 6131, 555, 6745, 15285, 3243, 3267, 3292, 1459, 3266, 6502, 3279, 3142, 3295, 3317, 569, 7566, 756, 2918, 6900, 3930, 3361, 3983, 565, 713, 3253, 3252, 7884, 3287, 6716, 9377, 3154, 9511, 2917, 1495, 9388, 10877, 3520, 689, 9237, 3923, 3176, 16485, 3869, 3255, 3183, 9409, 1627, 9449, 726, 716, 9406, 5744, 10659, 3213, 7020, 6492, 8468, 2926, 3309, 3235, 11464, 3721, 1253, 8751, 3870, 1047, 724, 2664, 3354, 3239, 5725]\n",
      "Actors a 1 grado de separacion de Kevin Bacon: 101\n"
     ]
    }
   ],
   "source": [
    "# filtramos aquellos aristas que tengan a kevin bacon\n",
    "kevin1 = network.filter(lambda x:x[0]==KEVIN_BACON_ID or \\\n",
    "                        x[1]==KEVIN_BACON_ID)\n",
    "# emitimos aquellos actor_id de los actores que trabajaron \n",
    "# con Kevin\n",
    "kevin1 = kevin1.map(\n",
    "    lambda x:x[0] if x[1]==KEVIN_BACON_ID else x[1])\n",
    "print kevin1.collect()\n",
    "print \"Actors a 1 grado de separacion de Kevin Bacon: \" + str(kevin1.count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"Danes, Claire\"\n",
      "\"Wilson, Luke (I)\"\n",
      "\"Taylor, Elizabeth (I)\"\n",
      "\"Hoffman, Dustin\"\n",
      "\"Harris, Ed (I)\"\n",
      "\"Pollak, Kevin\"\n",
      "\"Danson, Ted\"\n",
      "\"Sinise, Gary\"\n",
      "\"Hanks, Tom\"\n",
      "\"Bisset, Jacqueline\"\n",
      "\"Ice-T\"\n",
      "\"Harden, Marcia Gay\"\n",
      "\"Grant, Hugh (I)\"\n",
      "\"Bonham Carter, Helena\"\n",
      "\"Jackson, Janet (I)\"\n",
      "\"Ford, Harrison (I)\"\n",
      "\"Shue, Elisabeth\"\n",
      "\"Jolie, Angelina\"\n",
      "\"Gere, Richard\"\n",
      "\"Moore, Demi\"\n",
      "\"Keaton, Michael\"\n",
      "\"Fishburne, Laurence\"\n",
      "\"Quinlan, Kathleen\"\n",
      "\"Penn, Sean\"\n",
      "\"Robbins, Tim (I)\"\n",
      "\"Dern, Laura\"\n",
      "\"Leigh, Jennifer Jason\"\n",
      "\"Cher (I)\"\n",
      "\"Goldberg, Whoopi\"\n",
      "\"Crudup, Billy\"\n",
      "\"Ryan, Meg\"\n",
      "\"Lauper, Cyndi\"\n",
      "\"Grunberg, Greg\"\n",
      "\"Dunn, Kevin (I)\"\n",
      "\"Spears, Britney\"\n",
      "\"Roberts, Julia\"\n",
      "\"Wahlberg, Mark (I)\"\n",
      "\"Lange, Jessica\"\n",
      "\"Smith Jr., Eddie Bo\"\n",
      "\"Parker, Sarah Jessica\"\n",
      "\"Howard, Clint\"\n",
      "\"Fonda, Bridget\"\n",
      "\"Paxton, Bill\"\n",
      "\"Reitman, Ivan\"\n",
      "\"Dillon, Matt (I)\"\n",
      "\"Spacey, Kevin\"\n",
      "\"Lane, Diane (I)\"\n",
      "\"Travolta, John\"\n",
      "\"Norwood, Brandy\"\n",
      "\"Gibson, Mel (I)\"\n",
      "\"Brolin, Josh\"\n",
      "\"Riegert, Peter\"\n",
      "\"Crawford, Thomas (I)\"\n",
      "\"Matlin, Marlee\"\n",
      "\"Helgeland, Brian\"\n",
      "\"Allen, Karen (I)\"\n",
      "\"Madonna (I)\"\n",
      "\"Matheson, Tim (I)\"\n",
      "\"De Niro, Robert\"\n",
      "\"MacLaine, Shirley\"\n",
      "\"McRobbie, Peter\"\n",
      "\"Driver, Minnie\"\n",
      "\"Ramis, Harold\"\n",
      "\"Hopper, Dennis\"\n",
      "\"Silverstone, Alicia\"\n",
      "\"Tomlin, Lily\"\n",
      "\"Costner, Kevin\"\n",
      "\"Eastwood, Clint\"\n",
      "\"McGill, Bruce\"\n",
      "\"Furst, Stephen\"\n",
      "\"Slotnick, Joey\"\n",
      "\"Keitel, Harvey\"\n",
      "\"Verhoeven, Paul (I)\"\n",
      "\"Jameson, Jenna\"\n",
      "\"Newton-John, Olivia\"\n",
      "\"Rimes, LeAnn\"\n",
      "\"Hoffman, Philip Seymour\"\n",
      "\"Crawford, Cindy (I)\"\n",
      "\"Hounsou, Djimon\"\n",
      "\"Sedgwick, Kyra\"\n",
      "\"Woodruff Jr., Tom\"\n",
      "\"Linney, Laura\"\n",
      "\"Murphy, Eddie (I)\"\n",
      "\"Landis, John (I)\"\n",
      "\"Bon Jovi, Jon\"\n",
      "\"Douglas, Michael (I)\"\n",
      "\"Vella, Vinny\"\n",
      "\"Masterson, Mary Stuart\"\n",
      "\"Carrey, Jim\"\n",
      "\"Schwarzenegger, Arnold\"\n",
      "\"Schiffer, Claudia\"\n",
      "\"Fonda, Peter (I)\"\n",
      "\"Renfro, Brad\"\n",
      "\"Douglas, Illeana\"\n",
      "\"Cruise, Tom\"\n",
      "\"Vernon, John (I)\"\n",
      "\"Willis, Bruce (I)\"\n",
      "\"Dickens, Kim\"\n",
      "\"Bratt, Benjamin (I)\"\n",
      "\"Muniz, Frankie\"\n",
      "\"Scott, Jill (II)\"\n"
     ]
    }
   ],
   "source": [
    "#obtenemos los nombres de los actores a un grado de separacion.\n",
    "kevin1_names = kevin1.map(lambda x:(x,1))\\\n",
    "                     .join(actors_key)\\\n",
    "                     .map(lambda x:x[1][1])\n",
    "\n",
    "bacon1_actors = kevin1_names.collect()\n",
    "for actor in bacon1_actors:\n",
    "    print actor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grado Promedio de la Red"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numero total de actores: 17577\n"
     ]
    }
   ],
   "source": [
    "total_deg = network.flatMap(lambda x:[(x[0],1),(x[1],1)])\\\n",
    "                   .reduceByKey(lambda x,y: x+y)\n",
    "\n",
    "num_actors = total_deg.count()\n",
    "\n",
    "print \"Numero total de actores: \" + str(num_actors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grado Promedio: 16.3323661603\n"
     ]
    }
   ],
   "source": [
    "acum_deg = total_deg.map(lambda x:x[1])\\\n",
    "                    .reduce(lambda x,y: x+y)\n",
    "acum_deg\n",
    "\n",
    "print \"Grado Promedio: \" + str((float(acum_deg)/num_actors)/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N-Degrees of Kevin Bacon\n",
    "\n",
    "Para poder realizar el calculo de los N-Degrees de Kevin Bacon (conocidos como Bacon Numbers) realizaremos una implementacion distribuida de BFS.\n",
    "\n",
    "Para poder realizar la implementacion de N-Degrees of Kevin Bacon vamos a necesitar convertirlo en lista de adyacencia, \n",
    "\n",
    "```\n",
    "(A,B)(A,C)(B,C) a una representacion del tipo (A,[B,C]),(B,[C]).\n",
    "```\n",
    "\n",
    "Pero en particular para implementar algoritmos de camino minimos con un formato particular.\n",
    "\n",
    "```\n",
    "(node_id, (distance, status, [list of neighbors], trace))\n",
    "```\n",
    "\n",
    "En el caso particular para calcular los Bacon Numbers vamos a usar la siguiente representacion:\n",
    "\n",
    "```\n",
    "[(node_id,(distance_from_kevin,status,[neighbors], trace)),....(node,(distance_from_kevin,status,[neighbors], trace))]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convirtiendo el grafo en lista de adyacencia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(3257, set([519, 9237, 1047, 1064, 555, 8751, 565, 569, 6716, 3133, 3142, 3143, 7762, 3160, 6745, 1627, 5725, 16485, 3169, 2918, 2662, 3176, 3183, 5744, 2664, 10877, 3721, 3213, 8334, 4248, 9377, 3235, 3239, 9386, 3243, 9388, 689, 3252, 3253, 3255, 701, 9406, 9409, 3266, 3267, 708, 11464, 713, 716, 3279, 724, 10966, 3287, 3292, 3295, 7884, 1253, 9449, 3306, 8999, 3308, 3309, 6895, 6900, 3317, 726, 8468, 8982, 3354, 3869, 3870, 3361, 8996, 9511, 3884, 2896, 3923, 3930, 6492, 2917, 6502, 7020, 2926, 9079, 8578, 7566, 3983, 8087, 10659, 1459, 15285, 756, 3305, 3520, 7105, 1495, 481, 5612, 3154, 6131, 3242]))]\n",
      "Cantidad de vecinos de Kevin Bacon: 101\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "# First we convert each (A,B) into (A,B) and (B,A)\n",
    "adjlist = network.flatMap(lambda x:[(x[0],x[1]),(x[1],x[0])])\n",
    "\n",
    "# veamos especificamente que pasa con Kevin Bacon\n",
    "# uso de set para evitar duplicados, etc.\n",
    "kadj = adjlist.groupByKey()\\\n",
    "             .filter(lambda x:x[0]==KEVIN_BACON_ID)\\\n",
    "             .map(lambda x:(x[0],(set(x[1]))))\n",
    "\n",
    "kadj_driver = kadj.take(1)\n",
    "\n",
    "print kadj_driver\n",
    "\n",
    "print 'Cantidad de vecinos de Kevin Bacon: ' + str(len(kadj_driver[0][1]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Llevando a la representacion necesaria para calcular los Bacon Numbers "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numero total de nodos en nuestro grafo: 17577\n"
     ]
    }
   ],
   "source": [
    "# Usando groupByKey tenemos toda la informacion para poder armar la lista de adyacencia\n",
    "# usando un set oara eliminar los duplicados.\n",
    "# Inicializamos la distancia como infinito con 999\n",
    "# status en -\n",
    "# la lista de vecinos de ese nodo\n",
    "# trace en 0\n",
    "adjlist = adjlist.groupByKey()\\\n",
    "                 .map(\n",
    "        lambda x:(x[0],(999,'-',list(set(x[1])),0)))\\\n",
    "                .cache()\n",
    "\n",
    "total_nodes = adjlist.count()\n",
    "print \"Numero total de nodos en nuestro grafo: \" + str(total_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, (999, '-', [1, 2, 3, 4, 8, 10, 25, 28], 0)), (2, (999, '-', [0, 1, 3, 11, 12, 17, 18, 19, 12182, 1049, 25, 27, 28, 31, 33, 16418, 41, 15791, 50, 16693, 56, 57, 16701, 15294, 15296, 15297, 15298, 15300, 15303], 0))]\n"
     ]
    }
   ],
   "source": [
    "# Nuestro RDD ahora tiene la forma [(node,(distance_from_kevin,status,[neighbors], trace)),....(node,(distance_from_kevin,status,[neighbors], trace))]\n",
    "print adjlist.take(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# El siguiente paso es marcar todos los nodos que son vecinos de Kevin Bacon como: \n",
    "#    1. a distancia 1\n",
    "#    2. y como procesados en el status con 'P'\n",
    "# Para hacer esto tomamos el nodo de Kevin Bacon y \n",
    "# generamos nuevos nodos para los vecinos de la forma\n",
    "# (node_id,(1,'P',[])).\n",
    "# Luego en la fase de reduceByKey vamos a hacer un join de todos los nodos en uno unico (esperemos!)\n",
    "\n",
    "# Para hacer esto definimos la funcion proc_node \n",
    "# como la funcion que procesa un nodo \n",
    "# y vamos a comenzar el procesamiento desde \n",
    "# KEVIN_BACON_ID (Kevin Bacon)\n",
    "def proc_node(node):\n",
    "    # Recibimos un nodo de la forma \n",
    "    #(nodeid, distance_from_kevin, status, \n",
    "    # list_of_neighbors, trace)\n",
    "    # Generamos nuevos nodos para cada \n",
    "    #vecino agregando 1 a la distancia del nodo actual (!)\n",
    "    if node[1][0]==999:        new_distance = 1\n",
    "    else:\n",
    "        new_distance = node[1][0]+1\n",
    "    ret = []\n",
    "    for neighbor in node[1][2]:\n",
    "        ret.append((neighbor,(new_distance,'P',[],node[0])))\n",
    "    # We also update the node as already processed!\n",
    "    ret.append((node[0],(node[1][0],'DONE',node[1][2],node[1][3])))\n",
    "    return ret\n",
    "\n",
    "# Definimos la funcion de reduccion\n",
    "def reduce_nodes(n1,n2):\n",
    "    # Recibimos dos nodos de la forma \n",
    "    # (distance_from_kevin,status,list_of_neighbors,trace) \n",
    "    # No quedamos con la distancia minima\n",
    "    # si uno de los nodos esta marcado como \n",
    "    # 'DONE' nos quedamos con 'DONE'\n",
    "    # si uno de los nodos esta marcado \n",
    "    # como 'P' nos quedamos con 'P'\n",
    "    # nos quedamos con la lista \n",
    "    # mas larga de vecinos (alguna podria estar vacia)\n",
    "    # Mantenemos un trace de la minima distancia\n",
    "    new_status = ''\n",
    "    if n1[1]=='P' or n2[1]=='P':\n",
    "        new_status = 'P'\n",
    "    if n1[1]=='DONE' or n2[1]=='DONE':\n",
    "        new_status = 'DONE'\n",
    "    if n1[0]<n2[0]:\n",
    "        new_distance = n1[0]\n",
    "        trace = n1[3]\n",
    "    else:\n",
    "        new_distance = n2[0]\n",
    "        trace = n2[3]\n",
    "    new_list = n1[2]\n",
    "    if len(n2[2])>len(n1[2]):\n",
    "        new_list = n2[2]\n",
    "    return (new_distance,new_status,new_list,trace)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Primera Pasada\n",
    "\n",
    "Procesamos inicialmente solo el nodo de Kevin Bacon. Luego de esta Primera pasada deberiamos obtener solamente 101 con Bacon Numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Primera Pasada: Nuestra primer tarea es procesar solo el nodo de Kevin Bacon (KEVIN_BACON_ID)\n",
    "adjlist = adjlist.flatMap(\n",
    "    lambda x:proc_node(x) if x[0]==KEVIN_BACON_ID else [x])\n",
    "adjlist = adjlist.reduceByKey(reduce_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numero de nodos con Bacon Number: 101/17577\n"
     ]
    }
   ],
   "source": [
    "# calculamos cuantos luego de la primer pasada tienen el bacon number\n",
    "# estos serian los que estan a un grado de separacion\n",
    "# y por lo que comprobamos anteriormente deberian ser 101\n",
    "def bn_stats(adjlist,total_nodes):\n",
    "    k_with_number = adjlist.filter(lambda x:x[1][0]<999)\n",
    "    print \"Numero de nodos con Bacon Number: \" + str(k_with_number.count()) + \"/\" + str(total_nodes)\n",
    "\n",
    "bn_stats(adjlist,total_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algunos Actores with Bacon Numbers\n",
      "\"Danes, Claire\"\n",
      "\"Wilson, Luke (I)\"\n",
      "\"Taylor, Elizabeth (I)\"\n",
      "\"Hoffman, Dustin\"\n",
      "\"Harris, Ed (I)\"\n",
      "\"Pollak, Kevin\"\n",
      "\"Danson, Ted\"\n",
      "\"Sinise, Gary\"\n",
      "\"Hanks, Tom\"\n",
      "\"Bisset, Jacqueline\"\n",
      "\"Ice-T\"\n",
      "\"Harden, Marcia Gay\"\n",
      "\"Grant, Hugh (I)\"\n",
      "\"Bonham Carter, Helena\"\n",
      "\"Jackson, Janet (I)\"\n",
      "\"Ford, Harrison (I)\"\n",
      "\"Shue, Elisabeth\"\n",
      "\"Jolie, Angelina\"\n",
      "\"Gere, Richard\"\n",
      "\"Moore, Demi\"\n"
     ]
    }
   ],
   "source": [
    "def some_with_bacon_numbers(adjlist, degree): \n",
    "    print \"Algunos Actores with Bacon Numbers\"\n",
    "    kb_1_names = adjlist.filter(lambda x:x[1][0]==degree)\\\n",
    "                         .map(lambda x:(x[0],1))\\\n",
    "                         .join(actors_key)\\\n",
    "                         .map(lambda x:x[1][1])\\\n",
    "\n",
    "    for name in kb_1_names.take(20):\n",
    "        print name\n",
    "\n",
    "some_with_bacon_numbers(adjlist,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Segunda Pasada\n",
    "\n",
    "Nuestro segundo paso consiste en procesar todos aquellos nodos con status 'P'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numero de nodos con Bacon Number: 2491/17577\n",
      "Algunos Actores with Bacon Numbers\n",
      "\"Chaynes, Allysin\"\n",
      "\"DaBone, Dale\"\n",
      "\"Plimpton, George\"\n",
      "\"Carrera, Asia\"\n",
      "\"Watanabe, Gedde\"\n",
      "\"O&apos;Connor, Jeanette\"\n",
      "\"Steele, Lexington\"\n",
      "\"Savage, Herschel\"\n",
      "\"Gibson, Deborah (I)\"\n",
      "\"Roth, Tim\"\n",
      "\"Weaving, Hugo\"\n",
      "\"Whedon, Joss\"\n",
      "\"Loftin, Lennie\"\n",
      "\"Kinnear, Greg\"\n",
      "\"Hackman, Gene\"\n",
      "\"Livingston, Ron\"\n",
      "\"Garity, Troy\"\n",
      "\"Fischler, Patrick\"\n",
      "\"Berkeley, Xander\"\n",
      "\"Gage, Kevin\"\n"
     ]
    }
   ],
   "source": [
    "# Nuestro siguiente paso consiste en procesar todos los nodos con status 'P'\n",
    "adjlist = adjlist.flatMap(\n",
    "    lambda x:proc_node(x) if x[1][1]=='P' else [x])\n",
    "adjlist = adjlist.reduceByKey(reduce_nodes)\n",
    "\n",
    "bn_stats(adjlist,total_nodes)\n",
    "some_with_bacon_numbers(adjlist,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Siguientes N-Pasadas Iterativas\n",
    "\n",
    "Seguimos procesando entonces los nodos que estan en status 'P' hasta que no queden mas por procesar o no puedan procesarse mas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numero de nodos con Bacon Number: 9650/17577\n",
      "Numero de nodos con Bacon Number: 14463/17577\n",
      "Numero de nodos con Bacon Number: 16459/17577\n",
      "Numero de nodos con Bacon Number: 16951/17577\n",
      "Numero de nodos con Bacon Number: 17270/17577\n",
      "Numero de nodos con Bacon Number: 17445/17577\n",
      "Numero de nodos con Bacon Number: 17455/17577\n",
      "Numero de nodos con Bacon Number: 17455/17577\n",
      "Numero de nodos con Bacon Number: 17455/17577\n",
      "Numero de nodos con Bacon Number: 17455/17577\n"
     ]
    }
   ],
   "source": [
    "for i in range(0,10):\n",
    "    adjlist = adjlist.flatMap(\n",
    "        lambda x:proc_node(x) if x[1][1]=='P' else [x])\n",
    "    adjlist = adjlist.reduceByKey(reduce_nodes)\n",
    "    bn_stats(adjlist, total_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algunas verificaciones notables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(5222, u'\"Francella, Guillermo\"', 5)]\n",
      "[(5224, u'\"Brandoni, Luis\"', 4)]\n",
      "[(4763, u'\"Pauls, Gast\\ufffdn\"', 3)]\n"
     ]
    }
   ],
   "source": [
    "# Francella, Guillermo (5222)\n",
    "print adjlist.filter(lambda x:x[0]==5222).join(actors_key_cat).map(lambda x: (x[0],x[1][1][0],x[1][0][0])).collect()\n",
    "# Luis Brandoni (5223)\n",
    "print adjlist.filter(lambda x:x[0]==5224).join(actors_key_cat).map(lambda x: (x[0],x[1][1][0],x[1][0][0])).collect()\n",
    "# Gaston Pauls (4763)\n",
    "print adjlist.filter(lambda x:x[0]==4763).join(actors_key_cat).map(lambda x: (x[0],x[1][1][0],x[1][0][0])).collect()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resumen: Caminos minimos desde un nodo\n",
    "\n",
    "- **Usamos una estructura de nodo de lista de adyacencia con algunas variables extras para ayudar al procesamiento.**\n",
    "    - (node_id, (distance, status, [list of neighbors]))\n",
    "- **El estado inicial es solo con el nodo inicio en status ‘P’ y distancia 0.**\n",
    "- **El resto de los nodos status ‘-’ y distancia Infinita (999) con nodos que vamos a tener que procesar.**\n",
    "- El algoritmo es iterativo, por lo que en cada iteracion hacemos:\n",
    "    - Por cada nodo marcado como 'P' procesamos sus vecinos\n",
    "    - Por cada vecino generamos un nuevo nodo de la forma (node_id, (distance+1,'P',[]))\n",
    "    - Luego en la fase de reduce nos quedaremos la distancia mínima y la lista de vecinos (alguno de los nodos la tiene)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random Walks\n",
    "\n",
    "Concepto a ser desarrollado mas adelante en la materia, en particular para comprender PageRank (Teletransportacion!).\n",
    "\n",
    "**Idea Base: Comenzar en uno o varios nodos al azar y en cada paso movernos a un nodo vecino de forma aleatoria.**\n",
    "\n",
    "Los random walks tienen muchísimas aplicaciones.\n",
    "\n",
    "- Determinar la centralidad (importancia) de nodos o aristas\n",
    "- Encontrar nodos parecidos a otros\n",
    "- Detectar clusters / comunidades\n",
    "- Sistemas de Recomendaciones\n",
    "\n",
    "### En Spark\n",
    "\n",
    "Comenzar con un conjunto de nodos al azar.\n",
    "\n",
    "- Por cada nodo elegir un vecino al azar y agregarlo a los resultados.\n",
    "- Repetir este proceso “n” veces (longitud de los Random Walks)\n",
    "- Observación: La cantidad de random walks es constante pero cada random walk tiene un nodo nuevo en cada iteración"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Centralidad (Importancia) de Nodos Utilizando Random Walks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, [1, 2, 3, 4, 8, 10, 25, 28])]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Centrality by Random Walks!\n",
    "# Select some random nodes from the graph\n",
    "# From those nodes start a random walk\n",
    "# Then just compute 1 for each node we have found!\n",
    "import numpy as np\n",
    "\n",
    "# llevamos la representacion que usamos para los bacon numbers \n",
    "# a una tipica representacion de lista de adyacencia\n",
    "graph = network.flatMap(lambda x:[(x[0],x[1]),(x[1],x[0])])\\\n",
    "               .groupByKey()\\\n",
    "               .map(lambda x: (x[0], list(set(x[1]))))\\\n",
    "               .cache()\n",
    "graph.take(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5229\n"
     ]
    }
   ],
   "source": [
    "# Como primer paso tomamos una muestra aleatoria con reemplazo\n",
    "my_sample = graph.sample(True, 0.3)\n",
    "\n",
    "print my_sample.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tomamos una muestra de: 5229 nodos\n"
     ]
    }
   ],
   "source": [
    "# todos los nodos seleccionados son parte de los random walks\n",
    "all_the_nodes = my_sample.map(lambda x:(x[0],1))\n",
    "\n",
    "print \"Tomamos una muestra de: \"+ str(my_sample.count()) + \" nodos\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round: 0 Total number of nodes:10458\n",
      "Round: 1 Total number of nodes:15687\n",
      "Round: 2 Total number of nodes:20916\n",
      "Round: 3 Total number of nodes:26145\n",
      "Round: 4 Total number of nodes:31374\n",
      "Round: 5 Total number of nodes:36603\n",
      "Round: 6 Total number of nodes:41832\n",
      "Round: 7 Total number of nodes:47061\n",
      "Round: 8 Total number of nodes:52290\n",
      "Round: 9 Total number of nodes:57519\n",
      "----------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "# Esta funcion toma un nodo y retorna un nuevo nodo seleccionando un random neighbor\n",
    "# De cada nodo en la muestra seleccionar un random neighbor\n",
    "def pick_random_neighbor(node):\n",
    "    neighbor = np.random.choice(node[1])\n",
    "    return (neighbor,'node')\n",
    "\n",
    "for i in range(0,10):\n",
    "    # Seleccionar un random neighbor de cada nodo\n",
    "    my_sample = my_sample.map(lambda x:pick_random_neighbor(x)).cache()\n",
    "    # hace un join con grafo para obtener una lista de vecinos\n",
    "    my_sample = my_sample.join(graph).map(lambda x:(x[0],x[1][1])).cache()\n",
    "    # adicionar lo nuevos nodos a la lista de nodos visitados\n",
    "    just_nodes = my_sample.map(lambda x:(x[0],1))\n",
    "    all_the_nodes = all_the_nodes.union(just_nodes).cache()\n",
    "    print \"Round: \"+str(i)+\" Total number of nodes:\"+str(all_the_nodes.count())\n",
    "print \"----------------------------------------------------------------------\"    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, (2, (u'\"Tordy, G\\ufffdza\"', u'Comedy'))), (1540, (1, (u'\"Stanicheva, Marianne\"', u'Action'))), (3080, (10, (u'\"Hoger, Nina\"', u'Drama'))), (4620, (4, (u'\"Neuhauser, Adele\"', u'Crime'))), (6160, (1, (u'\"De Souza, Rodolfo\"', u'Drama')))]\n"
     ]
    }
   ],
   "source": [
    "all_the_nodes = all_the_nodes.reduceByKey(lambda x,y:x+y)\n",
    "nodes_with_names = all_the_nodes.join(actors_key_cat)\n",
    "print nodes_with_names.take(5)\n",
    "central_actors =  nodes_with_names.takeOrdered(50,lambda x:-x[1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1. \"Goldberg, Whoopi\" (Comedy) = 48\n",
      "2. \"Berl�and, Fran�ois\" (Drama) = 43\n",
      "3. \"Baldwin, Alec\" (Comedy) = 40\n",
      "4. \"Jackson, Samuel L.\" (Drama) = 40\n",
      "5. \"Diaz, Cameron\" (Drama) = 37\n",
      "6. \"Stiller, Ben\" (Comedy) = 35\n",
      "7. \"Lopez, Jennifer (I)\" (Music) = 34\n",
      "8. \"Davis, Mark (V)\" (Adult) = 34\n",
      "9. \"Parker, Sarah Jessica\" (Music) = 34\n",
      "10. \"Hanks, Tom\" (Family) = 32\n",
      "11. \"Berry, Halle\" (Family) = 31\n",
      "12. \"Madonna (I)\" (Music) = 30\n",
      "13. \"Williams, Robin (I)\" (Comedy) = 30\n",
      "14. \"Hopper, Dennis\" (Music) = 29\n",
      "15. \"Crystal, Billy\" (Comedy) = 29\n",
      "16. \"Ferrell, Will\" (Comedy) = 29\n",
      "17. \"Carrey, Jim\" (Family) = 28\n",
      "18. \"Hoffman, Dustin\" (Thriller) = 28\n",
      "19. \"Smith, Will (I)\" (Music) = 28\n",
      "20. \"Cruise, Tom\" (Music) = 28\n",
      "21. \"Brazeau, Jay\" (Drama) = 28\n",
      "22. \"Douglas, Michael (I)\" (Family) = 28\n",
      "23. \"Stone, Sharon (I)\" (Family) = 28\n",
      "24. \"Morel, Fran�ois (I)\" (Comedy) = 27\n",
      "25. \"Jeremy, Ron\" (Adult) = 27\n",
      "26. \"Cannon, Chris (III)\" (Adult) = 27\n",
      "27. \"Walken, Christopher\" (Comedy) = 27\n",
      "28. \"Fry, Stephen\" (Comedy) = 26\n",
      "29. \"Lawrence, Joel (II)\" (Adult) = 26\n",
      "30. \"Sanders, Alex (I)\" (Adult) = 26\n",
      "31. \"Dogg, Snoop\" (Music) = 26\n",
      "32. \"Myers, Mike (I)\" (Comedy) = 26\n",
      "33. \"Tedeschi, Tony\" (Adult) = 26\n",
      "34. \"Fischer, Ottfried\" (Crime) = 25\n",
      "35. \"Kidman, Nicole\" (Family) = 25\n",
      "36. \"Barrymore, Drew\" (Drama) = 25\n",
      "37. \"Voyeur, Vince\" (Adult) = 25\n",
      "38. \"Schwarz, Jaecki\" (Crime) = 25\n",
      "39. \"Cher (I)\" (Music) = 25\n",
      "40. \"Harrelson, Woody\" (Comedy) = 25\n",
      "41. \"Brialy, Jean-Claude\" (Comedy) = 25\n",
      "42. \"Pete, Mr.\" (Adult) = 24\n",
      "43. \"Travolta, John\" (Drama) = 24\n",
      "44. \"Clinton, Bill\" (Music) = 24\n",
      "45. \"Bennett, Jeff (I)\" (Family) = 24\n",
      "46. \"Ford, Harrison (I)\" (Thriller) = 24\n",
      "47. \"Welker, Frank\" (Family) = 24\n",
      "48. \"Soucie, Kath\" (Family) = 24\n",
      "49. \"Sarandon, Susan\" (Drama) = 24\n",
      "50. \"Osugi, Ren\" (Drama) = 24\n"
     ]
    }
   ],
   "source": [
    "i=0\n",
    "for actor in central_actors:\n",
    "    i=i+1\n",
    "    print str(i)+\". \"+actor[1][1][0]+\" (\"+actor[1][1][1]+\") = \"+str(actor[1][0])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15rc1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}