05_graphs_as_matrices_1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#The goal of the exercise is to show that the number of components in a graph is equal to the number of eigen values =1\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = nx.read_edgelist(\"data/protein.txt\", delimiter='\\t')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "185\n"
     ]
    }
   ],
   "source": [
    "#Print the number of components of g using networkx function\n",
    "num_comp = nx.number_connected_components(g)\n",
    "print(num_comp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "185\n"
     ]
    }
   ],
   "source": [
    "#Let's find the eigen values and count how many of them is equal to 1\n",
    "\n",
    "#1- Get the adjacency matrix representation of your graph\n",
    "adj_mat = nx.to_numpy_matrix(g)\n",
    "\n",
    "#2- Row-normalize the adjacency matrix so you get the stochastic matrix\n",
    "adj_mat = adj_mat/adj_mat.sum(axis=1)\n",
    "\n",
    "#3- Compute the eigen vectors, and the eigen values of the adjacency matrix\n",
    "eig_values, eig_vectors = np.linalg.eig(adj_mat)\n",
    "\n",
    "#4- Count the number of eigen values equal to 1  (practically >=.99)\n",
    "print((np.real(eig_values) >=.99).sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print((np.real(eig_values) >=.99).sum() == num_comp)"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

05_graphs_as_matrices_2.ipynb

05_graphs_as_matrices_3.ipynb