example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Weighted spectral embedding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an example of the weighted spectral embedding of a graph, using unit weights or internal node weights (node degrees for an unweighted graph)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from spectral_embedding import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "spectral = SpectralEmbedding()\n",
    "weighted_spectral = SpectralEmbedding(node_weights = 'degree')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Toy example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph = nx.karate_club_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ground_truth_labels = list(nx.get_node_attributes(graph, 'club').values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "adjacency = nx.to_scipy_sparse_matrix(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Embeddings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<spectral_embedding.SpectralEmbedding at 0x1a20ebb048>"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spectral.fit(adjacency)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<spectral_embedding.SpectralEmbedding at 0x1a20ebb550>"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weighted_spectral.fit(adjacency)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "embedding = spectral.embedding_\n",
    "weighted_embedding = weighted_spectral.embedding_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "normalized_embedding = (embedding.T / np.linalg.norm(embedding,axis = 1)).T\n",
    "normalized_weighted_embedding = (weighted_embedding.T / np.linalg.norm(weighted_embedding,axis = 1)).T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clusterings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n_clusters = 2\n",
    "kmeans = KMeans(n_clusters)\n",
    "kmeans.fit(embedding)\n",
    "labels = list(kmeans.labels_)\n",
    "kmeans.fit(normalized_embedding)\n",
    "normalized_labels = list(kmeans.labels_)\n",
    "kmeans.fit(weighted_embedding)\n",
    "weighted_labels = list(kmeans.labels_)\n",
    "kmeans.fit(normalized_weighted_embedding)\n",
    "normalized_weighted_labels = list(kmeans.labels_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'Mr. Hi': 17, 'Officer': 17})"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Ground truth\n",
    "Counter(ground_truth_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Counter({0: 19, 1: 15}), Counter({0: 18, 1: 16}))"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Spectral embedding\n",
    "Counter(labels), Counter(normalized_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Counter({0: 15, 1: 19}), Counter({0: 16, 1: 18}))"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Weighted spectral embedding\n",
    "Counter(weighted_labels), Counter(normalized_weighted_labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import urllib.request\n",
    "\n",
    "url = \"http://perso.telecom-paristech.fr/~bonald/graphs/\"\n",
    "dataset = \"openflights.graphml.gz\"\n",
    "download = urllib.request.urlretrieve(url + dataset, dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Name: Openflights\n",
      "Type: Graph\n",
      "Number of nodes: 3097\n",
      "Number of edges: 18193\n",
      "Average degree:  11.7488\n"
     ]
    }
   ],
   "source": [
    "graph = nx.read_graphml(dataset, node_type=int)\n",
    "print(nx.info(graph))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "adjacency = nx.to_scipy_sparse_matrix(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Embeddings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<spectral_embedding.SpectralEmbedding at 0x1a20ee1588>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spectral.fit(adjacency)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<spectral_embedding.SpectralEmbedding at 0x1a20ee1550>"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weighted_spectral.fit(adjacency)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "embedding = spectral.embedding_\n",
    "weighted_embedding = weighted_spectral.embedding_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "normalized_embedding = (embedding.T / np.linalg.norm(embedding,axis = 1)).T\n",
    "normalized_weighted_embedding = (weighted_embedding.T / np.linalg.norm(weighted_embedding,axis = 1)).T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clusterings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n_clusters = 10\n",
    "kmeans = KMeans(n_clusters)\n",
    "kmeans.fit(embedding)\n",
    "labels = list(kmeans.labels_)\n",
    "kmeans.fit(normalized_embedding)\n",
    "normalized_labels = list(kmeans.labels_)\n",
    "kmeans.fit(weighted_embedding)\n",
    "weighted_labels = list(kmeans.labels_)\n",
    "kmeans.fit(normalized_weighted_embedding)\n",
    "normalized_weighted_labels = list(kmeans.labels_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 2985, 1: 3, 2: 5, 3: 18, 4: 30, 5: 3, 6: 26, 7: 4, 8: 21, 9: 2})"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 67,\n",
       "         1: 947,\n",
       "         2: 92,\n",
       "         3: 96,\n",
       "         4: 585,\n",
       "         5: 111,\n",
       "         6: 135,\n",
       "         7: 149,\n",
       "         8: 454,\n",
       "         9: 461})"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(normalized_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 2965, 1: 2, 2: 26, 3: 21, 4: 3, 5: 21, 6: 30, 7: 11, 8: 3, 9: 15})"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(weighted_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 639,\n",
       "         1: 595,\n",
       "         2: 154,\n",
       "         3: 214,\n",
       "         4: 525,\n",
       "         5: 253,\n",
       "         6: 307,\n",
       "         7: 140,\n",
       "         8: 106,\n",
       "         9: 164})"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(normalized_weighted_labels)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "hide_input": false,
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}