<file_sep>#!/usr/bin/env python
#<NAME>
#CSE 597C
import sys, os

def read_graph(file_el):
  print 'reading graph'
  fp = open(file_el, 'r')
  n, m = fp.readline().split()
  n = int(n)
  m = int(m)
  print 'Number of vertices: %d' % n
  print 'Number of edges: %d' % m
  print 'first open for degrees...'
  with open('./DOT/'+file_el[:-4]+'.dot', 'w+') as output:
    print 'opened new dot:'+'./DOT/'+file_el[:-4]+'.dot'
    output.write('strict graph {\n')
    for line in fp:
      u, v = line.split()
      u = int(u)
      v = int(v)
      if v > u:
        output.write("\t%d -- %d\n" % (u, v))
    output.write('}')
  fp.close()

if __name__ == "__main__":
  input_file_el = sys.argv[-1]
  print 'making dot file'
  read_graph(input_file_el)
<file_sep>#ifndef GRAPH_H
#define GRAPH_H
#include <igraph/igraph.h>
typedef struct {
  int n;          /* number of vertices */
  int m;          /* number of edges */
  int *adj;       /* adj[num_edges[i]..num_edges[i+1]-1] gives
                     vertices adjacent to vertex i */
  int *num_edges; /* num_edges[i+1]-num_edges[i] gives degree of
                     vertex i */
} graph_t;

int read_graph_file(char *filename, graph_t *g);
int read_to_igraph(char *filename, igraph_t *ig);
int read_vertex_names(char* vertex_ids_filename, char** v_names, int** name_offsets, int n);

#endif
<file_sep>import os, sys, json
import pickle
import numpy as np
import datetime
import Quandl

atoke = open("../../api_key.ig", 'r').read().strip()
def run():
  # Read in the symbols
  syms = []
  with open("../../WIKI_tickers.csv", 'r') as fp:
    fp.readline()
    for line in fp:
      syms.append(line.split(',')[0].strip())
  # Request the data for each symbol and store them in a dictionary
  for sym in syms:
    with open(os.path.join('../../data', sym.split('/')[1]), 'w+') as output:
      sym_data = Quandl.get(sym + ".1",returns="numpy",authtoken=atoke)
      pickle.dump(sym_data, output)
  


if __name__ == "__main__":
  run()
<file_sep>#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#include "graph.h"
#include "community_metrics.h"

#define SWAP_INTP(a,b) {int * t3mp; t3mp=(a); (a)=(b); (b)=t3mp;}
#define MAX_ITERS 100

// Structure and requisite comparison function //
typedef struct score_t{
  int edge;
  double score;
} score_t;

int score_cmp(const void* a, const void* b){
  score_t* A = (score_t*)a;
  score_t* B = (score_t*)b;
  return (int)(B->score - A->score);
}

///////////////////////////////////////////////////////////////////////////////
//////////////////////////// BEGIN ADAMIC /////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
score_t* calc_adamic(graph_t* g){
  score_t* edges   = calloc(g->n*g->n, sizeof(score_t));
  double* t_scores = calloc(g->n, sizeof(double));
  int* visited = calloc(g->n, sizeof(int));
  int i,j,k,x,y,z,numVisited,n=g->n;
  int numE=0;
  double t_score=0;
  int* has_edge = calloc(n, sizeof(int));

  for(x = 0; x < n; x++){
    numVisited=0;

    for(k = g->num_edges[x]; k < g->num_edges[x+1]; k++){
      z=g->adj[k];
      t_score = 1.0/log(g->num_edges[z+1]-g->num_edges[z]);
      for(j = g->num_edges[z]; j < g->num_edges[z+1]; j++){
        y = g->adj[j];
        if(y!=x && t_score!=0 && t_scores[y]==0) {
          visited[numVisited++]=y;
        }
        t_scores[y] += t_score;
      }
    }

    for(k = g->num_edges[x]; k < g->num_edges[x+1]; k++){
      has_edge[g->adj[k]] = 1;
    }

    //For each edge visited we now have calculated it's complete score so store
    //in the scores array
    for(i=0; i<numVisited; i++){
      y=visited[i];
      if(t_scores[y]==0 || has_edge[y]) continue;

      edges[numE++].edge = x*n + y;
      edges[numE].score = t_scores[y];

      //Clear data
      visited[i] = 0;
      t_scores[y] = 0;
    }

    for(k = g->num_edges[x]; k < g->num_edges[x+1]; k++){
      has_edge[g->adj[k]] = 0;
    }
  }

  qsort(edges, numE, sizeof(score_t), score_cmp);

  free(t_scores);
  free(visited);
  return edges;
}

