AnoGraph/code/hcms.cpp at c9cee155ca8471558fb821f7048cf333ecb61f5b · Stream-AD/AnoGraph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
#include <algorithm>

#include "hcms.hpp"
#include "anoedgeglobal.hpp"
#include "anoedgelocal.hpp"
#include "anograph.hpp"
#include "anographk.hpp"
#include "utils.hpp"

using namespace std;

Hcms::Hcms(int r, int b) {
    num_rows = r;
    num_buckets = b;

    hash_a.resize(num_rows);
    hash_b.resize(num_rows);
    for (int i = 0; i < num_rows; i++) {
        hash_a[i] = rand() % (num_buckets - 1) + 1;
        hash_b[i] = rand() % num_buckets;
    }
    this->clear();
}

Hcms::Hcms(int r, int b, int d) {
    num_rows = r;
    num_buckets = b;
    num_dense_submatrices = d;

    hash_a.resize(num_rows);
    hash_b.resize(num_rows);
    for (int i = 0; i < num_rows; i++) {
        hash_a[i] = rand() % (num_buckets - 1) + 1;
        hash_b[i] = rand() % num_buckets;
    }
    this->clear();
}

int Hcms::hash(int elem, int i) {
    int resid = (elem * hash_a[i] + hash_b[i]) % num_buckets;
    return resid + (resid < 0 ? num_buckets : 0);
}

void Hcms::insert(int a, int b, double weight) {
    for (int i = 0; i < num_rows; i++) {
        int a_bucket = hash(a, i);
        int b_bucket = hash(b, i);
        count[i][a_bucket][b_bucket] += weight;
    }
}

double Hcms::getCount(int a, int b) {
    double min_count = numeric_limits<double>::max();
    for (int i = 0; i < num_rows; i++) {
        int a_bucket = hash(a, i);
        int b_bucket = hash(b, i);
        min_count = MIN(min_count, count[i][a_bucket][b_bucket]);
    }
    return min_count;
}

void Hcms::decay(double decay_factor) {
    for (int i = 0; i < num_rows; i++) {
        for (int j = 0; j < num_buckets; j++) {
            for (int k = 0; k < num_buckets; k++) {
                count[i][j][k] = count[i][j][k]*decay_factor;
            }
        }
    }
}

double Hcms::getAnoedgeglobalScore(string algorithm, int src, int dst) {
    double min_dsubgraph = numeric_limits<double>::max();
    for (int i = 0; i < num_rows; i++) {
        int src_bucket = hash(src, i);
        int dst_bucket = hash(dst, i);
        double cur_dsubgraph = AnoedgeGlobal::getAnoedgeglobalDensity(count[i], src_bucket, dst_bucket);
        min_dsubgraph = MIN(min_dsubgraph, cur_dsubgraph);
    }
    return min_dsubgraph;
}

void Hcms::intializeDenseSubmatrices() {
    for (int i = 0; i < num_rows; i++) {
        vector<Submatrix> cur_dense_submatrix;
        vector<pair<double, pair<int, int>>> flat_counts;
        for (int j = 0; j < num_buckets; j++) {
            for (int k = 0; k < num_buckets; k++) {
                flat_counts.push_back({count[i][j][k], {j, k}});
            }
        }
        sort(flat_counts.begin(), flat_counts.end(), greater<pair<double, pair<int, int>>>());
        for (int j = 0; j < num_dense_submatrices; j++) {
            Submatrix initial_submatrix(j, j, 0.0);
            cur_dense_submatrix.push_back(initial_submatrix);
        }
        densest_matrices.push_back(cur_dense_submatrix);
    }
}

double Hcms::getAnoedgelocalScore(string algorithm, int src, int dst) {
    double min_dsubgraph = numeric_limits<double>::max();
    for (int i = 0; i < num_rows; i++) {
        int src_bucket = hash(src, i);
        int dst_bucket = hash(dst, i);

        for (int j = 0; j < num_dense_submatrices; j++) {
            if (densest_matrices[i][j].checkAndAdd(src_bucket, dst_bucket, count[i])) {
                bool flag = true;
                int del_cnt = -1;
                while (flag) {
                    flag = densest_matrices[i][j].checkAndDel(count[i]);
                    del_cnt++;
                }
            }
        }

        double cur_dsubgraph = 0.0;
        for (int j = 0; j < num_dense_submatrices; j++) {
            double cur_likelihood = densest_matrices[i][j].getLikelihoodScore(src_bucket, dst_bucket, count[i]);
            cur_dsubgraph = cur_dsubgraph + cur_likelihood;
        }
        min_dsubgraph = MIN(min_dsubgraph, cur_dsubgraph);
    }
    return min_dsubgraph;
}

void Hcms::decay(double decay_factor, bool flag) {
    for (int i = 0; i < num_rows; i++) {
        for (int j = 0; j < num_buckets; j++) {
            for (int k = 0; k < num_buckets; k++) {
                count[i][j][k] = count[i][j][k]*decay_factor;
            }
        }
    }
    if (flag) {
        for (int i = 0; i < num_rows; i++) {
            for (int j = 0; j < num_dense_submatrices; j++) {
                densest_matrices[i][j].decay(decay_factor);
            }
        }
    }
}

double Hcms::getAnographScore(string algorithm) {
    double min_dsubgraph = numeric_limits<double>::max();
    for (int i = 0; i < num_rows; i++) {
        double cur_dsubgraph = Anograph::getAnographDensity(count[i]);
        min_dsubgraph = MIN(min_dsubgraph, cur_dsubgraph);
    }
    return min_dsubgraph;
}

double Hcms::getAnographKScore(string algorithm, int K) {
    double min_dsubgraph = numeric_limits<double>::max();
    for (int i = 0; i < num_rows; i++) {
        double cur_dsubgraph = AnographK::getAnographKDensity(count[i], K);
        min_dsubgraph = MIN(min_dsubgraph, cur_dsubgraph);
    }
    return min_dsubgraph;
}

void Hcms::clear() {
    count = vector<vector<vector<double>>>(num_rows, vector<vector<double>>(num_buckets, vector<double>(num_buckets, 0.0)));
}