voteRank.ipynb

VoteRank.ipynb

{
  "cells": [
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-02-15T12:12:18.123537",
          "end_time": "2017-02-15T12:12:18.770430"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "# -*- coding: utf-8 -*-\n#\n#   Copyright (C) 2017 by\n#   Fredrik Erlandsson <[email protected]>\n#   All rights reserved.\n#   BSD license.\n\"\"\"Algorithm to compute influetial seeds in a graph using voterank.\"\"\"\n\nimport networkx as nx\n\n__all__ = ['voterank']\n__author__ = \"\"\"\\n\"\"\".join(['Fredrik Erlandsson <[email protected]>'])\n\n\ndef voterank(graph, num_seeds=3):\n    r\"\"\"Compute a list of seeds for the nodes in the graph using VoteRank [1]_.\n    \n    Parameters\n    ----------\n    graph : NetworkX graph\n\n    num:_seeds : integer\n        Number of seeds to extract (default 3).\n\n    Returns\n    -------\n    seeds : list\n        Ordered list of computed seeds.\n\n\n    References\n    ----------\n    .. [1] Zhang, J.-X. et al. (2016).\n        Identifying a set of influential spreaders in complex networks.\n        Sci. Rep. 6, 27823; doi: 10.1038/srep27823 .\n    \"\"\"\n    seeds = list()\n    avgDegree = sum(graph.degree().values()) / float(graph.number_of_nodes())\n    print avgDegree\n    # step 1 - initiate all nodes to (0,1)\n    for n in graph:\n        graph.node[n]['voterank'] = [0, 1]\n    while True:\n        # step 1b (not sure this is needed, the Fig.1 and the Algo is unclear)\n        for n in graph:\n            graph.node[n]['voterank'][0] = 0\n        # step 2 - vote\n        for n in graph:\n            for nbr in graph.neighbors_iter(n):\n                if nbr in seeds:\n                    continue  # don't update an already selected seed\n                graph.node[nbr]['voterank'][0] += graph.node[n]['voterank'][1]\n        print graph.nodes(data=True)\n        # step 3 - select top node\n        n, value = max(graph.nodes_iter(data=True),\n                       key=lambda x: x[1]['voterank'][0])\n        print \"Selected node:\", n, value  # , key\n        seeds.append(n)\n        # weaken the selected node\n        graph.node[n]['voterank'] = [0, 0]\n        # step 4 - update voterank properties\n        for nbr in graph.neighbors_iter(n):\n            graph.node[nbr]['voterank'][1] -= 1 / avgDegree\n        print graph.nodes(data=True)\n        # step 5 - Repeat steps 2 to 4 until num_seeds are elected.\n        if len(seeds) >= num_seeds:\n            print seeds, num_seeds\n            return seeds",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "ExecuteTime": {
          "start_time": "2017-02-15T12:12:18.772612",
          "end_time": "2017-02-15T12:12:18.812391"
        },
        "collapsed": false
      },
      "cell_type": "code",
      "source": "testNet = nx.Graph()\ntestNet.add_edges_from([(7, 8), (7, 5), (7, 9), (5, 0), (0, 1), (0, 2), (0, 3),\n                        (0, 4), (1, 6), (2, 6), (3, 6), (4, 6)])\nvoterank(testNet)",
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": "2.4\n[(0, {'voterank': [5, 1]}), (1, {'voterank': [2, 1]}), (2, {'voterank': [2, 1]}), (3, {'voterank': [2, 1]}), (4, {'voterank': [2, 1]}), (5, {'voterank': [2, 1]}), (6, {'voterank': [4, 1]}), (7, {'voterank': [3, 1]}), (8, {'voterank': [1, 1]}), (9, {'voterank': [1, 1]})]\nSelected node: 0 {'voterank': [5, 1]}\n[(0, {'voterank': [0, 0]}), (1, {'voterank': [2, 0.5833333333333333]}), (2, {'voterank': [2, 0.5833333333333333]}), (3, {'voterank': [2, 0.5833333333333333]}), (4, {'voterank': [2, 0.5833333333333333]}), (5, {'voterank': [2, 0.5833333333333333]}), (6, {'voterank': [4, 1]}), (7, {'voterank': [3, 1]}), (8, {'voterank': [1, 1]}), (9, {'voterank': [1, 1]})]\n[(0, {'voterank': [0, 0]}), (1, {'voterank': [1, 0.5833333333333333]}), (2, {'voterank': [1, 0.5833333333333333]}), (3, {'voterank': [1, 0.5833333333333333]}), (4, {'voterank': [1, 0.5833333333333333]}), (5, {'voterank': [1, 0.5833333333333333]}), (6, {'voterank': [2.333333333333333, 1]}), (7, {'voterank': [2.583333333333333, 1]}), (8, {'voterank': [1, 1]}), (9, {'voterank': [1, 1]})]\nSelected node: 7 {'voterank': [2.583333333333333, 1]}\n[(0, {'voterank': [0, 0]}), (1, {'voterank': [1, 0.5833333333333333]}), (2, {'voterank': [1, 0.5833333333333333]}), (3, {'voterank': [1, 0.5833333333333333]}), (4, {'voterank': [1, 0.5833333333333333]}), (5, {'voterank': [1, 0.16666666666666657]}), (6, {'voterank': [2.333333333333333, 1]}), (7, {'voterank': [0, 0]}), (8, {'voterank': [1, 0.5833333333333333]}), (9, {'voterank': [1, 0.5833333333333333]})]\n[(0, {'voterank': [0, 0]}), (1, {'voterank': [1, 0.5833333333333333]}), (2, {'voterank': [1, 0.5833333333333333]}), (3, {'voterank': [1, 0.5833333333333333]}), (4, {'voterank': [1, 0.5833333333333333]}), (5, {'voterank': [0, 0.16666666666666657]}), (6, {'voterank': [2.333333333333333, 1]}), (7, {'voterank': [0, 0]}), (8, {'voterank': [0, 0.5833333333333333]}), (9, {'voterank': [0, 0.5833333333333333]})]\nSelected node: 6 {'voterank': [2.333333333333333, 1]}\n[(0, {'voterank': [0, 0]}), (1, {'voterank': [1, 0.16666666666666657]}), (2, {'voterank': [1, 0.16666666666666657]}), (3, {'voterank': [1, 0.16666666666666657]}), (4, {'voterank': [1, 0.16666666666666657]}), (5, {'voterank': [0, 0.16666666666666657]}), (6, {'voterank': [0, 0]}), (7, {'voterank': [0, 0]}), (8, {'voterank': [0, 0.5833333333333333]}), (9, {'voterank': [0, 0.5833333333333333]})]\n[0, 7, 6] 3\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "[0, 7, 6]"
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    }
  ],
  "metadata": {
    "language_info": {
      "version": "2.7.12",
      "name": "python",
      "file_extension": ".py",
      "codemirror_mode": {
        "version": 2,
        "name": "ipython"
      },
      "pygments_lexer": "ipython2",
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python"
    },
    "kernelspec": {
      "name": "conda-env-py2-py",
      "display_name": "Python [conda env:py2]",
      "language": "python"
    },
    "gist": {
      "id": "d44800ddf90c3d8757d725ac3b508331",
      "data": {
        "description": "voteRank.ipynb",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/d44800ddf90c3d8757d725ac3b508331"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}