JuliaImplementation.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "using LightGraphs, GraphIO\n",
        "using TimerOutputs\n",
        "using StatsBase"
      ],
      "outputs": [],
      "execution_count": 32,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:14:40.444Z",
          "iopub.execute_input": "2020-07-18T14:14:40.448Z",
          "iopub.status.idle": "2020-07-18T14:14:40.456Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "const to = TimerOutput()\n",
        "dir = \"input_files\"\n",
        "input_files = filter(x -> isfile(joinpath(dir, x)), readdir(dir))"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "WARNING: redefining constant to\n"
          ]
        },
        {
          "output_type": "execute_result",
          "execution_count": 33,
          "data": {
            "text/plain": "6-element Array{String,1}:\n \"airtc.txt\"\n \"dolphins.txt\"\n \"facebook_combined.txt\"\n \"karateclub.txt\"\n \"lesmis.txt\"\n \"mcldata.txt\""
          },
          "metadata": {}
        }
      ],
      "execution_count": 33,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:14:40.704Z",
          "iopub.execute_input": "2020-07-18T14:14:40.708Z",
          "iopub.status.idle": "2020-07-18T14:14:40.723Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "function label_partition(g; k=8)\n",
        "  unlabeled_nodes = Set(vertices(g));\n",
        "  labeled_nodes = Set();\n",
        "  finished_nodes = Set();\n",
        "  labels = zeros(Int, nv(g));\n",
        "  random_k_nodes = sample(vertices(g), k, replace=false);\n",
        "  for (i, r) in enumerate(random_k_nodes)\n",
        "    labels[r] = i;\n",
        "    unlabeled_nodes = delete!(unlabeled_nodes, r)\n",
        "    labeled_nodes = push!(labeled_nodes, r)\n",
        "  end\n",
        "  \n",
        "  operations = 0\n",
        "  while !isempty(unlabeled_nodes)\n",
        "    for n in copy(labeled_nodes)\n",
        "      n_neighbors = setdiff(Set(neighbors(g, n)), union(labeled_nodes, finished_nodes))\n",
        "      operations += 1\n",
        "      if !isempty(n_neighbors)\n",
        "        neighbor = sample(collect(n_neighbors), 1)[1];\n",
        "        labels[neighbor] = labels[n];\n",
        "        unlabeled_nodes = delete!(unlabeled_nodes, neighbor);\n",
        "        labeled_nodes = push!(labeled_nodes, neighbor);\n",
        "        n_neighbors = delete!(n_neighbors, neighbor);\n",
        "      end\n",
        "      if isempty(n_neighbors)\n",
        "        labeled_nodes = delete!(labeled_nodes, n);\n",
        "        finished_nodes = push!(finished_nodes, n);\n",
        "      end\n",
        "    end\n",
        "  end\n",
        "  return labels\n",
        "end\n",
        "\n",
        "function graph_partition(g; k=8, c=10)\n",
        "  best_partition = []\n",
        "  best_modularity = -Inf\n",
        "  for i in 1:c\n",
        "    partitions = label_partition(g; k=k)\n",
        "    partition_modularity = modularity(g, partitions)\n",
        "#     println(partition_modularity)\n",
        "    if (best_modularity < partition_modularity)\n",
        "      best_partition = partitions\n",
        "      best_modularity = partition_modularity\n",
        "    end\n",
        "  end\n",
        "  return best_partition, best_modularity\n",
        "end"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 54,
          "data": {
            "text/plain": "graph_partition (generic function with 1 method)"
          },
          "metadata": {}
        }
      ],
      "execution_count": 54,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:37:29.621Z",
          "iopub.execute_input": "2020-07-18T14:37:29.626Z",
          "iopub.status.idle": "2020-07-18T14:37:29.638Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "filename = joinpath(dir, input_files[2])\n",
        "println(filename)\n",
        "g = SimpleGraph(loadgraph(filename, \"graph\", GraphIO.EdgeList.EdgeListFormat()))"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "input_files\\dolphins.txt\n"
          ]
        },
        {
          "output_type": "execute_result",
          "execution_count": 51,
          "data": {
            "text/plain": "{62, 159} undirected simple Int64 graph"
          },
          "metadata": {}
        }
      ],
      "execution_count": 51,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:36:14.405Z",
          "iopub.execute_input": "2020-07-18T14:36:14.409Z",
          "iopub.status.idle": "2020-07-18T14:36:14.421Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "best_modularity = -Inf\n",
        "best_k = 0\n",
        "for k in 2:15\n",
        "  @timeit to filename part, modu = graph_partition(g; k=k, c=25)\n",
        "  if (best_modularity < modu)\n",
        "    best_modularity = modu\n",
        "    best_k = k\n",
        "  end\n",
        "end\n",
        "round(best_modularity, digits=4), best_k"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 42,
          "data": {
            "text/plain": "(0.365, 4)"
          },
          "metadata": {}
        }
      ],
      "execution_count": 42,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:15:44.474Z",
          "iopub.execute_input": "2020-07-18T14:15:44.480Z",
          "iopub.status.idle": "2020-07-18T14:15:44.901Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "@timeit to filename part, modu = graph_partition(g; k=8, c=25)"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 55,
          "data": {
            "text/plain": "([7, 4, 4, 1, 1, 4, 7, 6, 4, 3  …  1, 7, 5, 3, 4, 4, 5, 3, 4, 7], 0.38036470076341916)"
          },
          "metadata": {}
        }
      ],
      "execution_count": 55,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:37:32.473Z",
          "iopub.execute_input": "2020-07-18T14:37:32.479Z",
          "iopub.status.idle": "2020-07-18T14:37:32.542Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "to"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 44,
          "data": {
            "text/plain": "\u001b[0m\u001b[1m ──────────────────────────────────────────────────────────────────────────────\u001b[22m\n\u001b[0m\u001b[1m                               \u001b[22m        Time                   Allocations      \n                               ──────────────────────   ───────────────────────\n       Tot / % measured:            67.7s / 0.38%            305MiB / 30.9%    \n\n Section               ncalls     time   %tot     avg     alloc   %tot      avg\n ──────────────────────────────────────────────────────────────────────────────\n input_files\\karate...     18    258ms   100%  14.3ms   94.5MiB  100%   5.25MiB\n\u001b[0m\u001b[1m ──────────────────────────────────────────────────────────────────────────────\u001b[22m"
          },
          "metadata": {}
        }
      ],
      "execution_count": 44,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-07-18T14:15:48.439Z",
          "iopub.execute_input": "2020-07-18T14:15:48.443Z",
          "iopub.status.idle": "2020-07-18T14:15:48.452Z"
        }
      }
    }
  ],
  "metadata": {
    "kernel_info": {
      "name": "julia-1.4"
    },
    "language_info": {
      "file_extension": ".jl",
      "name": "julia",
      "mimetype": "application/julia",
      "version": "1.4.2"
    },
    "kernelspec": {
      "argv": [
        "C:\\Users\\aadim\\AppData\\Local\\Programs\\Julia\\Julia-1.4.2\\bin\\julia.exe",
        "-i",
        "--startup-file=yes",
        "--color=yes",
        "--project=@.",
        "C:\\Users\\aadim\\.julia\\packages\\IJulia\\DrVMH\\src\\kernel.jl",
        "{connection_file}"
      ],
      "display_name": "Julia 1.4.2",
      "env": {},
      "interrupt_mode": "message",
      "language": "julia",
      "name": "julia-1.4"
    },
    "nteract": {
      "version": "0.24.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}