///////////////////////////////////////////////////////////////////////////////
///////////////////////////// BEGIN KATZ //////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

int *list_to_matrix(graph_t *g) {
  int n = g->n;
  int *Adj = calloc(n*n, sizeof(int));
  int i, j;

  for (i=0; i < n; i++) {
    for (j=g->num_edges[i]; j < g->num_edges[i+1]; j++) {
      int u = g->adj[j];
      Adj[i*n + u] = 1;
    }
  }
  return Adj;
}

int *matrix_mult(int *A, int *B, int n) {
  int i, j, k;
  int *Adj = calloc(n*n, sizeof(int));
  for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
      int sum = 0;
      for (k=0; k < n; k++) {
        sum = sum + (A[i*n+k]*B[k*n+j]);
      }
      Adj[i*n+j] = sum;
    }
  }
  return Adj;
}

score_t *katz_it(graph_t *g, double beta) {
  int n = g->n;
  int i, j, k;
  double exp = beta;
  int* Adj = list_to_matrix(g);
  int* cpy = malloc(n*n*sizeof(int));
  int* temp = cpy;
  memcpy(cpy, Adj, n*n*sizeof(int));
  //initialize scores
  score_t *scores = calloc(n*n, sizeof(score_t));
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      scores[i*n + j].edge = i*n + j;
    }
  }
  // count paths of length 1 through 10
  for(i = 0; i < 10; i++) {
    fprintf(stderr, "Iter: %d\n", i);
    for (j = 0; j < n; j++) {
      for (k = 0; k < n; k++) {
        scores[j*n + k].score += temp[j*n + k] * exp;
      }
    }
    exp = exp * beta;
    temp = matrix_mult(Adj, cpy, n);
    free(cpy);
    cpy = temp;
  }

  //Filter out edges in existence
  for(i = 0; i < n; i++){
    scores[i*(n+1)].score = 0;
    for(j = g->num_edges[i]; j < g->num_edges[i+1]; j++){
      scores[i*n + g->adj[j]].score = 0;
    }
  }
  // sort the scores
  qsort(scores, n*n, sizeof(score_t), score_cmp);

  free(Adj);
  Adj = NULL;
  free(temp);
  temp = NULL;
  cpy = NULL;

  return scores;
}

