로그버전

pintrust_v6.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include "BigDecimal.h"
#include <ctime>
#include <cmath>
using namespace std;
#define mp make_pair

#define ll long long
#define MAT vector<vector<double> >
#define MAT2 vector<vector<pair<int, int> > >

struct PinTrust {
    int TargetUser, U;
    double alpha, beta, epsilon, RF;
    MAT Belief, BeliefScore;//prior belief, final belief score
    MAT2 adj;
    // 0:postive, 1:negative, 2:reverse positive, 3: reverse negative
    MAT propagationMatrix;
    //for each user, <trust,distrust> score
    MAT Globalmsg;
    map<pair<int, int>, int> Trust;
    map<pair<int, int>, int> DisTrust;
    map<pair<int, int>, vector<int> > Rating;
    
    PinTrust(double alpha, double beta, double epsilon, double RF, int U, int TargetUser) {
        this->alpha = alpha;
        this->beta = beta;
        this->epsilon = epsilon;
        this->RF = RF;
        this->U = U;
        this->TargetUser = TargetUser;
        MakeBeliefScore(U, 2);
        
        adj.resize(U);
    }
    void ChangeFactor(double alpha, double beta, double epsilon, double RF) {
        this->alpha = alpha;
        this->beta = beta;
        this->epsilon = epsilon;
        this->RF = RF;
        MakeBeliefScore(U, 2);
        
        adj.clear();
        adj.resize(U);
    }
    void InputTrust(int u, int v) {
        Trust[mp(u, v)] = 1;
    }
    void InputDisTrust(int u, int v) {
        DisTrust[mp(u, v)] = 1;
    }
    void InputRating(int u, int v, int R) {
        Rating[mp(u, v)].push_back(R);
    }
    void MakeBeliefScore(int U, int S) {
        Globalmsg.clear();
        Globalmsg.resize(U);
        for (int i = 0; i < U; i++) {
            Globalmsg[i].push_back(1);
            Globalmsg[i].push_back(1);
        }
        
        Belief.clear();
        Belief.resize(U);
        for (int i = 0; i < Belief.size(); i++)Belief[i].resize(S);
        for (int i = 0; i < Belief.size(); i++) {
            Belief[i][0] = 0.5 + beta;
            Belief[i][1] = 0.5 - beta;
        }
        Belief[TargetUser][0] = 0.5 + alpha;
        Belief[TargetUser][1] = 0.5 - alpha;
    }
    void MakeEdge0() {
        //P[i][j] = Trust[i][j] or Rating[i][j]
        map<pair<int, int>, int> tmpadj;
        for (auto &it : Trust) {
            int u = it.first.first;
            int v = it.first.second;
            tmpadj[mp(u, v)] = 1;
        }
        for (auto &it : Rating) {
            int u = it.first.first;
            int v = it.first.second;
            tmpadj[mp(u, v)] = 1;
        }
        for (auto &it : tmpadj) {
            int u = it.first.first;
            int v = it.first.second;
            adj[u].push_back({ v, 0 });
            adj[v].push_back({ u, 2 });////reverse positive
        }
    }
    void MakeEdge1() {
        for (auto &it : DisTrust) {
            int u = it.first.first;
            int v = it.first.second;
            adj[u].push_back({ v, 1 });
            adj[v].push_back({ u, 3 });//reverse negative
        }
    }
    double GetFR(int u, int v) {
        int Ratingcnt = 0;
        double Ratingavr = 0;
        if (Rating.find(mp(u, v)) != Rating.end()) {
            Ratingcnt = (int)Rating[mp(u, v)].size();
            
            auto tmp = Rating[mp(u, v)];
            for (int i = 0; i < tmp.size(); i++) {
                Ratingavr += tmp[i];
            }
            
            Ratingavr /= (double)Ratingcnt + (1e-9);
        }
        
        if (Ratingcnt == 0) {
            return 0;
        }
        if (Ratingcnt >= 64) {
            if (Ratingavr <= 3) {
                return 0;
            }
            if (Ratingcnt <= 127)return 0.75;
            if (Ratingcnt <= 255)return 8.0;
            if (Ratingcnt <= 511)return 0.85;
            return 0.85;
        }
        if (Ratingcnt == 1) {
            if (Ratingavr <= 3)return 0.01;
            return 0.05;
        }
        else if (Ratingcnt <= 3) {
            if (Ratingavr <= 3)return 0.01;
            return 0.1;
        }
        else if (Ratingcnt <= 7) {
            if (Ratingavr <= 3)return 0.01;
            return 0.3;
        }
        else if (Ratingcnt <= 15) {
            if (Ratingavr <= 3)return 0.02;
            return 0.4;
        }
        else if (Ratingcnt <= 31) {
            if (Ratingavr <= 3)return 0.03;
            return 0.55;
        }
        else if (Ratingcnt <= 63) {
            if (Ratingavr <= 3)return 0.02;
            return 0.7;
        }
        return 0;
    }
    //source -> destination
    MAT MakePropagationMatrix0(int u, int v) {
        propagationMatrix.clear();
        propagationMatrix.resize(2);
        for (int i = 0; i < 2; i++)propagationMatrix[i].resize(2);
        propagationMatrix[0][0] = propagationMatrix[1][1] = 0.5 + epsilon*((double)Trust[mp(u, v)] + GetFR(u, v));
        propagationMatrix[1][0] = propagationMatrix[0][1] = 0.5 - epsilon*((double)Trust[mp(u, v)] + GetFR(u, v));
        return propagationMatrix;
    }
    MAT MakePropagationMatrix1(int u, int v) {
        propagationMatrix.clear();
        propagationMatrix.resize(2);
        for (int i = 0; i < 2; i++)propagationMatrix[i].resize(2);
        propagationMatrix[0][0] = propagationMatrix[1][1] = 0.5 - epsilon;
        propagationMatrix[1][0] = propagationMatrix[0][1] = 0.5 + epsilon;
        return propagationMatrix;
    }
    MAT MakePropagationMatrix2(int u, int v) {
        propagationMatrix.clear();
        propagationMatrix.resize(2);
        for (int i = 0; i < 2; i++)propagationMatrix[i].resize(2);
        propagationMatrix[0][0] = propagationMatrix[1][1] = 0.5 + epsilon*((double)Trust[mp(u, v)] + GetFR(u, v))*RF;
        propagationMatrix[1][0] = propagationMatrix[0][1] = 0.5 - epsilon*((double)Trust[mp(u, v)] + GetFR(u, v))*RF;
        return propagationMatrix;
    }
    MAT MakePropagationMatrix3(int u, int v) {
        propagationMatrix.clear();
        propagationMatrix.resize(2);
        for (int i = 0; i < 2; i++)propagationMatrix[i].resize(2);
        propagationMatrix[0][0] = propagationMatrix[1][1] = 0.5 - epsilon*RF;
        propagationMatrix[1][0] = propagationMatrix[0][1] = 0.5 + epsilon*RF;
        return propagationMatrix;
    }
    MAT newMatrix(int U, int S) {
        MAT ret = vector<vector<double > >(U, vector<double>(S, 1));
        return ret;
    }
    vector<double> newMessage(int S) {
        vector<double> ret(S, 1);
        return ret;
    }
    // flag == what adj matrix(P, N, PR, NR) I have.
    vector<double> PropagateMessage(int u, int v, vector<double>& msgvalue, int S, int flag) {
        vector<double> msg = newMessage(S);
        MAT psi;
        if (flag == 0)psi = MakePropagationMatrix0(u, v);
        else if (flag == 1)psi = MakePropagationMatrix1(u, v);
        else if (flag == 2)psi = MakePropagationMatrix2(u, v);//!!!!!reverse edge자체를 반대로 넣어서
        else if (flag == 3)psi = MakePropagationMatrix3(u, v);
        
        for (int p = 0; p < S; p++) {
            double sum = 0;
            for (int q = 0; q < S; q++) {
                sum += Belief[u][q] * psi[q][p] * msgvalue[q];
            }
            msg[p] = sum;
        }
        return msg;
    }
    void NormalizeMessage(vector<double>& msg, int S) {
        double sum = 0;
        for (int i = 0; i < S; i++) {
            sum += msg[i];
        }
        for (int i = 0; i < S; i++) {
            msg[i] = msg[i] / sum;
        }
    }
    
