Program Listing for File GedWalk.hpp¶

/* GedWalk.hpp
 *
 *  Created on: 18.6.2018
 *     Authors: Eugenio Angriman <angrimae@hu-berlin.de>
 *              Alexander van der Grinten <avdgrinten@hu-berlin.de>
 */

#ifndef NETWORKIT_CENTRALITY_GED_WALK_HPP_
#define NETWORKIT_CENTRALITY_GED_WALK_HPP_

#include <networkit/auxiliary/VectorComparator.hpp>
#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

#include <tlx/container/d_ary_addressable_int_heap.hpp>

namespace NetworKit {

class GedWalk final : public Algorithm {

    using walks = double;

public:
    enum GreedyStrategy {
        LAZY,
        STOCHASTIC,
        lazy = LAZY, // this + following added for backwards compatibility
        stochastic = STOCHASTIC
    };

    enum BoundStrategy {
        NO,
        SPECTRAL,
        GEOMETRIC,
        ADAPTIVE_GEOMETRIC,
        no = NO, // this + following added for backwards compatibility
        spectral = SPECTRAL,
        geometric = GEOMETRIC,
        adaptiveGeometric = ADAPTIVE_GEOMETRIC
    };

    double stocEpsilon = 0.1;

private:
    const Graph *G;
    const count k;
    const double epsilon;
    double alpha;
    const BoundStrategy boundStrategy;
    GreedyStrategy greedyStrategy;
    double spectralDelta;
    double degOutMax;
    double degInMax;
    std::vector<double> alphas;

    // Size of pathsIn / pathsOut and related vectors.
    count allocatedLevels = 15;

    double sigmaMax;

    // Similar to gainScore, gainBound and gainW, but for the entire group.
    // These values are always maintained exactly.
    double groupScore; // Score of the group.
    walks groupW;      // Number of walks on the last level.
    walks groupBound;  // Upper bound on the score of the group.

    walks graphW;

    count nLevels = 2;
    std::vector<node> group;
    std::vector<unsigned char> inGroup;
    std::vector<unsigned char> isExact;
    std::vector<unsigned char> nodesToPick;
    std::vector<std::vector<walks>> pathsIn, pathsOut;
    std::vector<std::vector<walks>> pathsHit, pathsMiss;

    // Unless isExact[x], these values might be upper bounds on the true values.
    std::vector<double> gainScore; // Marginal score of the group.
    std::vector<walks> gainW;      // Number of marginal walks on the last level.
    std::vector<double> gainBound; // Upper bound on the marginal score.

    struct EvaluationResult {
        double score;
        walks w;
    };

    tlx::d_ary_addressable_int_heap<node, 2, Aux::GreaterInVector<double>> scoreQ{gainScore},
        boundQ{gainBound};

    void init();
    double computeGamma();
    void estimateGains();
    void computeMarginalGain(node z);
    void maximizeGain();
    bool separateNodes();
    double computeSigmaMax() const;
    void fillPQs();
    void updateAlphas();
    EvaluationResult evaluateGraph();
    EvaluationResult evaluateGroup();

public:
    GedWalk(const Graph &G, count k = 1, double initEpsilon = 0.1, double alpha = -1.,
            BoundStrategy bs = BoundStrategy::GEOMETRIC, GreedyStrategy gs = GreedyStrategy::LAZY,
            double spectralDelta = 0.5);

    void run() override;

    double getApproximateScore() const {
        assureFinished();
        return groupScore;
    }

    template <class InputIt>
    double scoreOfGroup(InputIt first, InputIt last, double scoreEpsilon = .1);

    std::vector<node> groupMaxGedWalk() const {
        assureFinished();
        return group;
    }

    const std::vector<double> &boundOfMarginalGains() const { return gainBound; }
};

template <class InputIt>
double GedWalk::scoreOfGroup(InputIt first, InputIt last, double scoreEpsilon) {
    if (boundStrategy == BoundStrategy::SPECTRAL) {
        assert(alpha * static_cast<double>(sigmaMax) < 1.);
    } else if (boundStrategy == BoundStrategy::GEOMETRIC) {
        assert(alpha * static_cast<double>(degInMax) < 1.);
    } else {
        assert(boundStrategy == BoundStrategy::ADAPTIVE_GEOMETRIC);
        assert(alpha * static_cast<double>(degOutMax + degInMax) < 1.);
    }

    std::fill(pathsHit[0].begin(), pathsHit[0].end(), walks{0});
    std::fill(pathsMiss[0].begin(), pathsMiss[0].end(), walks{1});
    std::fill(inGroup.begin(), inGroup.end(), static_cast<unsigned char>(0));
    while (first != last) {
        const auto u = *first;
        inGroup[u] = 1;
        pathsHit[0][u] = 1.0;
        pathsMiss[0][u] = 0.0;
        ++first;
    }

    graphW = evaluateGraph().w;

    do {
        const auto result = evaluateGroup();
        groupScore = result.score;
        groupW = result.w;
        if (boundStrategy == BoundStrategy::SPECTRAL) {
            const double gamma =
                std::sqrt(G->numberOfNodes()) * (sigmaMax / (1 - alpha * sigmaMax));
            groupBound = result.score + alphas[nLevels + 1] * gamma * graphW;
        } else if (boundStrategy == BoundStrategy::GEOMETRIC) {
            const double gamma = (degInMax / (1 - alpha * degInMax));
            groupBound = result.score + alphas[nLevels + 1] * gamma * graphW;
        } else {
            assert(boundStrategy == BoundStrategy::ADAPTIVE_GEOMETRIC);
            groupBound = result.score + alphas[nLevels + 1] * computeGamma() * result.w;
        }

        DEBUG("score is ", groupScore, ", bound is ", groupBound);
        if (groupBound < groupScore + scoreEpsilon)
            return groupScore;

        DEBUG("increasing path length to ", nLevels + 1);
        if (nLevels + 1 >= allocatedLevels) {
            DEBUG("allocating ", nLevels + 2, " GedWalk levels");
            while (allocatedLevels < nLevels + 2) {
                pathsIn.emplace_back((G->upperNodeIdBound()));
                pathsOut.emplace_back((G->upperNodeIdBound()));
                pathsHit.emplace_back((G->upperNodeIdBound()));
                pathsMiss.emplace_back((G->upperNodeIdBound()));
                ++allocatedLevels;
            }

            updateAlphas();
        }

        ++nLevels;
        graphW = evaluateGraph().w;
    } while (true);
}

} // namespace NetworKit
#endif // NETWORKIT_CENTRALITY_GED_WALK_HPP_