//matrix_mult(graph_t* a, )
int main(int argc, char **argv) {

  char *input_graph_filename;
  char* vertex_ids_filename;
  char* v_names = 0x0;
  int* name_offsets = 0x0;
  graph_t g;
  char* files[4] = {"results/adamic_10.dat", "results/adamic_100.dat", "results/katz_10.dat", "results/katz_100.dat"};

  /* parse input args */
  if (argc != 4) {
    fprintf(stderr, "%s <edge list file> <vertex ids file> <beta>\n",
        argv[0]);
    exit(1);
  }


  double beta = atof(argv[3]);

  input_graph_filename = argv[1];
  vertex_ids_filename  = argv[2];

  read_graph_file(input_graph_filename, &g);
  read_vertex_names(vertex_ids_filename, &v_names, &name_offsets, g.n);

  score_t* links = calc_adamic(&g);

  ////////// Begin print code (ugly don't look) /////////////////

  FILE* f;
  f = fopen(files[0], "w");
  for(int i=0; i<10; i++){
    fprintf(f,"Edge: (%s,%s); Score: %f\n",
        v_names+name_offsets[links[i].edge/g.n],
        v_names+name_offsets[links[i].edge%g.n], links[i].score);
  }
  fclose(f);
  f = fopen(files[1], "w");
  for(int i=0; i<100; i++){
    fprintf(f,"Edge: (%s,%s); Score: %f\n",
        v_names+name_offsets[links[i].edge/g.n],
        v_names+name_offsets[links[i].edge%g.n], links[i].score);
  }
  // Give the probability for edges to not be connected to neighbors
  score_t *t;
  t = katz_it(&g, beta);
  fprintf(stderr, "The top predicted links and their scores:\n");
  for (int i = 0; i < 10; i++) {
    fprintf(stderr, "Edge: (%d,%d); Score: %f\n",
        t[i].edge/g.n, t[i].edge%g.n, t[i].score);
  }

  f = fopen(files[2], "w");
  for(int i=0; i<10; i++){
    fprintf(f,"Edge: (%s,%s); Score: %f\n",
        v_names+name_offsets[t[i].edge/g.n],
        v_names+name_offsets[t[i].edge%g.n], t[i].score);
  }
  fclose(f);

  f = fopen(files[3], "w");
  for(int i=0; i<100; i++){
    fprintf(f,"Edge: (%s,%s); Score: %f\n",
        v_names+name_offsets[t[i].edge/g.n],
        v_names+name_offsets[t[i].edge%g.n], t[i].score);
  }
  fclose(f);

  free(v_names);
  free(name_offsets);
  return 0;
}
<file_sep>#ifndef COMMUNITY_METRICS_H
#define COMMUNITY_METRICS_H
typedef struct {
  int size;
  int intra;
  int inter;
} c_density;

double modularity(const graph_t* g, const int* coms);
double min_intra_density(const graph_t* g, const c_density* densities);
double avg_conductance (const graph_t* g, const c_density* densities);
double coverage(const graph_t* g, const c_density* densities);

//Helper that calculates the number of intra and inter
//cluster edges per community
c_density* calc_edge_densities(const graph_t* g, const int* coms);
#endif
<file_sep>#<NAME>
#CSE 597C
import numpy as np
import matplotlib.pyplot as plt

def plot_deg_dist(x_list):
  x = np.array(x_list)
  fig = plt.figure()
  plt.hist(x)
  fig.suptitle('Degree Distribution')
  plt.xlabel('Degree (d)')
  plt.ylabel('Frequency')
  plt.yscale('log', nonposy='clip')
  plt.show()

def plot_assort(x_list, avg_list):
  x = np.array(x_list)
  y = np.array(avg_list)
  fig = plt.figure()
  plt.plot(x, y, 'o')
  fig.suptitle('Assortativity')
  plt.xlabel('Degree')
  plt.ylabel('Average neighbor degree')
  #plt.ylim([0,max(y)])
  plt.yscale('log', nonposy='clip')
  plt.xscale('log', nonposy='clip')
  plt.show()

def plot_cc(cc_list):
  prob = []
  cc = []
  for i in np.arange(0, 1, 0.01):
    cc.append(i)
    prob.append(float(sum(j < i for j in cc_list))/len(cc_list))
  fig = plt.figure()
  plt.plot(prob, cc, linewidth=2)
  fig.suptitle('Cluster Coefficient')
  plt.xlabel('Cluster Coefficient (c)')
  plt.ylabel('P(x <= c)')
  plt.show()
<file_sep>CC = gcc
EXEC = link_pred
GDB_EXEC = $(EXEC:%=g_%)
PROF_EXEC = $(EXEC:%=p_%)
HDIRS = -Ih -I/opt/local/include
CDIR = c/
CFLAGS = -Wall -std=gnu99 $(HDIRS)
LLIBS = -L/opt/local/lib -ligraph
LIBS = $(CDIR)graph.c $(CDIR)community_metrics.c 
RM = -rm -f


all: $(EXEC)

$(EXEC): % : $(CDIR)%.c $(LIBS)
	$(CC) -o $@ $(CFLAGS) -O3 $< $(LIBS) $(LLIBS)

$(GDB_EXEC): g_% : $(CDIR)%.c $(LIBS)
	$(CC) -o $@ $(CFLAGS) -ggdb3 $< $(LIBS) $(LLIBS)