    void run() {
        //To erase reciprocal, erase type 2, 3 edge inside these func.
        MakeEdge0();
        MakeEdge1();
        //MAT MSG = newMatrix(U, 2);
        map<pair<int, int>, vector<double> > MSG;
        //while not converged
        for (int ite = 0; ite < 30; ite++) {
            for (int i = 0; i < U; i++) {
                vector<double> msg = newMessage(2);
                for (int j = 0; j < adj[i].size(); j++) {
                    int k = adj[i][j].first; // neighbor
                    for (int di = 0; di < 2; di++) {
                        if (MSG.find(mp(k, i)) == MSG.end()) {
                            MSG[mp(k, i)].push_back(1.0);
                            MSG[mp(k, i)].push_back(1.0);
                        }
                        // msg[di] *= MSG[mp(k, i)][di];
                        msg[di] += log(MSG[mp(k, i)][di]);
                    }
                }
                // 로그 때문에 추가
                for (int di = 0; di < 2; di++) {
                    msg[di] = pow(10, msg[di]);
                }
                
                for (int j = 0; j < adj[i].size(); j++) {
                    int k = adj[i][j].first; // neighbor
                    int type = adj[i][j].second;
                    
                    vector<double> msg_divided;
                    msg_divided = newMessage(2);
                    for (int p = 0; p < 2; p++) {
                        msg_divided[p] = msg[p];
                        if (MSG[mp(k, i)][p] < 1e-10) continue;
                        msg_divided[p] = msg[p] / MSG[mp(k, i)][p];
                        //너무 작으면 propagate할때 작은 값이 곱해져서 -nan나오는걸 방지
                        if (msg_divided[p] < 1e-10)msg_divided[p] = 1e-10;
                    }
                    
                    MSG[mp(i, k)] = PropagateMessage(i, k, msg_divided, 2, type);
                    
                    NormalizeMessage(MSG[mp(i, k)], 2);
                }
            }
        }
        
        // nomalize 되기 전 최종 belif score를 여기서 계산 함
        for (int i = 0; i < U; i++) {
            double p = 0, q = 0;
            for (int j = 0; j < adj[i].size(); j++) {
                int neighbor = adj[i][j].first;
                //multiply message
                p += log(MSG[mp(neighbor, i)][0]);
                q += log(MSG[mp(neighbor, i)][1]);
            }
            p += log(Belief[i][0]);
            q += log(Belief[i][1]);
            
            double minV = min(p, q);
            p -= minV;
            q -= minV;
            
            p = pow(10, p);
            q = pow(10, q);
            
            Globalmsg[i][0] = p / (p+q);
            Globalmsg[i][1] = q / (p+q);
            

//            BigDecimal P("1"), Q("1");
//            double p = 0, q = 0;
//            for (int j = 0; j < adj[i].size(); j++) {
//                int neighbor = adj[i][j].first;
//                //multiply message
//                P *= MSG[mp(neighbor, i)][0];
//                Q *= MSG[mp(neighbor, i)][1];
//            }
//            P *= Belief[i][0];
//            Q *= Belief[i][1];
//            
//            BigDecimal i0 = P / (P + Q);
//            BigDecimal i1 = Q / (P + Q);
//            
//            Globalmsg[i][0] = i0.toDouble();
//            Globalmsg[i][1] = i1.toDouble();
//            
            
        }
    }
    
