Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGr_PageRankGAP: pagerank for the GAP benchmark
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis and Mohsen Aznaveh, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // This is an Advanced algorithm (G->AT and G->out_degree are required).
19 :
20 : // PageRank for the GAP benchmark (only). Do not use in production.
21 :
22 : // This algorithm follows the specification given in the GAP Benchmark Suite:
23 : // https://arxiv.org/abs/1508.03619 which assumes that both A and A' are
24 : // already available, as are the row and column degrees. The GAP specification
25 : // ignores dangling nodes (nodes with no outgoing edges, also called sinks),
26 : // and thus shouldn't be used in production. This method is for the GAP
27 : // benchmark only. See LAGr_PageRank for a method that
28 : // handles sinks correctly. This method does not return a centrality metric
29 : // such that sum(centrality) is 1, if sinks are present.
30 :
31 : // The G->AT and G->out_degree cached properties must be defined for this
32 : // method. If G is undirected or G->A is known to have a symmetric structure,
33 : // then G->A is used instead of G->AT, however.
34 :
35 : #define LG_FREE_WORK \
36 : { \
37 : GrB_free (&d1) ; \
38 : GrB_free (&d) ; \
39 : GrB_free (&t) ; \
40 : GrB_free (&w) ; \
41 : }
42 :
43 : #define LG_FREE_ALL \
44 : { \
45 : LG_FREE_WORK ; \
46 : GrB_free (&r) ; \
47 : }
48 :
49 : #include "LG_internal.h"
50 :
51 3 : int LAGr_PageRankGAP
52 : (
53 : // output:
54 : GrB_Vector *centrality, // centrality(i): GAP-style pagerank of node i
55 : int *iters, // number of iterations taken
56 : // input:
57 : const LAGraph_Graph G, // input graph
58 : float damping, // damping factor (typically 0.85)
59 : float tol, // stopping tolerance (typically 1e-4) ;
60 : int itermax, // maximum number of iterations (typically 100)
61 : char *msg
62 : )
63 : {
64 :
65 : //--------------------------------------------------------------------------
66 : // check inputs
67 : //--------------------------------------------------------------------------
68 :
69 3 : LG_CLEAR_MSG ;
70 3 : GrB_Vector r = NULL, d = NULL, t = NULL, w = NULL, d1 = NULL ;
71 3 : LG_ASSERT (centrality != NULL, GrB_NULL_POINTER) ;
72 3 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
73 : GrB_Matrix AT ;
74 3 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
75 2 : G->is_symmetric_structure == LAGraph_TRUE)
76 : {
77 : // A and A' have the same structure
78 1 : AT = G->A ;
79 : }
80 : else
81 : {
82 : // A and A' differ
83 2 : AT = G->AT ;
84 2 : LG_ASSERT_MSG (AT != NULL,
85 : LAGRAPH_NOT_CACHED, "G->AT is required") ;
86 : }
87 3 : GrB_Vector d_out = G->out_degree ;
88 3 : LG_ASSERT_MSG (d_out != NULL,
89 : LAGRAPH_NOT_CACHED, "G->out_degree is required") ;
90 :
91 : //--------------------------------------------------------------------------
92 : // initializations
93 : //--------------------------------------------------------------------------
94 :
95 : GrB_Index n ;
96 3 : (*centrality) = NULL ;
97 3 : GRB_TRY (GrB_Matrix_nrows (&n, AT)) ;
98 :
99 3 : const float scaled_damping = (1 - damping) / n ;
100 3 : const float teleport = scaled_damping ; // teleport = (1 - damping) / n
101 3 : float rdiff = 1 ; // first iteration is always done
102 :
103 : // r = 1 / n
104 3 : GRB_TRY (GrB_Vector_new (&t, GrB_FP32, n)) ;
105 3 : GRB_TRY (GrB_Vector_new (&r, GrB_FP32, n)) ;
106 3 : GRB_TRY (GrB_Vector_new (&w, GrB_FP32, n)) ;
107 3 : GRB_TRY (GrB_assign (r, NULL, NULL, (float) (1.0 / n), GrB_ALL, n, NULL)) ;
108 :
109 : // prescale with damping factor, so it isn't done each iteration
110 : // d = d_out / damping ;
111 3 : GRB_TRY (GrB_Vector_new (&d, GrB_FP32, n)) ;
112 3 : GRB_TRY (GrB_apply (d, NULL, NULL, GrB_DIV_FP32, d_out, damping, NULL)) ;
113 :
114 : // d1 = 1 / damping
115 3 : float dmin = 1.0 / damping ;
116 3 : GRB_TRY (GrB_Vector_new (&d1, GrB_FP32, n)) ;
117 3 : GRB_TRY (GrB_assign (d1, NULL, NULL, dmin, GrB_ALL, n, NULL)) ;
118 : // d = max (d1, d)
119 3 : GRB_TRY (GrB_eWiseAdd (d, NULL, NULL, GrB_MAX_FP32, d1, d, NULL)) ;
120 3 : GrB_free (&d1) ;
121 :
122 : //--------------------------------------------------------------------------
123 : // pagerank iterations
124 : //--------------------------------------------------------------------------
125 :
126 55 : for ((*iters) = 0 ; (*iters) < itermax && rdiff > tol ; (*iters)++)
127 : {
128 : // swap t and r ; now t is the old score
129 52 : GrB_Vector temp = t ; t = r ; r = temp ;
130 : // w = t ./ d
131 52 : GRB_TRY (GrB_eWiseMult (w, NULL, NULL, GrB_DIV_FP32, t, d, NULL)) ;
132 : // r = teleport
133 52 : GRB_TRY (GrB_assign (r, NULL, NULL, teleport, GrB_ALL, n, NULL)) ;
134 : // r += A'*w
135 52 : GRB_TRY (GrB_mxv (r, NULL, GrB_PLUS_FP32, LAGraph_plus_second_fp32,
136 : AT, w, NULL)) ;
137 : // t -= r
138 52 : GRB_TRY (GrB_assign (t, NULL, GrB_MINUS_FP32, r, GrB_ALL, n, NULL)) ;
139 : // t = abs (t)
140 52 : GRB_TRY (GrB_apply (t, NULL, NULL, GrB_ABS_FP32, t, NULL)) ;
141 : // rdiff = sum (t)
142 52 : GRB_TRY (GrB_reduce (&rdiff, NULL, GrB_PLUS_MONOID_FP32, t, NULL)) ;
143 : }
144 :
145 : //--------------------------------------------------------------------------
146 : // free workspace and return result
147 : //--------------------------------------------------------------------------
148 :
149 3 : (*centrality) = r ;
150 3 : LG_FREE_WORK ;
151 3 : return (GrB_SUCCESS) ;
152 : }
|
