TriX_NetworkX.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0c273d44",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy import sparse\n",
    "from scipy.sparse import csr_matrix\n",
    "from scipy.sparse import coo_matrix\n",
    "from time import perf_counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6c05dd4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "filename = './datasets/facebook_combined.txt'\n",
    "# filename = './datasets/amazon0302.mtx'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ed42537c",
   "metadata": {},
   "outputs": [],
   "source": [
    "t0 = perf_counter()\n",
    "testgraph = nx.read_edgelist(filename, comments='#', delimiter=None, create_using=nx.Graph, nodetype=None, data=True, edgetype=None, encoding='utf-8')\n",
    "t_load = perf_counter() - t0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4751cca7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[   0  252  504  757 1009 1262 1514 1767 2019 2271 2524 2776 3029 3281\n",
      " 3534 3786 4039]\n"
     ]
    }
   ],
   "source": [
    "## define the partition index\n",
    "adj_matrix_dim = len(testgraph.nodes)\n",
    "partition_num = 16 ## can be set a variable\n",
    "partition_index = np.zeros(partition_num + 1, dtype=np.int32)\n",
    "for i in range(partition_num):\n",
    "    partition_index[i+1] = np.int32(adj_matrix_dim*(i+1)/partition_num)\n",
    "print(partition_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f85aefb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from multiprocessing.pool import ThreadPool as Pool\n",
    "\n",
    "pool_size = 16\n",
    "\n",
    "def worker(i, partition_index, G_part, testgraph):\n",
    "    for edge_list in testgraph.edges:\n",
    "        if((int(edge_list[1]) >= partition_index[i]) and (int(edge_list[1]) < partition_index[i+1])):\n",
    "            G_part[i].add_edge(edge_list[0], edge_list[1])\n",
    "\n",
    "pool = Pool(pool_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5aa2591d",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_part = []\n",
    "for i in range(partition_num):\n",
    "    G_part.append(nx.DiGraph())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ecde1cf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(partition_num):\n",
    "    pool.apply_async(worker, (i, partition_index, G_part, testgraph, ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e48fa8ee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "graph partition  0 :  DiGraph with 252 nodes and 1431 edges\n",
      "graph partition  1 :  DiGraph with 471 nodes and 3219 edges\n",
      "graph partition  2 :  DiGraph with 401 nodes and 3255 edges\n",
      "graph partition  3 :  DiGraph with 347 nodes and 2036 edges\n",
      "graph partition  4 :  DiGraph with 388 nodes and 2980 edges\n",
      "graph partition  5 :  DiGraph with 618 nodes and 6036 edges\n",
      "graph partition  6 :  DiGraph with 856 nodes and 10612 edges\n",
      "graph partition  7 :  DiGraph with 1216 nodes and 9408 edges\n",
      "graph partition  8 :  DiGraph with 448 nodes and 7399 edges\n",
      "graph partition  9 :  DiGraph with 634 nodes and 12308 edges\n",
      "graph partition  10 :  DiGraph with 893 nodes and 9937 edges\n",
      "graph partition  11 :  DiGraph with 417 nodes and 3793 edges\n",
      "graph partition  12 :  DiGraph with 620 nodes and 5722 edges\n",
      "graph partition  13 :  DiGraph with 852 nodes and 4958 edges\n",
      "graph partition  14 :  DiGraph with 360 nodes and 2178 edges\n",
      "graph partition  15 :  DiGraph with 576 nodes and 2962 edges\n"
     ]
    }
   ],
   "source": [
    "for i in range(partition_num):\n",
    "    print(\"graph partition \", i, \": \", G_part[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "14e4179c",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Get partition graph, maybe need to be parallel\n",
    "# G_part = []\n",
    "# for i in range(partition_num):\n",
    "#     G_part.append(nx.DiGraph())\n",
    "\n",
    "for edge_list in testgraph.edges:\n",
    "    for i in range(partition_num):\n",
    "        if ((int(edge_list[1]) >= partition_index[i]) and (int(edge_list[1]) < partition_index[i+1])):\n",
    "            G_part[i].add_edge(edge_list[0], edge_list[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d69b2964",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "graph partition  0 :  DiGraph with 252 nodes and 1431 edges\n",
      "graph partition  1 :  DiGraph with 471 nodes and 3219 edges\n",
      "graph partition  2 :  DiGraph with 401 nodes and 3255 edges\n",
      "graph partition  3 :  DiGraph with 347 nodes and 2036 edges\n",
      "graph partition  4 :  DiGraph with 388 nodes and 2980 edges\n",
      "graph partition  5 :  DiGraph with 618 nodes and 6036 edges\n",
      "graph partition  6 :  DiGraph with 856 nodes and 10612 edges\n",
      "graph partition  7 :  DiGraph with 1216 nodes and 9408 edges\n",
      "graph partition  8 :  DiGraph with 448 nodes and 7399 edges\n",
      "graph partition  9 :  DiGraph with 634 nodes and 12308 edges\n",
      "graph partition  10 :  DiGraph with 893 nodes and 9937 edges\n",
      "graph partition  11 :  DiGraph with 417 nodes and 3793 edges\n",
      "graph partition  12 :  DiGraph with 620 nodes and 5722 edges\n",
      "graph partition  13 :  DiGraph with 852 nodes and 4958 edges\n",
      "graph partition  14 :  DiGraph with 360 nodes and 2178 edges\n",
      "graph partition  15 :  DiGraph with 576 nodes and 2962 edges\n"
     ]
    }
   ],
   "source": [
    "for i in range(partition_num):\n",
    "    print(\"graph partition \", i, \": \", G_part[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "dcfbcabe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1612010\n"
     ]
    }
   ],
   "source": [
    "## triangle count in sub-graphs (need be parallel)\n",
    "triangle_count = 0\n",
    "node_triangle = np.zeros(len(testgraph.nodes))\n",
    "for g_index in range(partition_num): ## could be executed parallelly in different machines\n",
    "    for edge_list in testgraph.edges: ## traverse all the edges in the original graph\n",
    "        if ((G_part[g_index].has_node(edge_list[0])) and (G_part[g_index].has_node(edge_list[1]))):\n",
    "            srcSet = G_part[g_index].adj[edge_list[0]]\n",
    "            dstSet = G_part[g_index].adj[edge_list[1]]\n",
    "            for node_obj in srcSet:\n",
    "                if node_obj in dstSet:\n",
    "                    triangle_count += 1\n",
    "                    node_triangle[int(edge_list[0])] += 1\n",
    "                    node_triangle[int(edge_list[1])] += 1\n",
    "                    node_triangle[int(node_obj)] += 1\n",
    "\n",
    "print (triangle_count)\n",
    "## print (node_triangle)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "53912243",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1612010\n"
     ]
    }
   ],
   "source": [
    "testgraph_golden = nx.read_edgelist(filename, comments='#', delimiter=None, create_using=None, nodetype=None, data=True, edgetype=None, encoding='utf-8')\n",
    "triangle_golden = nx.triangles(testgraph_golden)\n",
    "result_golden = int(sum(triangle_golden.values())/3)\n",
    "print (result_golden)\n",
    "## print (triangle_golden)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac9c4ff6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.15 (default, Nov 24 2022, 15:19:38) \n[GCC 11.2.0]"
  },
  "vscode": {
   "interpreter": {
    "hash": "d8c35ca727124e6ef49ad1437a456b0984b9ec489fab4181e991d3ddd54fc8fa"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}