path: root/src/hidden/hv_net.c

/**
 *  This program is free software: you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see
 *  <http://www.gnu.org/licenses/>.
 *
 *  (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk>
 * 
 *  This file is part of NetBunch, a package for complex network
 *  analysis and modelling. For more information please visit:
 *
 *             http://www.complex-networks.net/
 *
 *  If you use this software, please add a reference to 
 *
 *               V. Latora, V. Nicosia, G. Russo             
 *   "Complex Networks: Principles, Methods and Applications"
 *              Cambridge University Press (2017) 
 *                ISBN: 9781107103184
 *
 ***********************************************************************
 *
 *  This in an implementation of the hidden-variable model by Bogunya'
 *  and Pastor-Satorras. The program creates a random graph whose
 *  joint degree distribution is identical to that of a network given
 *  as input.
 *
 *  References:
 *  
 *  [1] M. Boguna and R. Pastor-Satorras. "Class of correlated random
 *  networks with hidden variables". Phys. Rev. E 68 (2003), 036112.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

#include "utils.h"
#include "cum_distr.h"


void usage(char *argv[]){
  printf("********************************************************************\n"
         "**                                                                **\n"
         "**                        -*-   hv_net   -*-                      **\n"
         "**                                                                **\n"
         "**   Create a random graph whose joint degree distribution is     **\n"
         "**   identical to that of a network provided as input.            **\n"
         "**                                                                **\n"
         "**   If 'graph_in' is equal to '-' (dash), read the edge list     **\n"
         "**   from STDIN.                                                  **\n"
         "**                                                                **\n"
         "**   The program prints on STDOUT the edge-list of the sampled    **\n"
         "**   graph.                                                       **\n"
         "**                                                                **\n"
         "**   If 'SHOW' is specified as second parameter, the program      **\n"
         "**   prints on STDERR the values of the hidden variable           **\n"
         "**   associated to each node and of the actual degree they have   **\n"
         "**   in the newly-created random graph, in the format:            **\n"
         "**                                                                **\n"
         "**       h_1 k_1                                                  **\n"
         "**       h_2 k_2                                                  **\n"
         "**       ...                                                      **\n"
         "**       h_N k_N                                                  **\n"
         "**                                                                **\n"
         "********************************************************************\n"
         " This is Free Software - You can use and distribute it under \n"
         " the terms of the GNU General Public License, version 3 or later\n\n"
         " (c) Vincenzo Nicosia 2009-2017 (v.nicosia@qmul.ac.uk)\n\n"
         "********************************************************************\n\n"
         );
  printf("Usage: %s <graph_in> [SHOW]\n", argv[0]);
}



typedef struct{
  unsigned int N;
  unsigned int K;
  unsigned int *J_slap;
  unsigned int *r_slap;
  unsigned int k_min;
  unsigned int k_max;
  double *pk; /* degree distribution -- this is equal to rho!!!! */
  double **pkk; /* joint degree distribution */
  double **f; /* the linking function */
  unsigned int *h; /* The array containing hidden variables for the N nodes */
  unsigned int *new_degs; /* the new degrees of the sampled graph */
} params_t;


/**
 * 
 * sample the hidden degrees of the nodes using the cumulative
 * distribution P(k)
 *
 */
void sample_node_variables(params_t *p, cum_distr_t *P){
  
  unsigned int i;
  unsigned int k;
  

  for(i=0; i<p->N; i++){
    k = cum_distr_sample(P);
    p->h[i] = k;
  }
}

/**
 *
 * Compute the function f(h,h') for each pair of degrees
 *
 */
void compute_fhh(params_t *p){
  
  unsigned int k1, k2;
  double avg_k;

  avg_k = 1.0 * p->K / p->N;
  
  for(k1 = p->k_min; k1 <= p->k_max; k1++){
    for(k2 = k1; k2 <= p->k_max; k2++){
      p->f[k1][k2] = p->f[k2][k1] = avg_k * p->pkk[k1][k2] / (p->N * p->pk[k1] * p->pk[k2]);
    }
  }
}



/**
 * 
 * Sample the edges of the graph
 *
 */
void sample_edges(params_t *p){
 
  unsigned int i, j, ki, kj;
  double val;

  for(i=0; i<p->N; i++){
    ki = p->h[i];
    for (j=i+1; j<p->N; j++){
      kj = p->h[j];
      val = 1.0 * rand() / RAND_MAX;
      /* we create the edge (i,j) with proability f[ki][kj]*/
      if (val < p->f[ki][kj]){
        printf("%d %d\n", i, j);
        p->new_degs[i] += 1;
        p->new_degs[j] += 1;
      }
    }
  }
}