$(PROF_EXEC): p_% : $(CDIR)%.c $(LIBS)
	$(CC) -o $@ $(CFLAGS) -O3 -pg $< $(LIBS) $(LLIBS)

clean:
	$(RM) $(EXEC) $(GDB_EXEC) $(PROF_EXEC)

#Print variable (for debugging Makefile)
#PHONY: all
#all: ; $(info $$GDB_EXEC is [${GDB_EXEC}])
<file_sep>Project Team: <NAME> and <NAME>

We implemented Adamic/Adar and Katz algorithm. Performance wise, Adamic/Adar
was far superior to Katz. For this reason, our implementation of Katz was
truncated to 10 iterations, i.e. up to paths of length 10. We got some
interesting results between the two of them. The top 10/100 list for
Adamic/Adar are included as adamic_10.dat and adamic_100.dat. The top 10/100
list of Katz is inclded as katz_10.dat and katz_100.dat. We ran the Katz link
prediction algorithm with a beta value of 0.05. In our test, beta = 0.05,
preformed the most sensibly.
<file_sep>import os, sys
import numpy as np
import pickle
import datetime
import math

# N is the number of days
# start is the first day
# load the symbol data into memory
def load_sym_data(N, start):
  data_path = '../data'
  syms = {}
  files = os.listdir(data_path)
  for f in files:
    with open(os.path.join(data_path, f), 'r') as fp:
      the_file = pickle.load(fp)
    found_start = False
    failed = False
    line = ''
    index = 0
    while not found_start and not failed:
      try:
        line = the_file[index]
        if line[0] >= start:
          found_start = True
        index += 1
      except IndexError:
        failed = True
        print the_file[index-1], index-1
    if not failed:
      syms[f] = []
      for i in range(index-1,index+N):
        try:
          syms[f].append(the_file[i][1])
        except IndexError:
          syms.pop(f, None)
          break
  # syms should now hold the correct dates and the associated prices for all the
  # stock symbols
  for sym in syms:
    print sym
    print syms[sym]
  return syms

# t is an index in the list of prices
# t = 0 represents the starting date
# t = 1 should be the starting point because of t-1
def R(sym, t):
  return math.log(syms[sym][t]/syms[sym][t-1])

# magic?
def Cij(sym_i, sym_j, N):
  RiRj = sum([R(sym_i, t)*R(sym_j,t) for t in range(1, N)])/N
  Ri_Rj = (sum([R(sym_i,t) for t in range(1, N)])/N)*(sum([R(sym_j,t) for t in range(1, N)])/N)
  top = RiRj - Ri_Rj
  vsRi = math.pow(sum([R(sym_i,t) for t in range(1, N)])/N, 2)
  vsRj = math.pow(sum([R(sym_j,t) for t in range(1, N)])/N, 2)
  bl = sum([math.pow(R(sym_i,t), 2) - vsRi for t in range(1, N)])/N
  br = sum([math.pow(R(sym_j,t), 2) - vsRj for t in range(1, N)])/N
  bottom = math.sqrt(bl*br)
  return top/bottom

if __name__ == "__main__":
  N = 250
  print 'N =', N, 'loading to memory'
  syms = load_sym_data(N, datetime.datetime(2012, 1, 2, 0, 0))
  theta = -0.1
  vertID = {}
  id = 0
  graph_path = '../graphs/'
  sample = 'dissim_first_250'
  with open(os.path.join(graph_path, sample+'_names.txt'), 'w+') as fp:
    for sym in syms:
      fp.write('%s\n' % sym)
      vertID[sym] = id
      id += 1
  m = 0
  with open(os.path.join(graph_path, sample+'_el.tmp'), 'w+') as fp:
    for sym_i in syms:
      for sym_j in syms:
        if sym_i != sym_j:
          #print 'Cij =', Cij(sym_i, sym_j, N), 'for i =', sym_i, 'and j =', sym_j
          temp = Cij(sym_i, sym_j, N)
          if temp < theta:
            print temp
            # add an edge
            m += 1
            fp.write('%d %d\n' % (vertID[sym_i], vertID[sym_j]))
  # the graph is now there, but we need the n and m values
  n = id
  with open(os.path.join(graph_path, sample+'_el.txt'), 'w+') as fp:
    fp.write('%s %s\n' % (n, m))
    fp2 = open(os.path.join(graph_path, sample+'_el.tmp'), 'r')
    for edge in fp2:
      fp.write(edge)
  os.system('rm '+os.path.join(graph_path, sample+'_el.tmp'))
