All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AlgebraicPageRank.h
Go to the documentation of this file.
1 /*
2  * AlgebraicPageRank.h
3  *
4  * Created on: Jun 20, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICPAGERANK_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICPAGERANK_H_
10 
11 #include "../../base/Algorithm.h"
12 #include "../../auxiliary/Parallel.h"
13 
14 #include "../../graph/Graph.h"
15 #include "../GraphBLAS.h"
16 #include "../Vector.h"
17 
18 namespace NetworKit {
19 
24 template<class Matrix>
25 class AlgebraicPageRank : public Algorithm {
26 public:
27 
35  AlgebraicPageRank(const Graph& graph, const double damp = 0.85, const double tol = 1e-8) : damp(damp), tol(tol) {
36  Matrix A = Matrix::adjacencyMatrix(graph);
37  // normalize At by out-degree
38  Vector invOutDeg = GraphBLAS::rowReduce(A);
39 #pragma omp parallel for
40  for (index i = 0; i < invOutDeg.getDimension(); ++i) {
41  invOutDeg[i] = 1.0/invOutDeg[i];
42  }
43 
44  std::vector<Triplet> mTriplets(A.nnz());
45  index idx = 0;
46  A.forNonZeroElementsInRowOrder([&](index i, index j, double value) {
47  mTriplets[idx++] = {j,i, damp * value * invOutDeg[i]};
48  });
49  M = std::move(Matrix(A.numberOfRows(), mTriplets));
50  }
51 
52  void run() override;
53 
59  std::vector<double> scores(bool moveOut = false);
60 
61 
67  std::vector<std::pair<node, double>> ranking();
68 
75  double score(node v);
76 
82  double maximum() {
83  return 1.0;
84  }
85 
86 private:
87  Matrix M;
88 
89  const double damp;
90  const double tol;
91 
92  std::vector<double> scoreData;
93  std::vector<double> edgeScoreData;
94 };
95 
96 template<class Matrix>
98  count n = M.numberOfRows();
99  double teleportProb = (1.0 - damp) / (double) n;
100  Vector rank(n, 1.0/(double)n);
101  Vector lastRank;
102 
103  do {
104  lastRank = rank;
105  rank = M * rank;
106  rank.apply([&](double value) {return value += teleportProb;});
107  } while ((rank - lastRank).length() > tol);
108 
109  double sum = 0.0;
110 #pragma omp parallel for reduction(+:sum)
111  for (index i = 0; i < rank.getDimension(); ++i) {
112  sum += rank[i];
113  }
114 
115  scoreData.resize(n, 0);
116 #pragma omp parallel for
117  for (index i = 0; i < rank.getDimension(); ++i) {
118  scoreData[i] = rank[i] / sum;
119  }
120 
121  hasRun = true;
122 }
123 
124 template<class Matrix>
125 std::vector<double> AlgebraicPageRank<Matrix>::scores(bool moveOut) {
126  if (!hasRun) throw std::runtime_error("Call run method first");
127  hasRun = !moveOut;
128  return moveOut ? std::move(scoreData) : scoreData;
129 }
130 
131 template<class Matrix>
132 std::vector<std::pair<node, double>> AlgebraicPageRank<Matrix>::ranking() {
133  if (!hasRun) throw std::runtime_error("Call run method first");
134  std::vector<std::pair<node, double> > ranking;
135  for (index i = 0; i < scoreData.size(); ++i) {
136  ranking.push_back({i, scoreData[i]});
137  }
138  Aux::Parallel::sort(ranking.begin(), ranking.end(), [](std::pair<node, double> x, std::pair<node, double> y) { return x.second > y.second; });
139  return ranking;
140 }
141 
142 template<class Matrix>
144  if (!hasRun) throw std::runtime_error("Call run method first");
145  return scoreData.at(v);
146 }
147 
148 } /* namespace NetworKit */
149 
150 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICPAGERANK_H_ */
double score(node v)
Get the betweenness score of node v calculated by run().
Definition: AlgebraicPageRank.h:143
double maximum()
Get the theoretical maximum of centrality score in the given graph.
Definition: AlgebraicPageRank.h:82
NetworKit::Vector rowReduce(const Matrix &matrix)
Computes the row-reduction of the matrix and returns the result as a vector.
Definition: GraphBLAS.h:278
std::vector< std::pair< node, double > > ranking()
Get a vector of pairs sorted into descending order.
Definition: AlgebraicPageRank.h:132
count getDimension() const
Definition: Vector.h:74
std::vector< double > scores(bool moveOut=false)
Get a vector containing the betweenness score for each node in the graph.
Definition: AlgebraicPageRank.h:125
uint64_t index
Typedefs.
Definition: Globals.h:20
Implementation of PageRank using the GraphBLAS interface.
Definition: AlgebraicPageRank.h:25
AlgebraicPageRank(const Graph &graph, const double damp=0.85, const double tol=1e-8)
Constructs an instance of AlgebraicPageRank for the given graph.
Definition: AlgebraicPageRank.h:35
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
index node
Definition: Globals.h:23
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
Definition: Algorithm.h:9
void apply(const F unaryElementFunction)
Applies the unary function unaryElementFunction to each value in the Vector.
Definition: Vector.h:322
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
void run() override
The generic run method which calls runImpl() and takes care of setting to the appropriate value...
Definition: AlgebraicPageRank.h:97