    void RunAll() {
        run();
        
        BeliefScore.resize(U);
        for (int i = 0; i < U; i++) {
            BeliefScore[i].resize(2);
        }
        for (int i = 0; i < U; i++) {
            double sum = 0;
            for (int di = 0; di < 2; di++) {
                sum += Globalmsg[i][di];
            }
            for (int di = 0; di < 2; di++) {
                Globalmsg[i][di] /= sum;
            }
            for (int di = 0; di < 2; di++) {
                BeliefScore[i][di] = Globalmsg[i][di];
            }
        }
    }
    
};


double alpha = 1e-2;
double beta = 1e-4;
double epsilon = 0.005;
double RF = 0.1;
int usernum = 10;
int targetUser = 0;

int main() {
    freopen("soc-sign-epinions.txt", "r", stdin);
    freopen("soc-sign-epinions_output_log.txt", "w", stdout);
    
    clock_t start;
    double duration;
    start = clock();
    
    int M; // 간선 개수
    targetUser = 0; M = 841372; usernum = 200000;
    PinTrust pinTrust(alpha, beta, epsilon, RF, usernum, targetUser);
    
    for (int ite = 0; ite < M; ite++) {
        int u, v, trust, distrust, rating;
        cin >> u >> v >> trust;
        
        if (trust == 1)
            pinTrust.InputTrust(u, v);
        else
            pinTrust.InputDisTrust(u, v);
    }
    pinTrust.RunAll();
    
    // belifScore 출력
    vector<pair<double, pair<double, int> > > output;
    for (int i = 0; i<usernum; i++) {
        output.push_back(mp(-pinTrust.BeliefScore[i][0], mp(pinTrust.BeliefScore[i][1], i)));
    }
    sort(output.begin(), output.end());
    int topK = 100;
    for (int i = 0; i < topK; i++) {
        double TS = -output[i].first;
        double DS = output[i].second.first;
        cout << "user " << output[i].second.second
        << " : " << "( " << TS << ", " << DS << " )" << endl;
    }
    for (int i = topK; i < output.size(); i++) {
        if (output[i].second.second == 0) {
            double TS = -output[i].first;
            double DS = output[i].second.first;
            cout << "user 0번은 " << TS << " , " << DS << endl; break;
        }
    }
    
    duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
    cout<<"duration: "<< duration << endl;
    
    return 0;
}