Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_HITS: Hyperlink-Induced Topic Search algorithm using GraphBLAS API
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 Aurko Routh, Texas A&M University
15 :
16 : // TODO: almost ready for src. this is advanced; add a basic method and add to src
17 : // TODO: rename to LAGr_HubsAndAuthorities?
18 :
19 : //------------------------------------------------------------------------------
20 :
21 : #define LG_FREE_WORK \
22 : { \
23 : GrB_free (&h_old) ; \
24 : GrB_free (&a_old) ; \
25 : }
26 :
27 : #define LG_FREE_ALL \
28 : { \
29 : LG_FREE_WORK ; \
30 : GrB_free(&h); \
31 : GrB_free(&a); \
32 : }
33 :
34 : #include "LAGraphX.h"
35 : #include "LG_internal.h"
36 :
37 : // Check graph with error messages if it's empty
38 :
39 6 : int LAGr_HITS
40 : (
41 : GrB_Vector *hubs,
42 : GrB_Vector *authorities,
43 : int *iters,
44 : const LAGraph_Graph G,
45 : float tol,
46 : int itermax,
47 : char *msg
48 : )
49 : {
50 :
51 6 : LG_CLEAR_MSG ;
52 6 : GrB_Vector h = NULL, a = NULL, h_old = NULL, a_old=NULL;
53 6 : LG_ASSERT (hubs != NULL, GrB_NULL_POINTER) ;
54 6 : LG_ASSERT (authorities != NULL, GrB_NULL_POINTER) ;
55 6 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
56 : GrB_Matrix AT ;
57 6 : GrB_Vector out_degree = G->out_degree, in_degree = NULL ;
58 6 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
59 3 : G->is_symmetric_structure == LAGraph_TRUE)
60 : {
61 : // A and A' have the same structure
62 3 : AT = G->A ;
63 3 : in_degree = out_degree ;
64 : }
65 : else
66 : {
67 : // A and A' differ
68 3 : AT = G->AT ;
69 3 : LG_ASSERT_MSG (AT != NULL,
70 : LAGRAPH_NOT_CACHED, "G->AT is required") ;
71 3 : in_degree = G->in_degree ;
72 : }
73 : // Initializations
74 : GrB_Index n;
75 6 : (*hubs) = NULL;
76 6 : (*authorities) = NULL;
77 6 : GRB_TRY(GrB_Matrix_nrows(&n, AT))
78 6 : float rdiff = 100;
79 :
80 6 : GRB_TRY (GrB_Vector_new (&h_old, GrB_FP32, n)) ;
81 6 : GRB_TRY (GrB_Vector_new (&a_old, GrB_FP32, n)) ;
82 6 : GRB_TRY (GrB_Vector_new (&h, GrB_FP32, n));
83 6 : GRB_TRY (GrB_Vector_new (&a, GrB_FP32, n)) ;
84 :
85 6 : float defaultValue = 1.0;
86 6 : GRB_TRY(GrB_assign(a, NULL, NULL, defaultValue, GrB_ALL, n, NULL));
87 6 : GRB_TRY(GrB_assign(h, NULL, NULL, defaultValue, GrB_ALL, n, NULL));
88 :
89 6 : bool flag = true ;
90 6 : if (in_degree != NULL && out_degree != NULL)
91 : {
92 6 : GrB_Index in_nonempty = 0, out_nonempty = 0 ;
93 : // Count the number of non-zero entries in the in_degree vector
94 6 : GRB_TRY (GrB_Vector_nvals(&in_nonempty, in_degree)) ;
95 : // Count the number of non-zero entries in the out_degree vector
96 6 : GRB_TRY (GrB_Vector_nvals(&out_nonempty, out_degree)) ;
97 6 : flag = (in_nonempty + out_nonempty) > n/16.0;
98 : }
99 :
100 267 : for((*iters) = 0; (*iters) < itermax && rdiff > tol; (*iters)++) {
101 : // Save old values of h and a
102 261 : GrB_Vector temp = h_old ; h_old = h ; h = temp ;
103 261 : temp = a_old ; a_old = a ; a = temp ;
104 :
105 261 : if(flag) {
106 : //a = 0
107 217 : GRB_TRY(GrB_assign(a, NULL, GrB_PLUS_FP32, 0.0, GrB_ALL, n, NULL));
108 : //h = 0
109 217 : GRB_TRY(GrB_assign(h, NULL, GrB_PLUS_FP32, 0.0, GrB_ALL, n, NULL));
110 : // a += AT . h
111 217 : GRB_TRY(GrB_mxv(a, NULL,NULL, LAGraph_plus_second_fp32, AT, h_old, NULL));
112 : // h += A . a
113 217 : GRB_TRY(GrB_mxv(h, NULL,NULL, LAGraph_plus_second_fp32, G->A, a_old, NULL));
114 : } else {
115 : // a = AT . h
116 44 : GRB_TRY(GrB_mxv(a, NULL,NULL, LAGraph_plus_second_fp32, AT, h_old, NULL));
117 : // h = A . a
118 44 : GRB_TRY(GrB_mxv(h, NULL,NULL, LAGraph_plus_second_fp32, G->A, a_old, NULL));
119 : }
120 :
121 : // float maxA;
122 : float sumA;
123 261 : GRB_TRY(GrB_reduce(&sumA, NULL, GrB_PLUS_MONOID_FP32, a, NULL)); // Calculate the sum of all elements in the vector
124 261 : GRB_TRY(GrB_assign(a, NULL, GrB_DIV_FP32, sumA, GrB_ALL, n, NULL)); // Divide all elements by the sum
125 :
126 : float sumH;
127 261 : GRB_TRY(GrB_reduce(&sumH, NULL, GrB_PLUS_MONOID_FP32, h, NULL)); // Calculate the sum of all elements in the vector
128 261 : GRB_TRY(GrB_assign(h, NULL, GrB_DIV_FP32, sumH, GrB_ALL, n, NULL)); // Divide all elements by the sum
129 :
130 : // Deal with tolerance
131 :
132 : // a_old -= a
133 261 : GRB_TRY (GrB_assign(a_old, NULL, GrB_MINUS_FP32, a, GrB_ALL, n, NULL));
134 :
135 : // a_old = abs(a_old)
136 261 : GRB_TRY(GrB_apply (a_old, NULL, NULL, GrB_ABS_FP32, a_old, NULL));
137 :
138 : // rdiff = sum(a_old)
139 261 : GRB_TRY(GrB_reduce (&rdiff, NULL, GrB_PLUS_MONOID_FP32, a_old, NULL));
140 :
141 : // h_old -= h
142 261 : GRB_TRY (GrB_assign (h_old, NULL, GrB_MINUS_FP32, h, GrB_ALL, n, NULL));
143 :
144 : // h_old = abs(h_old)
145 261 : GRB_TRY (GrB_apply (h_old, NULL, NULL, GrB_ABS_FP32, h_old, NULL));
146 :
147 : // rdiff += sum(h_old)
148 261 : GRB_TRY (GrB_reduce (&rdiff, GrB_PLUS_FP32, GrB_PLUS_MONOID_FP32, h_old, NULL)) ;
149 :
150 : // rdiff = rdiff/2
151 261 : rdiff /= 2;
152 : }
153 :
154 : // Normalize
155 : float sumA;
156 6 : GRB_TRY(GrB_reduce(&sumA, NULL, GrB_PLUS_MONOID_FP32, a, NULL)); // Calculate the sum of all elements in the vector
157 6 : GRB_TRY(GrB_assign(a, NULL, GrB_DIV_FP32, sumA, GrB_ALL, n, NULL)); // Divide all elements by the sum
158 :
159 : float sumH;
160 6 : GRB_TRY(GrB_reduce(&sumH, NULL, GrB_PLUS_MONOID_FP32, h, NULL)); // Calculate the sum of all elements in the vector
161 6 : GRB_TRY(GrB_assign(h, NULL, GrB_DIV_FP32, sumH, GrB_ALL, n, NULL)); // Divide all elements by the sum
162 :
163 6 : (*hubs) = h;
164 6 : (*authorities) = a;
165 6 : LG_FREE_WORK;
166 6 : return (GrB_SUCCESS);
167 : }
|