<file_sep>#!/usr/bin/env python
#<NAME>
#CSE 597C
import sys, os
import my_plot

# design of g
#  n;          /* number of vertices */
#  m;          /* number of edges */
#  adj;        /* adj[num_edges[i]..num_edges[i+1]-1] gives 
#                 vertices adjacent to vertex i */
#  num_edges;  /* num_edges[i+1]-num_edges[i] gives degree of 
#                 vertex i */ 
def analyze(g):
  n = g['n']
  m = g['m']
  print 'finding degree distribution and assortitivity'
  # find degree distribution
  deg = []
  avg_deg = []
  for i in range(n):
    degree_i = g['num_edges'][i+1] - g['num_edges'][i]
    deg.append(degree_i)
    temp_degs = []
    for j in range(g['num_edges'][i], g['num_edges'][i+1]-1):
      u = g['adj'][j]
      degree_u = g['num_edges'][u+1] - g['num_edges'][u]
      temp_degs.append(degree_u) 
    if len(temp_degs) > 0:
      avg_deg.append(sum(temp_degs)/len(temp_degs))
    else:
      avg_deg.append(0)
      
  my_plot.plot_deg_dist(deg)
  my_plot.plot_assort(deg, avg_deg) 
  
  print 'finding clustering coefficient distribution'
  cluster_co = []
  for i in range(n):
    k_i = g['num_edges'][i+1] - g['num_edges'][i]
    t_g = (k_i*(k_i - 1))/2
    num_tris = 0.0
    temp_adj = {}
    for j in range(g['num_edges'][i], g['num_edges'][i+1]-1):
      temp_adj[g['adj'][j]] = True # use dict for const time check in N(i)
    for vert in temp_adj:
      for k in range(g['num_edges'][vert], g['num_edges'][vert+1]-1):
        u = g['adj'][k]
        if u in temp_adj:
          if temp_adj[u]:
            num_tris += 1
      temp_adj[vert] = False
    if t_g == 0:
      cluster_co.append(0)
    else:
      cc = num_tris/t_g
      cluster_co.append(cc)
  #print cluster_co
  print 'plotting cluster coefficient'
  my_plot.plot_cc(cluster_co)
  


  return 0

#essentially the python version of the read_graph function from centralities.c
def read_graph(file_el, file_names):

  print 'reading graph'
  fp = open(file_el, 'r')
  n, m = fp.readline().split()
  n = int(n)
  m = int(m)
  print 'Number of vertices: %d' % n
  print 'Number of edges: %d' % m
  print 'first open for degrees...'
  degrees = []
  for i in range(n):
    degrees.append(0)
  for line in fp:
    u, v = line.split()
    u = int(u)
    v = int(v)
    degrees[u] += 1
    degrees[v] += 1
  fp.close()
  
  num_edges = []
  adj = []
  num_edges.append(0)
  for i in range(1, n+1):
    num_edges.append(num_edges[i-1] + degrees[i-1])

  print 'second open for adjacency list'
  fp = open(file_el, 'r')
  fp.readline()
  for i in range(n):
    degrees[i] = 0
  for i in range(2*m):
    adj.append(0)
  for line in fp:
    u = int(line.split()[0])
    v = int(line.split()[1])
    uv_loc = num_edges[u] + degrees[u]
    vu_loc = num_edges[v] + degrees[v]
    adj[uv_loc] = v
    adj[vu_loc] = u
    degrees[u] += 1
    degrees[v] += 1

  g = {}
  g['n'] = n
  g['m'] = m
  g['num_edges'] = num_edges
  g['adj'] = adj

  print 'finished reading in graph'
  return g


