rw.c
Go to the documentation of this file.
1 
11 #include <GKlib.h>
12 
13 
14 /*************************************************************************/
28 /**************************************************************************/
29 int gk_rw_PageRank(gk_csr_t *mat, float lamda, float eps, int max_niter, float *pr)
30 {
31  ssize_t i, j, k, iter, nrows;
32  double *rscale, *prold, *prnew, *prtmp;
33  double fromsinks, error;
34  ssize_t *rowptr;
35  int *rowind;
36  float *rowval;
37 
38  nrows = mat->nrows;
39  rowptr = mat->rowptr;
40  rowind = mat->rowind;
41  rowval = mat->rowval;
42 
43  prold = gk_dsmalloc(nrows, 0, "gk_rw_PageRank: prnew");
44  prnew = gk_dsmalloc(nrows, 0, "gk_rw_PageRank: prold");
45  rscale = gk_dsmalloc(nrows, 0, "gk_rw_PageRank: rscale");
46 
47  /* compute the scaling factors to get adjacency weights into transition
48  probabilities */
49  for (i=0; i<nrows; i++) {
50  for (j=rowptr[i]; j<rowptr[i+1]; j++)
51  rscale[i] += rowval[j];
52  if (rscale[i] > 0)
53  rscale[i] = 1.0/rscale[i];
54  }
55 
56  /* the restart distribution is the initial pr scores */
57  for (i=0; i<nrows; i++)
58  prnew[i] = pr[i];
59 
60  /* get into the PR iteration */
61  for (iter=0; iter<max_niter; iter++) {
62  gk_SWAP(prnew, prold, prtmp);
63  gk_dset(nrows, 0.0, prnew);
64 
65  /* determine the total current PR score of the sinks so that you
66  can distribute them to all nodes according to the restart
67  distribution. */
68  for (fromsinks=0.0, i=0; i<nrows; i++) {
69  if (rscale[i] == 0)
70  fromsinks += prold[i];
71  }
72 
73  /* push random-walk scores to the outlinks */
74  for (i=0; i<nrows; i++) {
75  for (j=rowptr[i]; j<rowptr[i+1]; j++)
76  prnew[rowind[j]] += prold[i]*rscale[i]*rowval[j];
77  }
78 
79  /* apply the restart conditions */
80  for (i=0; i<nrows; i++) {
81  prnew[i] = lamda*(fromsinks*pr[i]+prnew[i]) + (1.0-lamda)*pr[i];
82  }
83 
84  /* compute the error */
85  for (error=0.0, i=0; i<nrows; i++)
86  error = (fabs(prnew[i]-prold[i]) > error ? fabs(prnew[i]-prold[i]) : error);
87 
88  //printf("nrm1: %le maxfabserr: %le\n", gk_dsum(nrows, prnew, 1), error);
89 
90  if (error < eps)
91  break;
92  }
93 
94  /* store the computed pr scores into pr for output */
95  for (i=0; i<nrows; i++)
96  pr[i] = prnew[i];
97 
98  gk_free((void **)&prnew, &prold, &rscale, LTERM);
99 
100  return (int)(iter+1);
101 
102 }
103 
#define gk_SWAP(a, b, tmp)
Definition: gk_macros.h:19
int32_t * rowind
Definition: gk_struct.h:75
iterator iter(handle obj)
Definition: pytypes.h:2273
float * rowval
Definition: gk_struct.h:77
Real fabs(const Real &a)
#define rscale
Definition: gklib_rename.h:112
void gk_free(void **ptr1,...)
Definition: memory.c:202
ssize_t * rowptr
Definition: gk_struct.h:74
int32_t nrows
Definition: gk_struct.h:73
static double error
Definition: testRot3.cpp:37
int gk_rw_PageRank(gk_csr_t *mat, float lamda, float eps, int max_niter, float *pr)
Definition: rw.c:29
std::ptrdiff_t j
#define LTERM
Definition: gk_defs.h:14


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:35:35