Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGr_PageRankGX: pagerank for the LDBC Graphalytics (GX) 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 : // Originally contributed by Gabor Szarnyas and Balint Hegyi, Budapest
16 : // University of Technology and Economics (with accented characters: G\'{a}bor
17 : // Sz\'{a}rnyas and B\'{a}lint Hegyi, using LaTeX syntax).
18 :
19 : //------------------------------------------------------------------------------
20 :
21 : // This is an Advanced algorithm (G->AT and G->out_degree are required).
22 :
23 : // PageRank for the LDBC Graphalytics (GX) benchmark.
24 : // Do not use in production.
25 :
26 : // This algorithm follows the specification given in the LDBC Graphalytics
27 : // benchmark, see https://arxiv.org/pdf/2011.15028.pdf
28 :
29 : // The G->AT and G->out_degree cached properties must be defined for this
30 : // method. If G is undirected or G->A is known to have a symmetric structure,
31 : // then G->A is used instead of G->AT, however.
32 :
33 : #define LG_FREE_WORK \
34 : { \
35 : GrB_free (&d1) ; \
36 : GrB_free (&d) ; \
37 : GrB_free (&t) ; \
38 : GrB_free (&w) ; \
39 : GrB_free (&non_sink_mask) ; \
40 : GrB_free (&sink_vec) ; \
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_PageRankGX
52 : (
53 : // output:
54 : GrB_Vector *centrality, // centrality(i): GX-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 : int itermax, // maximum number of iterations (typically 100)
60 : char *msg
61 : )
62 : {
63 : //--------------------------------------------------------------------------
64 : // check inputs
65 : //--------------------------------------------------------------------------
66 :
67 3 : LG_CLEAR_MSG ;
68 3 : GrB_Vector r = NULL, d = NULL, t = NULL, w = NULL, d1 = NULL ;
69 3 : GrB_Vector non_sink_mask = NULL, sink_vec = NULL;
70 :
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 :
102 : // Determine vector of non-sink vertices:
103 : // These vertices are the ones which have outgoing edges. In subsequent
104 : // operations, this mask can be negated to select sink vertices.
105 3 : GRB_TRY (GrB_Vector_new (&non_sink_mask, GrB_BOOL, n)) ;
106 3 : GRB_TRY (GrB_reduce (non_sink_mask, NULL, NULL, GrB_LOR_MONOID_BOOL,
107 : G->A, NULL)) ;
108 :
109 : // Initialize vector for collecting the sink values
110 3 : GRB_TRY (GrB_Vector_new (&sink_vec, GrB_FP64, n)) ;
111 :
112 : // r = 1 / n
113 3 : GRB_TRY (GrB_Vector_new (&t, GrB_FP64, n)) ;
114 3 : GRB_TRY (GrB_Vector_new (&r, GrB_FP64, n)) ;
115 3 : GRB_TRY (GrB_Vector_new (&w, GrB_FP64, n)) ;
116 3 : GRB_TRY (GrB_assign (r, NULL, NULL, (float) (1.0 / n), GrB_ALL, n, NULL)) ;
117 :
118 : // prescale with damping factor, so it isn't done each iteration
119 : // d = d_out / damping ;
120 3 : GRB_TRY (GrB_Vector_new (&d, GrB_FP64, n)) ;
121 3 : GRB_TRY (GrB_apply (d, NULL, NULL, GrB_DIV_FP64, d_out, damping, NULL)) ;
122 :
123 : // d1 = 1 / damping
124 3 : float dmin = 1.0 / damping ;
125 3 : GRB_TRY (GrB_Vector_new (&d1, GrB_FP64, n)) ;
126 3 : GRB_TRY (GrB_assign (d1, NULL, NULL, dmin, GrB_ALL, n, NULL)) ;
127 : // d = max (d1, d)
128 3 : GRB_TRY (GrB_eWiseAdd (d, NULL, NULL, GrB_MAX_FP64, d1, d, NULL)) ;
129 3 : GrB_free (&d1) ;
130 :
131 : //--------------------------------------------------------------------------
132 : // pagerank iterations
133 : //--------------------------------------------------------------------------
134 :
135 303 : for ((*iters) = 0 ; (*iters) < itermax ; (*iters)++)
136 : {
137 : // swap t and r ; now t is the old score
138 300 : GrB_Vector temp = t ; t = r ; r = temp ;
139 :
140 : // sink value calculation
141 : // Extract all the sink PR entries from the previous result
142 300 : GRB_TRY (GrB_extract (sink_vec, non_sink_mask, NULL, t, GrB_ALL,
143 : n, GrB_DESC_SC)) ;
144 :
145 : // Sum the previous PR values of sink vertices together
146 : double sink_value;
147 300 : GRB_TRY (GrB_reduce (&sink_value, NULL, GrB_PLUS_MONOID_FP64,
148 : sink_vec, NULL )) ;
149 :
150 : // Multiply by damping factor and 1 / |V|
151 300 : sink_value *= (damping / n);
152 :
153 : // w = t ./ d
154 300 : GRB_TRY (GrB_eWiseMult (w, NULL, NULL, GrB_DIV_FP64, t, d, NULL)) ;
155 : // r = teleport + redistributed from sinks
156 300 : GRB_TRY (GrB_assign (r, NULL, NULL, teleport + sink_value, GrB_ALL,
157 : n, NULL)) ;
158 : // r += A'*w
159 300 : GRB_TRY (GrB_mxv (r, NULL, GrB_PLUS_FP64, LAGraph_plus_second_fp64,
160 : AT, w, NULL)) ;
161 : }
162 :
163 : //--------------------------------------------------------------------------
164 : // free workspace and return result
165 : //--------------------------------------------------------------------------
166 :
167 3 : (*centrality) = r ;
168 3 : LG_FREE_WORK ;
169 3 : return (GrB_SUCCESS) ;
170 : }
|
