Multilevel evaluation of balance in directed signed networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jupyter code for multiplevel evaluation of balance in directed signed graphs incluidng \n",
    "the binary linear programming model for computing the frustration index of directed signed graphs as described in the paper  Aref, S., Dinh, L., Rezapour, R. et al. Multilevel structural evaluation of signed directed social networks based on balance theory. Sci Rep 10, 15228 (2020). https://doi.org/10.1038/s41598-020-71838-6\n",
    "\n",
    "Jupyter code written by Samin Aref, Rezvaneh Rezapour, and Ly Dinh in 2020\n",
    "\n",
    " Creative common licence: \n",
    " Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)\n",
    "\n",
    "Using this code for non-commercial purposes is permitted to all given that the three following publications are cited:\n",
    "\n",
    "    Aref, S., Dinh, L., Rezapour, R. et al. Multilevel structural evaluation of signed directed social networks based on balance theory. Sci Rep 10, 15228 (2020). https://doi.org/10.1038/s41598-020-71838-6\n",
    "    \n",
    "    Aref, S., Mason, A. J., and Wilson, M. C. Computing the line index of balance using integer programming optimisation. In Optimization Problems in Graph Theory, B. Goldengorin, Ed. Springer, 2018, pp. 65-84. https://doi.org/10.1007/978-3-319-94830-0_3\n",
    "    \n",
    "    Aref, S., Mason, A. J., and Wilson, M. C. A Modeling and Computational Study of the Frustration Index in Signed Networks. Networks (2019). https://doi.org/10.1002/net.21907\n",
    "        \n",
    "Related dataset: \n",
    "\n",
    "    Aref, S., Dinh, L., and Rezapour, R. : Dataset of directed signed networks from social domain. figshare data repository, 2020, https://doi.org/10.6084/m9.figshare.12152628"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " #1 - Sampson affect data (determine the csv file for time-frame 2,3,4) \n",
      " #2 - Newcomb Fraternity (determine the csv file for time-frame 00,...,15) \n",
      " #3 - Lemann college choice and rejections (determine the csv file for House A,B,C) \n",
      " #4 - Tribes.csv \n",
      " #5 - Bitcoin Alpha trust.csv \n",
      " #6 - Bitcoin OTC trust.csv \n",
      " #7 - Reddit.csv \n",
      " #8 - WikiVote.csv \n",
      " #9 - Philosophers Master-pupil.csv \n",
      " #10 - Philosophers Acquaintance.csv \n",
      " #11 - Philosophers Flattened.csv\n",
      "Select a signed digraph from the list of datasets above? (1/2/...)1\n"
     ]
    }
   ],
   "source": [
    "# Loading networks from directed signed network datasets\n",
    "# As one graph for each instance \n",
    "# Change directory_path according to the location of data on your computer\n",
    "\n",
    "directory_path='U:\\\\datasets\\\\Networks\\\\Directed signed graphs\\\\'\n",
    "\n",
    "import networkx as nx\n",
    "import csv\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "Graph_list=[] \n",
    "signedMatrix=[]\n",
    "unsignedMatrix=[]\n",
    "sorted_weighted_edges=[]\n",
    "order=[]\n",
    "size=[]\n",
    "NumberOfNegative=[]\n",
    "undirectedGraph=[]\n",
    "undirected_sorted_weighted_edges=[]\n",
    "\n",
    "\n",
    "print(\n",
    "      ' #1 - Sampson affect data (determine the csv file for time-frame 2,3,4)',\n",
    "    '\\n #2 - Newcomb Fraternity (determine the csv file for time-frame 00,...,15)',\n",
    "    '\\n #3 - Lemann college choice and rejections (determine the csv file for House A,B,C)',\n",
    "    '\\n #4 - Tribes.csv',\n",
    "    '\\n #5 - Bitcoin Alpha trust.csv',\n",
    "    '\\n #6 - Bitcoin OTC trust.csv',\n",
    "    '\\n #7 - Reddit.csv',\n",
    "    '\\n #8 - WikiVote.csv',\n",
    "    '\\n #9 - Philosophers Master-pupil.csv',\n",
    "    '\\n #10 - Philosophers Acquaintance.csv',\n",
    "    '\\n #11 - Philosophers Flattened.csv'\n",
    "     )\n",
    "\n",
    "graph_type=int(input(\"Select a signed digraph from the list of datasets above? (1/2/...)\"))\n",
    "\n",
    "\n",
    "\n",
    "paths_for_datasets=[\n",
    "    directory_path+'Sampson affect data\\\\T2.csv',\n",
    "    directory_path+'Fraternity3\\\\newfrat00.csv',\n",
    "    directory_path+'Lemann college choice and rejections\\\\House_A.csv',\n",
    "    directory_path+'Tribes_sym.csv',\n",
    "    directory_path+'Bitcoin Alpha trust.csv',\n",
    "    directory_path+'Bitcoin OTC trust.csv',\n",
    "    directory_path+'Reddit.csv',\n",
    "    directory_path+'WikiVote.csv',\n",
    "    directory_path+'Philosophers Master-pupil-sym.csv',\n",
    "    directory_path+'Philosophers Acquaintance-sym.csv',\n",
    "    directory_path+'Philosophers Flattened-sym.csv'\n",
    "                   ]\n",
    "\n",
    "path=paths_for_datasets[graph_type-1]\n",
    "# This code can be modified to load multiple networks into the memory which requires\n",
    "# changing this parameter (to the desirable number) and changing the next two lines:\n",
    "run=1\n",
    "for i in range(run):\n",
    "    with open(path, newline='') as f:\n",
    "        edgelist=[]\n",
    "        reader = csv.reader(f)\n",
    "        edgelist = list(reader)\n",
    "    \n",
    "    #remove the header\n",
    "    edgelist=edgelist[1:]    \n",
    "\n",
    "    Graph_list.append(nx.DiGraph())\n",
    "\n",
    "    for [u,v,w] in edgelist:\n",
    "        Graph_list[i].add_edge(u,v, weight=np.sign(int(w)))\n",
    "\n",
    "\n",
    "    mapping=dict(zip(Graph_list[i].nodes(),range(len(Graph_list[i].nodes()))))\n",
    "    Graph_list[i]=nx.relabel_nodes(Graph_list[i],mapping)  \n",
    "    signedMatrix.append(nx.to_numpy_matrix(Graph_list[i]))\n",
    "    unsignedMatrix.append(abs(signedMatrix[i]))\n",
    "\n",
    "    weighted_edges=nx.get_edge_attributes(Graph_list[i], 'weight') \n",
    "    sorted_weighted_edges.append({})\n",
    "    for (u,v) in weighted_edges:\n",
    "        (sorted_weighted_edges[i])[(u,v)] = weighted_edges[(u,v)]\n",
    "    \n",
    "    order.append(len(signedMatrix[i]))\n",
    "    size.append(int(np.count_nonzero(signedMatrix[i])))\n",
    "    NumberOfNegative.append(((-1 == signedMatrix[i])).sum())\n",
    "        \n",
    "    undirectedGraph.append((Graph_list[i]).to_undirected(as_view=True))\n",
    "    undirected_sorted_weighted_edges.append(nx.get_edge_attributes(undirectedGraph[i], 'weight'))    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------------Network metrics-----------------------------\n",
      "index:  0\n",
      "global_clusterng_coefficient:  0.3488372093023256\n",
      "average_degree_centrality:  0.6797385620915032\n",
      "density:  0.33986928104575165\n",
      "average_clustering_coefficient:  0.5110269360269359\n",
      "triadic_census:  {'003': 94, '012': 186, '102': 102, '021D': 28, '021U': 44, '021C': 88, '111D': 72, '111U': 58, '030T': 30, '030C': 6, '201': 36, '120D': 18, '120U': 10, '120C': 22, '210': 20, '300': 2}\n",
      "shortest_path:  1.7450980392156863\n"
     ]
    }
   ],
   "source": [
    "# This section calculates general network metrics such as transitivity, degree centrality, and density of a network.\n",
    "# Note: for calculating the shortest path, the network should be connecte and consists of (only) 1 component.  \n",
    "# updated = 04/22/2020\n",
    "\n",
    "import pandas as pd\n",
    "from networkx import *\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import pickle\n",
    "\n",
    "\n",
    "#calculating the average\n",
    "def returnAverage(myDict): \n",
    "    sum = 0\n",
    "    for i in myDict: \n",
    "        sum = sum + myDict[i] \n",
    "    ave = sum / len(myDict)\n",
    "    return ave\n",
    "\n",
    "# calculate the network metrics in a given network (main function)\n",
    "def calculate_network_metrcis(G_new):\n",
    "\n",
    "    #remove isolate and pendants from the dataframe\n",
    "    G_new.remove_nodes_from(nx.isolates(G_new))\n",
    "    remove = [node for node,degree in G_new.degree() if degree == 1]\n",
    "    G_new.remove_nodes_from(remove)\n",
    "    # remove self loop\n",
    "    G_new.remove_edges_from(nx.selfloop_edges(G_new))\n",
    "    \n",
    "    print ('global_clusterng_coefficient: ', transitivity(G_new))\n",
    "    print ('average_degree_centrality: ', returnAverage(nx.degree_centrality(G_new)))\n",
    "    print ('density: ', nx.density(G_new))\n",
    "    print ('average_clustering_coefficient: ', returnAverage(nx.clustering(nx.Graph(G_new))))\n",
    "    print ('triadic_census: ', triadic_census(G_new))\n",
    "    \n",
    "    '''\n",
    "    for calculating shortest path, we first need to check if the Graph is weakly connected. \n",
    "    If not, we first get the largest component and calculate the shortest path only \n",
    "    for the largest component of the graph.\n",
    "    '''\n",
    "    if nx.number_weakly_connected_components(G_new) == 1:\n",
    "        print ('shortest_path: ',nx.average_shortest_path_length(G_new))\n",
    "        \n",
    "    else:\n",
    "        print ('NOTE: Shortest path cannot be calculated. Graph is not connected.')\n",
    "\n",
    "\n",
    "## iterate through the list of graphs to get the network metrics\n",
    "for index in range(run): \n",
    "    print ('-------------------------Network metrics-----------------------------')\n",
    "    print ('index: ', index)\n",
    "    calculate_network_metrcis(Graph_list[index])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------------Triadic balance-----------------------------\n",
      "index:  0\n",
      "Triad Level Balance:  0.6833333333333333\n",
      "Number of balance and transitive triads:  41\n",
      "Number of imbalance and transitive triads:  19\n",
      "Number of balance triads in each census {'030T': 22, '300': 2, '120U': 6, '120D': 11}\n",
      "Number of imbalance triads in each census {'120U': 4, '120D': 7, '030T': 8}\n"
     ]
    }
   ],
   "source": [
    "# This section calculates balace in triads with respect to direction.\n",
    "# We first extract the transitive triads, then we break the transitive triads to semi-cycles, and finally \n",
    "# calculate balance in each semicycle. The triad is balance only if all its semicycles are balance. \n",
    "# updated = 04/22/2020\n",
    "\n",
    "# This algorithm is based on the model introduced in the following paper:\n",
    "# XXX (will be updated)\n",
    "\n",
    "import pandas as pd\n",
    "from networkx import *\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import itertools\n",
    "from itertools import combinations\n",
    "import time\n",
    "import pickle\n",
    "from multiprocessing import Pool\n",
    "\n",
    "\n",
    "## counting the number of instances in a list\n",
    "def count_lists(mylist):            \n",
    "    new_dict = {}\n",
    "    for i in mylist:\n",
    "        if i[1] not in new_dict:\n",
    "            new_dict[i[1]] = 1\n",
    "        else:\n",
    "            new_dict[i[1]] += 1\n",
    "    return (new_dict)            \n",
    "\n",
    "## Get all triples in triads with respect to their census and edgelists (in edge_atts)\n",
    "def get_directed_triads(triads):\n",
    "    # Get all triplets of edges\n",
    "    for candidate_edges in combinations(triads.items(), 3):\n",
    "        # Get edges between unique pair of nodes\n",
    "        unique_edges = set([tuple(sorted(k)) for k,v in candidate_edges])\n",
    "        # Only consider triad in which the tree edges use a unique pair of nodes\n",
    "        if len(unique_edges) == 3:\n",
    "            yield dict(candidate_edges)\n",
    "            \n",
    "## searching through traids\n",
    "def search_triangles(G, nodes = None):\n",
    "    if nodes is None:\n",
    "        nodes_nbrs = G.adj.items()\n",
    "    else:\n",
    "        nodes_nbrs = ((n, G[n]) for n in G.nbunch_iter(nodes))\n",
    "    for v, v_nbrs in nodes_nbrs:\n",
    "        vs = set(v_nbrs) - {v}\n",
    "        for w in vs:\n",
    "            #print(w)\n",
    "            xx = vs & (set(G[w]) - {w})\n",
    "            yield [ set(x) for x in list(zip(itertools.repeat(v), itertools.repeat(w), list(xx))) ]\n",
    "            \n",
    "#Calculate balance in traids (main function)\n",
    "def calculate_traid_balance(G_new):\n",
    "    triad_dict = {}\n",
    "    triad_class = {}\n",
    "    all_triads = []\n",
    "    ## there are only 4 transistive census: 030T, 120D, 120U, and 300 \n",
    "    non_transitive_census = ['003','012', '102', '021D', '021C', '021U', '021', '111U', '111D', '201', '030C', '120C', '210']\n",
    "    all_triad = nx.triangles(G_new.to_undirected())\n",
    "    iter_g = search_triangles(G_new)\n",
    "    \n",
    "    \n",
    "    for iter_t in iter_g:\n",
    "        for ta in list(iter_t):\n",
    "            tt = \",\".join([str(x) for x in sorted(set(ta))])\n",
    "            triad_dict[tt] = True\n",
    "            \n",
    "\n",
    "    for val in triad_dict.keys():\n",
    "        nodes = [int(x) for x in val.split(\",\")]\n",
    "        census = [k for k, v in nx.triads.triadic_census(G_new.subgraph(nodes)).items() if v][0]\n",
    "        if census not in non_transitive_census:\n",
    "            sign = nx.get_edge_attributes(G_new.subgraph(nodes),'weight')\n",
    "            triad_class[val] = [census, sign]\n",
    "            #map_census_edges(G_new, val, triad_class)     \n",
    "\n",
    "    \n",
    "    for key, value in triad_class.items():\n",
    "        all_directed_triads = list(get_directed_triads(value[1]))\n",
    "        all_triads.append([all_directed_triads, value[0]])\n",
    "            \n",
    "    ## getting the balance vs. imbalance triads \n",
    "    balances = []\n",
    "    imbalances = []\n",
    "    for items in all_triads:\n",
    "        balance_list = []\n",
    "        \n",
    "        ## removing two cycles from 300 and then calculate balance\n",
    "        if items[1] == '300':\n",
    "            for triangle in items[0]:\n",
    "                node = []\n",
    "                for edge in triangle:\n",
    "                    if edge[0] not in node:\n",
    "                        node.append(edge[0])\n",
    "                if len(node) != 3:\n",
    "                    balance = 1\n",
    "                    for edge in triangle:\n",
    "                        balance *= triangle[edge]\n",
    "                    balance_list.append(balance)\n",
    "        else:\n",
    "            for item in items[0]:\n",
    "                balance = 1\n",
    "                for edge in item:\n",
    "                    balance *= item[edge]\n",
    "                balance_list.append(balance)\n",
    "        neg = []\n",
    "        for n in balance_list:\n",
    "            if n <= 0 :\n",
    "                neg.append(n)\n",
    "        if neg:\n",
    "            imbalances.append(items)\n",
    "        else:\n",
    "            balances.append(items)\n",
    "            \n",
    "    print ('Triad Level Balance: ', (len(balances)/(len(balances) + len(imbalances))))        \n",
    "    print ('Number of balance and transitive triads: ', len(balances))\n",
    "    print ('Number of imbalance and transitive triads: ', len(imbalances))\n",
    "    \n",
    "    print('Number of balance triads in each census', count_lists(balances))\n",
    "    print('Number of imbalance triads in each census', count_lists(imbalances))\n",
    "\n",
    "## iterate through the list of graphs to calculate balance in triads\n",
    "for index in range(run):\n",
    "    print ('-------------------------Triadic balance-----------------------------')\n",
    "    print ('index: ', index)\n",
    "    calculate_traid_balance(Graph_list[index])    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Instance 0  solution equals 17.0\n",
      "--------------------------------------------------------------------------------------------\n",
      "-------------------------------- ***  EXPERIMENT STATS  *** --------------------------------\n",
      "--------------------------------------------------------------------------------------------\n",
      "Lower bounds on frustration index: [17.]\n",
      "\n",
      "Solve times: [0.05]\n",
      "Average solve time 0.04799985885620117\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Continuous model to obtain a lower bound for L(G) as the optimal objective function of a DIRECTED signed graph\n",
    "# Based on the linear programming model (Eq. 7) discussed in the following publication\n",
    "#  Aref, S., and Neal, Z., Detecting Coalitions by Optimally Partitioning Signed Networks \n",
    "#  of Political Collaboration. Scientific Reports (2020). url: http://arxiv.org/pdf/1906.01696.\n",
    "\n",
    "# This code solves graph optimization model(s) using \"Gurobi solver\"\n",
    "# to compute a lower-bound of frustration index for the input signed digraph(s)\n",
    "\n",
    "# Note that you must have installed Gurobi into Jupyter and registered a Gurobi license\n",
    "# in order to run this code\n",
    "\n",
    "\n",
    "import time\n",
    "import numpy as np\n",
    "import multiprocessing\n",
    "from gurobipy import *\n",
    "objectivevalue=[]\n",
    "solveTime=[]\n",
    "\n",
    "for index in range(run):\n",
    "    \n",
    "    neighbors={}\n",
    "    Degree=[]\n",
    "    for u in sorted((undirectedGraph[index]).nodes()):\n",
    "        neighbors[u] = list((undirectedGraph[index])[u])\n",
    "        Degree.append(len(neighbors[u]))\n",
    "    # Note that reciprocated edges are counted as one and only contribute one to the degree of each endpoint\n",
    "    \n",
    "    #Finding the node with the highest unsigned degree\n",
    "    maximum_degree = max(Degree)\n",
    "    [node_to_fix]=[([i for i, j in enumerate(Degree) if j == maximum_degree]).pop()]\n",
    "    \n",
    "\n",
    "    # Model parameters\n",
    "    model = Model(\"Continuous model for lower-bounding frustration index\")\n",
    "    \n",
    "    # Do you want details of branching to be reported? (0=No, 1=Yes)\n",
    "    model.setParam(GRB.param.OutputFlag, 0) \n",
    "    \n",
    "    # There are different methods for solving optimization models:\n",
    "    # (-1=automatic, 0=primal simplex, 1=dual simplex, 2=barrier, 3=concurrent, 4=deterministic concurrent)\n",
    "    # For problems with a large number of contstraints, barrier method is more suitable\n",
    "    model.setParam(GRB.param.Method, 2)\n",
    "\n",
    "    # Solving the problems without crossover takes a substantially shorter time\n",
    "    # in cases where there are a large number of constraints. (0=without, 1=with)\n",
    "    model.setParam(GRB.Param.Crossover, 0)\n",
    "    \n",
    "    # What is the time limit in second?\n",
    "    # Here, it is set to 10 hours\n",
    "    model.setParam('TimeLimit', 10*3600)\n",
    "    \n",
    "    \n",
    "    # How many threads to be used for exploring the feasible space in parallel?\n",
    "    # Here, the minimum of 32 and the availbale CPUs is used\n",
    "    model.setParam(GRB.Param.Threads, min(32,multiprocessing.cpu_count()))\n",
    "   \n",
    "    #This chunk of code lists the graph triangles\n",
    "    GraphTriangles=[]\n",
    "    for n1 in sorted((undirectedGraph[index]).nodes()):\n",
    "        neighbors1 = set((undirectedGraph[index])[n1])\n",
    "        for n2 in filter(lambda x: x>n1, neighbors1):\n",
    "            neighbors2 = set((undirectedGraph[index])[n2])\n",
    "            common = neighbors1 & neighbors2\n",
    "            for n3 in filter(lambda x: x>n2, common):\n",
    "                GraphTriangles.append([n1,n2,n3])\n",
    "    #print(\"--- %Listed\",len(GraphTriangles),\"triangles for the graph\")\n",
    "    \n",
    "\n",
    "    # Create decision variables and update model to integrate new variables\n",
    "    # Note that the variables are defined as CONTINUOUS within the unit interval\n",
    "    x=[]\n",
    "    for i in range(0,order[index]):\n",
    "        x.append(model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='x'+str(i)))\n",
    "\n",
    "    z={}    \n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        z[(i,j)]=model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='z'+str(i)+','+str(j))    \n",
    "\n",
    "    model.update()\n",
    "    \n",
    "    # Set the objective function\n",
    "    OFV=0\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        OFV = OFV + (1-(sorted_weighted_edges[index])[(i,j)])/2 + ((sorted_weighted_edges[index])[(i,j)])*(x[i]+x[j]-2*z[(i,j)])          \n",
    "    model.setObjective(OFV, GRB.MINIMIZE)\n",
    "\n",
    "    # Add constraints to the model and update model to integrate new constraints\n",
    "    \n",
    "    ## ADD CORE CONSTRAINTS ##\n",
    "\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "            if (sorted_weighted_edges[index])[(i,j)]==1:\n",
    "                model.addConstr(z[(i,j)] <= (x[i]+x[j])/2 , 'Edge positive'+str(i)+','+str(j))\n",
    "            if (sorted_weighted_edges[index])[(i,j)]==-1:\n",
    "                model.addConstr(z[(i,j)] >= x[i] + x[j] -1 , 'Edge negative'+str(i)+','+str(j))            \n",
    "\n",
    "    for triangle in GraphTriangles:\n",
    "        [i,j,k]=triangle\n",
    "        b_ij=(i,j) in sorted_weighted_edges[index] \n",
    "        b_ik=(i,k) in sorted_weighted_edges[index]\n",
    "        b_jk=(j,k) in sorted_weighted_edges[index]\n",
    "        if b_ij:\n",
    "            if b_ik:\n",
    "                if b_jk:\n",
    "                    model.addConstr(x[j] + z[(i,k)] >= z[(i,j)] + z[(j,k)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr(x[i] + z[(j,k)] >= z[(i,j)] + z[(i,k)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                    model.addConstr(x[k] + z[(i,j)] >= z[(i,k)] + z[(j,k)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr( 1 + z[(i,j)] + z[(i,k)] + z[(j,k)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))           \n",
    "                else:\n",
    "                    model.addConstr(x[j] + z[(i,k)] >= z[(i,j)] + z[(k,j)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr(x[i] + z[(k,j)] >= z[(i,j)] + z[(i,k)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                    model.addConstr(x[k] + z[(i,j)] >= z[(i,k)] + z[(k,j)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr( 1 + z[(i,j)] + z[(i,k)] + z[(k,j)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))           \n",
    "            elif b_jk:\n",
    "                model.addConstr(x[j] + z[(k,i)] >= z[(i,j)] + z[(j,k)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr(x[i] + z[(j,k)] >= z[(i,j)] + z[(k,i)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                model.addConstr(x[k] + z[(i,j)] >= z[(k,i)] + z[(j,k)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr( 1 + z[(i,j)] + z[(k,i)] + z[(j,k)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))           \n",
    "            else:\n",
    "                model.addConstr(x[j] + z[(k,i)] >= z[(i,j)] + z[(k,j)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr(x[i] + z[(k,j)] >= z[(i,j)] + z[(k,i)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                model.addConstr(x[k] + z[(i,j)] >= z[(k,i)] + z[(k,j)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr( 1 + z[(i,j)] + z[(k,i)] + z[(k,j)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))           \n",
    "        else:\n",
    "            if b_ik:\n",
    "                if b_jk:\n",
    "                    model.addConstr(x[j] + z[(i,k)] >= z[(j,i)] + z[(j,k)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr(x[i] + z[(j,k)] >= z[(j,i)] + z[(i,k)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                    model.addConstr(x[k] + z[(j,i)] >= z[(i,k)] + z[(j,k)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr( 1 + z[(j,i)] + z[(i,k)] + z[(j,k)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))\n",
    "                else:\n",
    "                    model.addConstr(x[j] + z[(i,k)] >= z[(j,i)] + z[(k,j)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr(x[i] + z[(k,j)] >= z[(j,i)] + z[(i,k)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                    model.addConstr(x[k] + z[(j,i)] >= z[(i,k)] + z[(k,j)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    model.addConstr( 1 + z[(j,i)] + z[(i,k)] + z[(k,j)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))\n",
    "            elif b_jk:\n",
    "                model.addConstr(x[j] + z[(k,i)] >= z[(j,i)] + z[(j,k)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr(x[i] + z[(j,k)] >= z[(j,i)] + z[(k,i)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                model.addConstr(x[k] + z[(j,i)] >= z[(k,i)] + z[(j,k)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr( 1 + z[(j,i)] + z[(k,i)] + z[(j,k)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))\n",
    "            else:\n",
    "                model.addConstr(x[j] + z[(k,i)] >= z[(j,i)] + z[(k,j)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr(x[i] + z[(k,j)] >= z[(j,i)] + z[(k,i)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "                model.addConstr(x[k] + z[(j,i)] >= z[(k,i)] + z[(k,j)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "                model.addConstr( 1 + z[(j,i)] + z[(k,i)] + z[(k,j)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))\n",
    "    model.update()\n",
    "\n",
    "    ## ADD ADDITIONAL CONSTRAINTS (speed-ups) ##\n",
    "    \n",
    "    # Colour the node with the highest degree as 1\n",
    "    model.addConstr(x[node_to_fix]==1 , '1stnodecolour')   \n",
    "    model.update()\n",
    "  \n",
    "\n",
    "    # Solve\n",
    "    start_time = time.time()\n",
    "    model.optimize()\n",
    "    solveTime.append(time.time() - start_time) \n",
    "    \n",
    "    # Save optimal objective function values\n",
    "    obj = model.getObjective()\n",
    "    objectivevalue.append((obj.getValue()))\n",
    "        \n",
    "    # Report the optimal objective function value for each instance\n",
    "    print('Instance', index,' solution equals',np.around(objectivevalue[index])) \n",
    "    print(\"-\"*92)\n",
    "    \n",
    "    # Printing the solution (optional)\n",
    "    #print(\"Optimal values of the decision variables\")\n",
    "    #for v in model.getVars():\n",
    "    #    print (v.varName, v.x)\n",
    "    #print()    \n",
    "\n",
    "# Save the lower bounds as a list for the next step (computing the frutsration index)\n",
    "LowerBounds=np.around(objectivevalue)  \n",
    "\n",
    "print(\"-\"*32,\"***  EXPERIMENT STATS  ***\",\"-\"*32)\n",
    "print(\"-\"*92)\n",
    "print(\"Lower bounds on frustration index:\",LowerBounds)\n",
    "print()\n",
    "print(\"Solve times:\",np.around(solveTime, decimals=2))\n",
    "print(\"Average solve time\",np.mean(solveTime))\n",
    "#print(\"Solve time Standard Deviation\",np.std(solveTime))\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameter OutputFlag unchanged\n",
      "   Value: 1  Min: 0  Max: 1  Default: 1\n",
      "Changed value of parameter Threads to 4\n",
      "   Prev: 0  Min: 0  Max: 1024  Default: 0\n",
      "--- %Binary variables are created\n",
      "--- %Core constraints are added\n",
      "--- %Additional constraints are added\n",
      "Optimize a model with 248 rows, 122 columns and 845 nonzeros\n",
      "Variable types: 104 continuous, 18 integer (18 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 2e+01]\n",
      "Found heuristic solution: objective 49.0000000\n",
      "Presolve removed 16 rows and 8 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 232 rows, 114 columns, 789 nonzeros\n",
      "Extracted 39 lazy constraints\n",
      "Variable types: 96 continuous, 18 integer (18 binary)\n",
      "\n",
      "Root relaxation: objective 1.000000e+00, 19 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0    1.00000    0   18   49.00000    1.00000  98.0%     -    0s\n",
      "H    0     0                      32.0000000    1.00000  96.9%     -    0s\n",
      "     0     0   17.00000    0   18   32.00000   17.00000  46.9%     -    0s\n",
      "H    0     0                      25.0000000   17.00000  32.0%     -    0s\n",
      "     0     0   17.00000    0   18   25.00000   17.00000  32.0%     -    0s\n",
      "     0     0   17.00000    0   18   25.00000   17.00000  32.0%     -    0s\n",
      "     0     2   17.00000    0   18   25.00000   17.00000  32.0%     -    0s\n",
      "*    4     0               2      21.0000000   20.75000  1.19%   106    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 3\n",
      "  Lazy constraints: 39\n",
      "\n",
      "Explored 7 nodes (721 simplex iterations) in 0.21 seconds\n",
      "Thread count was 4 (of 4 available processors)\n",
      "\n",
      "Solution count 4: 21 25 32 49 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 2.100000000000e+01, best bound 2.100000000000e+01, gap 0.0000%\n",
      "Instance 0  solution equals 21.0\n",
      "Optimal values of the decision variables\n",
      "x0 : 0\n",
      "x1 : 1\n",
      "x2 : 0\n",
      "x3 : 0\n",
      "x4 : 1\n",
      "x5 : 0\n",
      "x6 : 0\n",
      "x7 : 0\n",
      "x8 : 1\n",
      "x9 : 1\n",
      "x10 : 0\n",
      "x11 : 0\n",
      "x12 : 0\n",
      "x13 : 1\n",
      "x14 : 0\n",
      "x15 : 0\n",
      "x16 : 0\n",
      "x17 : 0\n",
      "\n",
      "Meso-scale measurements for instance 0\n",
      "Cohesiveness: 0.8269230769230769\n",
      "Divisiveness: 0.7692307692307693\n",
      "\n",
      "--------------------------------------------------------------------------------------------\n",
      "-------------------------------- ***  EXPERIMENT STATS  *** --------------------------------\n",
      "--------------------------------------------------------------------------------------------\n",
      "Frustration indices: [21.]\n",
      "Solve times (in seconds): [0.22]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Binary linear programming model for computing the frustration index of \n",
    "# a directed signed graph (frustration-index-directed) as the optimal objective function\n",
    "\n",
    "# This code solves graph optimization model(s) using \"Gurobi solver\"\n",
    "# to compute the measure called, frustration index, for the input signed digraph(s)\n",
    "\n",
    "# Note that you must have installed Gurobi into Jupyter and registered a Gurobi license\n",
    "# in order to run this code\n",
    "\n",
    "# This part of code requires the lower bound produced in the step above. If you intend to run this computation \n",
    "# without providing a lower bound, you should first comment out the line containing this command:\n",
    "# model.addConstr(OFV >= int(LowerBounds[index]), 'LP lower bound')\n",
    "\n",
    "#Setting parameters\n",
    "#lazyParam=int(input(\"What is the lazy parameter for unbalanced triangle lazy cuts? (0/1/2/3)\"))\n",
    "# See \"lazy\" as a tunable parameter in linear constraint attributes in Gurobi optimizer reference manual below:\n",
    "# https://www.gurobi.com/documentation/8.1/refman/lazy.html\n",
    "lazyParam=int(3)\n",
    "\n",
    "#speedupParam=int(input(\"Do you want to use the speedups? (0=No, 1=Yes)\"))\n",
    "speedupParam=int(1)\n",
    "\n",
    "import collections\n",
    "import time\n",
    "import numpy as np\n",
    "import multiprocessing\n",
    "from gurobipy import *\n",
    "objectivevalue=[]\n",
    "solveTime=[]\n",
    "effectiveBranchingFactors=[]\n",
    "\n",
    "for index in range(run):\n",
    "    \n",
    "    type_of_edge=[]\n",
    "    optimal_node_values=[]\n",
    "\n",
    "    neighbors={}\n",
    "    Degree=[]\n",
    "    for u in sorted((undirectedGraph[index]).nodes()):\n",
    "        neighbors[u] = list((undirectedGraph[index])[u])\n",
    "        Degree.append(len(neighbors[u]))\n",
    "    # Note that reciprocated edges are counted as one and only contribute one to the degree of each endpoint\n",
    "    \n",
    "    #Finding the node with the highest unsigned degree\n",
    "    maximum_degree = max(Degree)\n",
    "    [node_to_fix]=[([i for i, j in enumerate(Degree) if j == maximum_degree]).pop()]\n",
    "\n",
    "    # Model parameters\n",
    "    model = Model(\"Computing the frustration index of directed signed graphs\")\n",
    "\n",
    "    # There are different methods for solving optimization models:\n",
    "    # (-1=automatic, 0=primal simplex, 1=dual simplex, 2=barrier, 3=concurrent, 4=deterministic concurrent)\n",
    "    # model.setParam(GRB.param.Method, -1)\n",
    "    \n",
    "    # What is the time limit in second?\n",
    "    # model.setParam('TimeLimit', 10*3600)\n",
    "    \n",
    "    # Do you want details of branching to be reported? (0=No, 1=Yes)\n",
    "    model.setParam(GRB.param.OutputFlag, 1) \n",
    "    \n",
    "    # Do you want a non-zero Mixed integer programming tolerance (MIP Gap)?\n",
    "    # Note that a non-zero MIP gap may prevent the model from computing the exact value of frustration index\n",
    "    # model.setParam('MIPGap', 0.0001)  \n",
    "    \n",
    "    # How many threads to be used for exploring the feasible space in parallel?\n",
    "    # Here, the minimum of 32 and the availbale CPUs is used\n",
    "    model.setParam(GRB.Param.Threads, min(32,multiprocessing.cpu_count()))\n",
    "    \n",
    "    #This chunk of code lists the graph triangles\n",
    "    GraphTriangles=[]\n",
    "    for n1 in sorted((undirectedGraph[index]).nodes()):\n",
    "        neighbors1 = set((undirectedGraph[index])[n1])\n",
    "        for n2 in filter(lambda x: x>n1, neighbors1):\n",
    "            neighbors2 = set((undirectedGraph[index])[n2])\n",
    "            common = neighbors1 & neighbors2\n",
    "            for n3 in filter(lambda x: x>n2, common):\n",
    "                GraphTriangles.append([n1,n2,n3])\n",
    "    #print(\"--- %Listed\",len(GraphTriangles),\"triangles for the graph\")\n",
    "\n",
    "    #This chunk of code lists the balanced and unbalanced triangles\n",
    "    w=nx.get_edge_attributes(undirectedGraph[index], 'weight')  \n",
    "    unbalanced_triangles = []\n",
    "    balanced_triangles = []\n",
    "    for triad in GraphTriangles: \n",
    "        if  (undirected_sorted_weighted_edges[index])[(triad[0],triad[1])]*\\\n",
    "        (undirected_sorted_weighted_edges[index])[(triad[0],triad[2])]*\\\n",
    "        (undirected_sorted_weighted_edges[index])[(triad[1],triad[2])] == -1:\n",
    "            unbalanced_triangles.append(triad)\n",
    "        elif (undirected_sorted_weighted_edges[index])[(triad[0],triad[1])]*\\\n",
    "        (undirected_sorted_weighted_edges[index])[(triad[0],triad[2])]*\\\n",
    "        (undirected_sorted_weighted_edges[index])[(triad[1],triad[2])] == 1:\n",
    "            balanced_triangles.append(triad)  \n",
    "    #print(\"--- %Listed\",len(unbalanced_triangles),\"unbalanced triangles for the graph\")\n",
    "\n",
    "    # Create decision variables and update model to integrate new variables\n",
    "    x=[]\n",
    "    for i in range(0,order[index]):\n",
    "        x.append(model.addVar(vtype=GRB.BINARY, name='x'+str(i))) # arguments by name\n",
    "    model.update()\n",
    "    \n",
    "    f={}\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        f[(i,j)]=model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='f'+str(i)+','+str(j))\n",
    "    model.update()\n",
    "    print(\"--- %Binary variables are created\")\n",
    "\n",
    "    # Set the objective function\n",
    "    OFV=0\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        OFV = OFV + f[(i,j)]                 \n",
    "    model.setObjective(OFV, GRB.MINIMIZE)\n",
    "\n",
    "    # Add constraints to the model and update model to integrate new constraints\n",
    "    \n",
    "    ## ADD CORE CONSTRAINTS ##\n",
    "\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        model.addConstr( f[(i,j)] >= x[i] - ((sorted_weighted_edges[index])[(i,j)])*x[j] -\\\n",
    "                        (1-(sorted_weighted_edges[index])[(i,j)])/2\n",
    "                             , '1st Edge'+','+str(i)+','+str(j))\n",
    "        model.addConstr( f[(i,j)] >= -x[i] + ((sorted_weighted_edges[index])[(i,j)])*x[j] +\\\n",
    "                        (1-(sorted_weighted_edges[index])[(i,j)])/2\n",
    "                             , '2nd Edge'+','+str(i)+','+str(j))                  \n",
    "    model.update()\n",
    "    model.addConstr(OFV >= int(LowerBounds[index]), 'LP lower bound')   # This line can be commented out\n",
    "    model.update()\n",
    "    print(\"--- %Core constraints are added\")\n",
    "    \n",
    "            \n",
    "    ## ADD ADDITIONAL CONSTRAINTS (speed-ups) ##\n",
    "    \n",
    "    if speedupParam==1:\n",
    "\n",
    "        # Triangle valid inequalities            \n",
    "\n",
    "        triangleInequalityCount=len(unbalanced_triangles)\n",
    "        for triangle in unbalanced_triangles:\n",
    "            [i,j,k]=triangle\n",
    "            b_ij=(i,j) in sorted_weighted_edges[index] \n",
    "            b_ik=(i,k) in sorted_weighted_edges[index]\n",
    "            b_jk=(j,k) in sorted_weighted_edges[index]\n",
    "            if b_ij:\n",
    "                if b_ik:\n",
    "                    if b_jk:\n",
    "                        model.addConstr(f[(i,j)] + f[(i,k)] + f[(j,k)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    else:\n",
    "                        model.addConstr(f[(i,j)] + f[(i,k)] + f[(k,j)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                elif b_jk:\n",
    "                    model.addConstr(f[(i,j)] + f[(k,i)] + f[(j,k)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                else:\n",
    "                    model.addConstr(f[(i,j)] + f[(k,i)] + f[(k,j)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "            else:\n",
    "                if b_ik:\n",
    "                    if b_jk:\n",
    "                        model.addConstr(f[(j,i)] + f[(i,k)] + f[(j,k)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                    else:\n",
    "                        model.addConstr(f[(j,i)] + f[(i,k)] + f[(k,j)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                elif b_jk:\n",
    "                    model.addConstr(f[(j,i)] + f[(k,i)] + f[(j,k)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "                else:\n",
    "                    model.addConstr(f[(j,i)] + f[(k,i)] + f[(k,j)] >= 1 ,\\\n",
    "                                        'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))\n",
    "        model.update()\n",
    "        model.setAttr('Lazy',model.getConstrs()[2*(size[index]):2*(size[index])+triangleInequalityCount]\\\n",
    "                      ,[lazyParam]*triangleInequalityCount)\n",
    "        model.update()\n",
    "        print(\"--- %Additional constraints are added\")\n",
    "\n",
    "        #branching priority is based on unsigned degree \n",
    "        model.setAttr('BranchPriority',model.getVars()[:order[index]],Degree)\n",
    "        model.update() \n",
    "    \n",
    "\n",
    "    # Solve\n",
    "    start_time = time.time()\n",
    "    model.optimize()\n",
    "    solveTime.append(time.time() - start_time) \n",
    "    \n",
    "    \n",
    "    # Save optimal objective function values\n",
    "    obj = model.getObjective()\n",
    "    objectivevalue.append((obj.getValue()))\n",
    "    \n",
    "    # Compute the effective branching factors\n",
    "    if (model.NodeCount)**(1/((size[index])+2*(order[index]))) >= 1:\n",
    "        effectiveBranchingFactors.append((model.NodeCount)**(1/((size[index])+2*(order[index]))))\n",
    "        \n",
    "    # Report the optimal objective function value for each instance\n",
    "    print('Instance', index,' solution equals',objectivevalue[index]) \n",
    "\n",
    "    # Printing the solution (optional)\n",
    "    print(\"Optimal values of the decision variables\")\n",
    "    for v in model.getVars():\n",
    "        if v.varName.startswith('x'):\n",
    "            optimal_node_values.append(int(v.x))\n",
    "            #if v.x!=1:\n",
    "            print (v.varName,\":\",int(v.x)) \n",
    "    \n",
    "    # For printing types of the edges according to the optimal partition according to the four categories:\n",
    "    # positive-internal, positive-external, negative-internal, negative-external\n",
    "    \n",
    "    for (u,v) in (sorted_weighted_edges[index]):\n",
    "        type_of_edge.append((2*(2*optimal_node_values[u]-1)*(2*optimal_node_values[v]-1)+((sorted_weighted_edges[index])[(u,v)])))\n",
    "    #    print(\"t\"+str(u)+\",\"+str(v)+\" :\",\\\n",
    "    #          2*(2*optimal_node_values[u]-1)*(2*optimal_node_values[v]-1)+((sorted_weighted_edges[index])[(u,v)]))\n",
    "    \n",
    "    print()\n",
    "    print(\"Meso-scale measurements for instance\",index)\n",
    "    counter=collections.Counter(type_of_edge)\n",
    "    if (counter[1]+counter[3])>0:\n",
    "        print(\"Cohesiveness:\",(counter[3]/(counter[1]+counter[3])))\n",
    "    else:\n",
    "        print(\"Cohesiveness is undefined because there are no internal edges.\")\n",
    "    if (counter[-1]+counter[-3])>0:\n",
    "        print(\"Divisiveness:\",(counter[-3]/(counter[-1]+counter[-3])))\n",
    "    else:\n",
    "        print(\"Divisiveness is undefined because there are no external edges.\")\n",
    "    print()\n",
    "    \n",
    "    print(\"-\"*92)\n",
    "  \n",
    "    \n",
    "print(\"-\"*32,\"***  EXPERIMENT STATS  ***\",\"-\"*32)\n",
    "print(\"-\"*92)\n",
    "print(\"Frustration indices:\",np.around(objectivevalue))\n",
    "#print(\"Average frustrarion index\",np.mean(objectivevalue))\n",
    "#print(\"Frustration index Standard Deviation\",np.std(objectivevalue))\n",
    "#print()\n",
    "print(\"Solve times (in seconds):\",np.around(solveTime, decimals=2))\n",
    "#print(\"Average solve time\",np.mean(solveTime))\n",
    "#print(\"Solve time Standard Deviation\",np.std(solveTime))\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This code is for producing synthetic data (generating random \"directed signed graphs\" or signed digraphs for short)\n",
    "# \"Signed digraphs\" are digraphs in which edges are postive or negative (signed)\n",
    "# This code asks you for type of random digraph, several parameters for generating them such as size and order\n",
    "# and then it asks for \"number of negative edges\" so that it randomly makes some edges negative and produce \n",
    "# a signed digraph out of an unsigned digraph\n",
    "\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import random\n",
    "\n",
    "\n",
    "listOfGraphs=[]\n",
    "NumberOfNegative=[]\n",
    "run=int(input(\"How many random digraphs do you want to create?(1/2/...)\"))\n",
    "\n",
    "\n",
    "print(\"\\n 1.  Erdős-Rényi binomial graph G_{n,p} \"\n",
    "      \"\\n 2.  Random graph of n nodes and m total edges G_{n,m} \")\n",
    "\n",
    "graph_type=int(input(\"What type of random graph(s) do you want to create from the list above? (1/2)\"))\n",
    "\n",
    "for i in range(run):\n",
    "\n",
    "    if graph_type == 1:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        p=float(input(\"What is the probability of having an edge for each two nodes? (0.1, 0.5, ...)\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.fast_gnp_random_graph(n,p,directed=True)\n",
    "        listOfGraphs.append(G) \n",
    "    elif graph_type == 2:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        m=int(input(\"What is the total number of edges?\"))  \n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.gnm_random_graph(n,m,directed=True)\n",
    "        listOfGraphs.append(G)\n",
    "    else:\n",
    "        print(\"Try again and choose a graph type from the selection above!\")\n",
    "\n",
    "                    \n",
    "Graph_list=[]\n",
    "signedMatrix=[]\n",
    "unsignedMatrix=[]\n",
    "ShuffledEdges=[]\n",
    "sorted_weighted_edges=[]\n",
    "order=[]\n",
    "size=[]\n",
    "undirectedGraph=[]\n",
    "undirected_sorted_weighted_edges=[]\n",
    "\n",
    "\n",
    "for i in range(run):\n",
    "        ShuffledEdges = list(listOfGraphs[i].edges())\n",
    "        random.shuffle(ShuffledEdges)\n",
    "        Graph_list.append(nx.DiGraph())\n",
    "        for u in listOfGraphs[i].nodes():\n",
    "            Graph_list[i].add_node(u)\n",
    "        for ind in range(0,NumberOfNegative[i]):\n",
    "            (u,v) = ShuffledEdges[ind]\n",
    "            Graph_list[i].add_edge(u,v,weight=-1)\n",
    "        for ind in range(NumberOfNegative[i],len(listOfGraphs[i].edges())):\n",
    "            (u,v) = ShuffledEdges[ind]\n",
    "            Graph_list[i].add_edge(u,v,weight=1)\n",
    "        signedMatrix.append(nx.to_numpy_matrix(Graph_list[i]))\n",
    "        unsignedMatrix.append(abs(signedMatrix[i]))\n",
    "        #ShuffledEdges=[]\n",
    "\n",
    "        weighted_edges=nx.get_edge_attributes(Graph_list[i], 'weight') \n",
    "        sorted_weighted_edges.append({})\n",
    "        for (u,v) in weighted_edges:\n",
    "            (sorted_weighted_edges[i])[(u,v)] = weighted_edges[(u,v)]\n",
    "            \n",
    "        order.append(len(signedMatrix[i]))\n",
    "        size.append(int(np.count_nonzero(signedMatrix[i])))\n",
    "        \n",
    "        undirectedGraph.append((Graph_list[i]).to_undirected(as_view=True))\n",
    "        undirected_sorted_weighted_edges.append(nx.get_edge_attributes(undirectedGraph[i], 'weight'))\n",
    "          "
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}