void init_hv_params(params_t *p){
  
  unsigned int  i;

  p->h = malloc(p->N * sizeof(unsigned int));
  p->f = malloc((p->k_max + 1) * sizeof(double*));
  p->new_degs = malloc(p->N * sizeof(unsigned int));

  for(i=0; i<=p->k_max; i++){
    p->f[i] = malloc((p->k_max + 1) * sizeof(double));
  }
  for (i=0; i<p->N; i++){
    p->new_degs[i] = 0;
  }
}



void compute_distributions(params_t *g){
  
  unsigned int i,j, neigh, k1, k2;
  double sumk, sumkk;

  g->k_min = g->N;
  g->k_max = 0;
  
  g->pk = NULL;

  /* Compute (and allocate on the fly) the degree distribution */

  for(i=0; i< g->N; i ++){
    k1 = g->r_slap [i+1] - g->r_slap[i];
    if (k1 > g->k_max){
      g->pk = realloc(g->pk, (k1 + 1) * sizeof(double));
      for(j=g->k_max+1; j<=k1; j++){
        g->pk[j] = 0;
      }
      g->k_max = k1;
    }
    else if(k1 < g->k_min){
      g->k_min = k1;
    }
    g->pk[k1] += 1;
  }
  
  /* Allocate and initialise the joint degree distribution */
  g->pkk = malloc((g->k_max + 1 ) * sizeof(double*));
  for(i=0; i<=g->k_max ; i++){
    g->pkk[i] = malloc((g->k_max + 1) * sizeof(double));
    memset(g->pkk[i], 0, (g->k_max + 1) * sizeof(double));
  }
  
  for(i=0; i<g->N; i++){
    k1 = g->r_slap[i+1] - g->r_slap[i];
    for(j=g->r_slap[i]; j< g->r_slap[i+1]; j++){
      neigh = g->J_slap[j];
      k2 = g->r_slap[neigh+1] - g->r_slap[neigh];
      g->pkk[k1][k2] += 1;
    }
  }

  /* Now we normalise both pk and pkk...*/

  sumk = sumkk = 0.0;
  
  for(i=0; i<=g->k_max; i++){
    g->pk[i] /= g->N;
    sumk += g->pk[i];
    g->pkk[i][i] /= (g->K);
    sumkk += g->pkk[i][i];
    for(j=i+1; j<=g->k_max; j++){
      g->pkk[i][j] /= (g->K);
      g->pkk[j][i] = g->pkk[i][j];
      sumkk += 2* g->pkk[i][j];
    }
  }
    
}


void compute_rho(params_t *g, cum_distr_t *P){
  
  unsigned int k;

  for(k=g->k_min; k<= g->k_max; k++){

    if(g->pk[k] > 0){
      if (cum_distr_add(P, k, g->pk[k]) != 0){
        fprintf(stderr, "Error in the computation of the cumulative degree distribution!!!!"
               " Exiting!!!\n");
        exit(3);
      }
    }
  }
}

void dump_deg_h(params_t *p){

  unsigned int i;

  for(i=0; i<p->N; i++){
    fprintf(stderr, "%d %d\n", p->h[i], p->new_degs[i]);
  }
}


int main(int argc, char *argv[]){
  
  params_t p;
  cum_distr_t *P;
  int i;

  FILE *filein;


  if (argc < 2){
    usage(argv);
    exit(1);
  }

  srand(time(NULL));

  if (!strcmp(argv[1], "-")){
    /* take the input from STDIN */
    filein = stdin;
  }
  else {
    filein = openfile_or_exit(argv[1], "r", 2);
  }
  
  p.J_slap = p.r_slap = NULL;
  
  read_slap(filein, &(p.K), &(p.N), &(p.J_slap), &(p.r_slap));

  fclose(filein);
  
  compute_distributions(&p);

  init_hv_params(&p);
  
  P = cum_distr_init(p.k_max + 1);
  compute_rho(&p, P);
  compute_fhh(&p);
  
  sample_node_variables(&p, P);
  sample_edges(&p);
  
  /* 
   *  If 'SHOW' is provided, print on STDERR the value of the hidden
   *  variable of each node
   */
  if (argc > 2 && !my_strcasecmp(argv[2], "SHOW")){
    dump_deg_h(&p);
  }

  cum_distr_destroy(P);
  free(p.J_slap);
  free(p.r_slap);
  free(p.pk);
  free(p.h);
  free(p.new_degs);
  for(i=0; i<=p.k_max ; i++){
    free(p.pkk[i]);
    free(p.f[i]);
  }
  free(p.pkk);
  free(p.f);
}