if __name__ == "__main__":
  input_file_el = sys.argv[-2]
  input_file_names = sys.argv[-1]
  g = read_graph(input_file_el, input_file_names)
  analyze(g)
<file_sep>#include <stdlib.h>
#include <assert.h>
#include <omp.h>

#include "graph.h"
#include "assortivity_metrics.h"
#define NUM_THREADS 4
/*
   int count_triangle_e(graph_t* g){
//For each edge <u,v>
//  adj_intersect = Adj(u) \cap  Adj(v)
//  For each w \in adj_intersect
//    output {u,v,w}; count++
//    Note each triangle will be outputted/counted 3 times (remove u adj list as loop through maybe? aka <a,b> is valid edge iff a<b (no self loops))
//    O(m*d_{max}*n)
return 0;
}
*/
static int edge_intersect_cnt(int* adj1, int len1, int* adj2, int len2){
  int v_i1=0, v_i2=0, count=0;
  int v_1=adj1[v_i1], v_2 = adj2[v_i2];
  while(v_i1<len1 && v_i2<len2){
    v_1 = adj1[v_i1];
    v_2 = adj2[v_i2];
    if(v_1<v_2){ v_i1++;}
    else if(v_1==v_2) { count++; v_i1++; v_i2++;}
    else { v_i2++; }
  }
  return count;
}
double* local_cluster_coeffs(graph_t* g){
  //For each node u
  //  For each neighbor v
  //    neigh_edges+=|Adj(u)\cap Adj(v)|
  //O(n*deg_{max}^2)?
  double* cluster_coeffs = malloc(g->n*sizeof(double));
#pragma omp parallel num_threads(NUM_THREADS)
  {
    int deg_v, neigh_edges, u, deg_u, count;

    int tId = omp_get_thread_num();
    int loopFrom=g->n/NUM_THREADS*tId;
    int loopTo=(tId==NUM_THREADS-1) ? g->n : g->n/NUM_THREADS*(tId+1);

    for(int v = loopFrom; v<loopTo; v++){
      deg_v = DEG(g,v);
      neigh_edges=0;
      for(int u_i=g->num_edges[v]; u_i<g->num_edges[v+1]; u_i++){
        u=g->adj[u_i];
        deg_u = DEG(g,u);
        count = edge_intersect_cnt(&g->adj[g->num_edges[u]], deg_u,
            &g->adj[g->num_edges[v]], deg_v);
        neigh_edges+=count;
      }
      if(deg_v!=0 && deg_v-1!=0)
        cluster_coeffs[v]=((double)neigh_edges)/(deg_v*(deg_v-1));
    }
  }
  return cluster_coeffs;
}

#define CNT_IND(v) ((v)*2+1)
#define E_IND(v) ((v)*2)
double calc_assort(graph_t* g, double* avg_neigh_deg){
  //Find max degree so we can  alloc. an array of that size*2 for e_{ii}'s' and a count of verts with each deg
  int max_deg=0;
  for(int v=0; v<g->n; v++){
    int cur_deg = DEG(g,v);
    max_deg = (max_deg<cur_deg) ? cur_deg : max_deg;
  }
  int* assocs = calloc((max_deg+1)*2, sizeof(int));
  //Scan vert's incrementing the appropriate count by it's degree
  for(int v=0; v<g->n; v++){
    int cur_deg = DEG(g,v);
    assocs[CNT_IND(cur_deg)]++;
    //Scan the vert's neighbors, incrementing the appropriate e_{ii} if they are of the same degree
    for(int n_i=g->num_edges[v]; n_i<g->num_edges[v+1]; n_i++){
      int n = g->adj[n_i];
      int n_deg = DEG(g,n);
      if(cur_deg!=0) {avg_neigh_deg[v]+=((double)n_deg)/cur_deg;}
      //Count edges only once
      if(v<n){
        if(n_deg==cur_deg){
          assocs[E_IND(cur_deg)]++;
        }
      }
    }
  }

  //Calculate degree-based assortativity coefficient
  //See Newman, "Mixing patterns in networks" Section II
  double  e_sum=0;
  double  a_sum=0;
  for(int i=0; i<max_deg; i++){
    double a_i=0;
    e_sum += assocs[E_IND(i)];
    a_i = ((double)assocs[CNT_IND(i)])*i/g->m;
    a_sum += a_i*a_i;
  }
  e_sum/=g->m;
  free(assocs);
  return (e_sum - a_sum) /(1-a_sum);
}
#undef E_IND
#undef CNT_IND
<file_sep>#include <stdlib.h>
#include <assert.h>

