Program Listing for File KatzIndex.hpp¶

/*
 * KatzIndex.hpp
 *
 *  Created on: 30.01.2015
 *      Author: Kolja Esders
 */

#ifndef NETWORKIT_LINKPREDICTION_KATZ_INDEX_HPP_
#define NETWORKIT_LINKPREDICTION_KATZ_INDEX_HPP_

#include <unordered_map>

#include <networkit/linkprediction/LinkPredictor.hpp>

namespace NetworKit {

class KatzIndex final : public LinkPredictor {
    count maxPathLength;

    double dampingValue;

    node lastStartNode;

    std::unordered_map<node, double>
        lastScores;

    std::vector<double>
        dampingFactors;

    // Helper method used to access the score for a given node-pair. Checks which of the given nodes
    // was used as the starting node and uses the other node to access the last scores generated.
    // Defaults to 0.0 if no score could be found.
    double getScore(node u, node v) const;

    double runImpl(node u, node v) override;

    void calcDampingFactors();

public:
    explicit KatzIndex(count maxPathLength = 5, double dampingValue = 0.005);

    explicit KatzIndex(const Graph &G, count maxPathLength = 5, double dampingValue = 0.005);

    // Overriding this method is necessary as the implementation of the Katz index makes use
    // of caching. This makes run() not thread-safe. To still achieve performance gains
    // we split the nodePairs into subsets and create a new Katz instance for every subset.
    std::vector<LinkPredictor::prediction>
    runOn(std::vector<std::pair<node, node>> nodePairs) override;
};

} // namespace NetworKit

#endif // NETWORKIT_LINKPREDICTION_KATZ_INDEX_HPP_