First commit on github -- NetBunch 1.0

1 files changed, 241 insertions, 0 deletions

diff --git a/src/bb_fitness/bb_fitness.c b/src/bb_fitness/bb_fitness.c
new file mode 100644
index 0000000..9f67c74
--- /dev/null
+++ b/src/bb_fitness/bb_fitness.c
@@ -0,0 +1,241 @@
+/**
+ *  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 program implements the fitness model proposed by Bianconi and
+ *  Barabasi, where the attachment probability is:
+ *
+ *     \Pi_{i->j} \propto a_j * k_j 
+ *
+ *  where a_j is the actractiveness of node j. 
+ *
+ *
+ *  References:
+ *  
+ * [1] G. Bianconi, A.-L. Barabasi, " Competition and multiscaling in
+ *     evolving networks". EPL-Europhys. Lett. 54 (2001), 436.
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "utils.h"
+#include "cum_distr.h"
+
+
+void usage(char *argv[]){
+  printf("********************************************************************\n"
+         "**                                                                **\n"
+         "**                        -*- bb_fitness -*-                      **\n"
+         "**                                                                **\n"
+         "**   Grow a network of 'N' nodes using the fitness model proposed **\n"
+         "**   by Bianconi and Barabasi.                                    **\n"
+         "**                                                                **\n"
+         "**   The initial network is a clique of 'n0' nodes, and each new  **\n"
+         "**   node creates 'm' edges. The attachment probability is of     **\n"
+         "**   the form:                                                    **\n"
+         "**                                                                **\n"
+         "**            P(i->j) ~ a_j * k_j                                 **\n"
+         "**                                                                **\n"
+         "**   where a_j is the attractiveness of node j. The values of     **\n"
+         "**   node attractiveness are sampled uniformly at random in       **\n"
+         "**   [0,1].                                                       **\n"
+         "**                                                                **\n"
+         "**   The program prints on STDOUT the edge-list of the final      **\n"
+         "**   graph.                                                       **\n"
+         "**                                                                **\n"
+         "**   If 'FIT' is specified as a fourth parameter, the values      **\n"
+         "**   of node attractiveness are printed on STDERR.                **\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 <N> <m> <n0> [SHOW]\n", argv[0]);
+}
+
+
+
+
+int init_network(unsigned int *I, unsigned int *J, int n0, 
+                 double *a, cum_distr_t *d){
+  
+  unsigned int n, i,  S_num;
+  
+  
+  S_num = 0;
+  for(n=0; n<n0; n++){
+    for(i=n+1; i<n0; i++){
+      I[S_num] = n;
+      J[S_num] = i % n0;
+      S_num += 1;
+    }
+    cum_distr_add(d, n, n0*a[n]);
+  }
+  return S_num;
+}
+
+int already_neighbour(unsigned int *J, int S_num, int j, int dest){
+
+   int i;
+
+   for(i=S_num; i< S_num + j; i ++){
+     if (J[i] == dest)
+       return 1;
+   }
+   return 0;
+}
+
+
+
+int bb_fitness(unsigned int *I, unsigned int *J, unsigned int N, 
+               unsigned int m, unsigned int n0,  double* a){
+  
+  cum_distr_t *d = NULL;
+  unsigned int n, j, dest, S_num;
+  
+  d = cum_distr_init(N * m);
+  
+  S_num = init_network(I, J, n0, a, d);
+  
+  
+  n = n0;
+  while (n<N){
+    for(j=0; j<m; j++){
+      I[S_num+j] = n;
+      dest = cum_distr_sample(d);
+      while(already_neighbour(J, S_num, j, dest)){
+        dest = cum_distr_sample(d);
+      }
+      J[S_num + j] = dest;
+    }
+    cum_distr_add(d, n, m*a[n]);
+    for (j=0; j<m; j++){
+      cum_distr_add(d, J[S_num + j], a[ J[S_num + j] ]);
+    }
+    S_num += m;
+    n += 1;
+  }
+  cum_distr_destroy(d);
+  return S_num;
+}
+
+void dump_graph(unsigned int *I, unsigned int *J, unsigned int K){
+  
+  unsigned int i;
+
+  for(i=0; i<K; i++){
+    printf("%d %d\n", J[i], I[i]);
+  }
+  
+}
+
+
+void init_fitness_uniform(double *a, unsigned int N){
+  
+  unsigned int i;
+
+  for(i=0; i<N; i++){
+    a[i] = 1.0 * rand() / RAND_MAX;
+  }
+  
+}
+
+
+void dump_fitness(double *a, unsigned int N){
+  
+  int i;
+
+  for(i=0; i<N; i++){
+    fprintf(stderr, "%g\n", a[i]);
+  }
+}
+
+
+int main(int argc, char *argv[]){
+  
+  int N, m, n0, K;
+  unsigned int *I, *J;
+  double *a;
+  
+  if (argc < 4){
+    usage(argv);
+    exit(1);
+  }
+  
+  N = atoi(argv[1]);
+  m = atoi(argv[2]);
+  n0 = atoi(argv[3]);
+  
+  a = malloc(N * sizeof(double));
+  
+  srand(time(NULL));
+
+  if (N < 1){
+    fprintf(stderr, "N must be positive\n");
+    exit(1);
+  }
+  if(m > n0){
+    fprintf(stderr, "n0 cannot be smaller than m\n");
+    exit(1);
+
+  }
+  if (n0<1){
+    fprintf(stderr, "n0 must be positive\n");
+    exit(1);
+  }
+  
+  if (m < 1){
+    fprintf(stderr, "m must be positive\n");
+    exit(1);
+  }
+  
+  I = malloc(N * m * sizeof(unsigned int));
+  J = malloc(N * m * sizeof(unsigned int));
+  a = malloc(N * sizeof(double));
+
+  init_fitness_uniform(a, N);
+  
+  K = bb_fitness(I, J, N, m, n0, a);
+  
+  dump_graph(I, J, K);
+  if (argc > 4 && !my_strcasecmp(argv[4], "SHOW")){
+    dump_fitness(a, N);
+  }
+  free(a);
+  free(I);
+  free(J);
+  
+}