#include "graph.h"
#include "community_metrics.h"

double modularity(const graph_t* g, const int* coms)
{
  double q=0;
  int* ttl_degs = calloc(g->n, sizeof(int));

  // k_i = degree of vertex i, A_{ij} = # of edges between i and j; m is number of edges
  // SUM(A_{ij} - k_i * k_j/2m) = SUM(A_{ij}) - SUM(k_i * SUM(k_j/2m)), where i,j are in the same community
  // SUM(k_j) = [total degree of community of vertex  i] - k_i
  // So we store the total degrees of all the communities here => O(n) time
  for(int v=0; v<g->n; v++){
    ttl_degs[coms[v]] += g->num_edges[v+1]-g->num_edges[v];
  }

  //Here we calculate k_i * SUM(k_j/2m) for all vertices i and subtracting  each to their respective communities
  //In effect calculating the -SUM(k_i * SUM(k_j/2m))
  //O(n) time
  for(int v=0; v<g->n; v++){
    int deg = g->num_edges[v+1] - g->num_edges[v];
    q -= deg*((ttl_degs[coms[v]]-deg)/(2.0*g->num_edges[g->n]));
  }

  //Add in 1 for each edge between two vertices in the same community
  //O(m)
  for(int s=0; s<g->n; s++){
    for(int t_i=g->num_edges[s]; t_i<g->num_edges[s+1]; t_i++){
      int t=g->adj[t_i];
      q += (coms[s]==coms[t]) ? 1 : 0;
    }
  }
  q/=g->num_edges[g->n];

  free(ttl_degs);
  return q;
  }

//Helper that calculates the number of intra and inter
//cluster edges per community
c_density* calc_edge_densities(const graph_t* g, const int* coms){
  int n = g->n;
  c_density* densities  = calloc(n, sizeof(c_density));
  for(int i=0; i<n; i++){
    densities[coms[i]].size++; //
    for(int j=g->num_edges[i]; j<g->num_edges[i+1]; j++){
      int vert=g->adj[j];
      (coms[i]==coms[vert]) ? densities[coms[i]].intra++ :  densities[coms[i]].inter++;
    }
  }
  for(int i=0; i<n; i++){
    assert(densities[i].intra%2==0);
    densities[i].intra/=2; //Counted each intra cluster edge twice
  }
  return densities;
}

double min_intra_density(const graph_t* g, const c_density* densities)
{
  double min = 1.0/0.0; //INFINITY
  double d;
  for(int i=0; i<g->n; i++){
    int sz = densities[i].size;
    if(sz!=0){
      d = (sz==1) ? 1 : (((double)densities[i].intra)/sz)/(sz-1);
      min = (min<d) ? min : d;
    }
  }
  return min;
}

double avg_conductance (const graph_t* g, const c_density* densities)
{
  int num_com=0;
  int g_deg = g->n;
  double total=0.0;

  //TODO: Parallel sum this
  for(int i = 0; i<g->n; i++){
    int sz=densities[i].size;
    if(sz!=0){
      int comm_deg = 2*densities[i].intra+densities[i].inter;//community degree
      int comp_deg = g_deg - comm_deg; //complement degree
      int min_deg = (comm_deg<comp_deg) ? comm_deg : comp_deg;
      if(min_deg!=0){
        total+=((double)densities[i].inter)/min_deg;
        num_com++;
      }
    }
  }
  return total/num_com;
}

double coverage(const graph_t* g, const c_density* densities)
{
  int num_intra = 0;
  int num_edges = g->num_edges[g->n];
  //TODO: Parallel sum this
  for(int i=0; i<g->n; i++){
    num_intra+=densities[i].intra;
  }
  return ((double)num_intra)/num_edges;
}

