All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
KatzIndex.h
Go to the documentation of this file.
1 /*
2  * KatzIndex.h
3  *
4  * Created on: 30.01.2015
5  * Author: Kolja Esders (kolja.esders@student.kit.edu)
6  */
7 
8 #ifndef KATZINDEX_H_
9 #define KATZINDEX_H_
10 
11 #include <unordered_map>
12 
13 #include "LinkPredictor.h"
14 
15 namespace NetworKit {
16 
25 class KatzIndex : public LinkPredictor {
26 private:
27  count maxPathLength;
28 
29  double dampingValue;
30 
31  node lastStartNode;
32 
33  std::unordered_map<node, double> lastScores;
34 
35  std::vector<double> dampingFactors;
36 
37  // Helper method used to access the score for a given node-pair. Checks which of the given nodes
38  // was used as the starting node and uses the other node to access the last scores generated.
39  // Defaults to 0.0 if no score could be found.
40  double getScore(node u, node v) const;
41 
50  double runImpl(node u, node v) override;
51 
57  void calcDampingFactors();
58 
59 public:
65  explicit KatzIndex(count maxPathLength = 5, double dampingValue = 0.005);
66 
73  explicit KatzIndex(const Graph& G, count maxPathLength = 5, double dampingValue = 0.005);
74 
75  // Overriding this method is necessary as the implementation of the Katz index makes use
76  // of caching. This makes run() not thread-safe. To still achieve performance gains
77  // we split the nodePairs into subsets and create a new Katz instance for every subset.
78  std::vector<LinkPredictor::prediction> runOn(std::vector<std::pair<node, node>> nodePairs) override;
79 
80 };
81 
82 } // namespace NetworKit
83 
84 #endif /* KATZINDEX_H_ */
Implementation of the Katz index.
Definition: KatzIndex.h:25
std::vector< LinkPredictor::prediction > runOn(std::vector< std::pair< node, node >> nodePairs) override
Executes the run-method on aĺl given nodePairs and returns a vector of predictions.
Definition: KatzIndex.cpp:63
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
KatzIndex(count maxPathLength=5, double dampingValue=0.005)
Definition: KatzIndex.cpp:16
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79