pintrust_v3.cpp

pintrust_v3.cpp

#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define mp make_pair

#define MN 1000
int matrix[MN][MN];

#define MAT vector<vector<double> >
#define MAT2 vector<vector<pair<double, 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;
    
    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(int U) {
        //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});
        }
    }
    void MakeEdge1(int U) {
        for (auto &it : DisTrust) {
            int u = it.first.first;
            int v = it.first.second;
            adj[u].push_back({v, 1});
        }
    }
    
    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;
        }
        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);
        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);
        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(v, u);
        else if (flag == 3)psi = MakePropagationMatrix3(v, u);
        
        for (int i = 0; i < S; i++) {
            double sum = 0;//??
            for (int j = 0; j < S; j++) {
                sum += Belief[i][j] * psi[j][i] * msgvalue[j];
            }
            msg[i] = sum;
        }
        return msg;
    }
    void NormalizeMessage(vector<double>& msg, int S) {
        double sum = 0;
        for (int i = 0; i < S; i++) {
            sum += msg[i];
        }
        if (sum <= 1e-12) {
            return;
        }
        for (int i = 0; i < S; i++) {
            msg[i] = msg[i] / sum;
        }
    }
    
    void run() {
        //for each Matrix...makeEdge need!!!!
        MakeEdge0(U);
        // MakeEdge1(U);
        
        //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];
                    }
                }
                
                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.resize(2);
                    for (int di = 0; di < 2; di++) {
                        MSG[mp(k, i)][di] += 1e-12;//prevent being zero
                        msg_divided[di] = msg[di] / MSG[mp(k, i)][di];
                    }
                    MSG[mp(i, k)] = PropagateMessage(i, k, msg_divided, 2, type);
                }
            }
        }
        
        // nomalize 되기 전 최종 belif score를 여기서 계산 함
        for (int i = 0; i < U; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int neighbor = adj[i][j].first;
                //multiply message
                for (int di = 0; di < 2; di++) {
                    Globalmsg[i][di] *= MSG[mp(neighbor, i)][di];
                }
            }
            for (int di = 0; di < 2; di++) {
                Globalmsg[i][di] *= Belief[i][di];
            }
        }
        
    }
    
    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++) {
                if (sum != 0)
                    Globalmsg[i][di] /= sum;
                else
                    Globalmsg[i][di] = 0;
            }
            for (int di = 0; di < 2; di++) {
                BeliefScore[i][di] = Globalmsg[i][di];
            }
        }
    }
    
};


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

int main() {
    
    // freopen("/Users/bowbowbow/Desktop/soc-Epinions1.txt", "r", stdin);
    // freopen("/Users/bowbowbow/Desktop/soc-Epinions1.output", "w", stdout);
    
    /**
     예시 input
     
     5 1 5
     1 0 1 0 5
     2 0 1 0 5
     3 0 1 0 5
     4 0 1 0 5
     3 1 1 0 5
     **/
    
    /**
     12 1 15
     0 1 1 0 0
     1 2 1 0 0
     1 3 1 0 0
     3 4 1 0 0
     4 11 1 0 0
     5 11 1 0 0
     6 7 1 0 0
     7 8 1 0 0
     8 9 1 0 0
     9 7 1 0 0
     3 0 0 1 0
     3 6 0 1 0
     3 5 0 1 0
     7 2 0 1 0
     6 10 0 1 0
     **/
    
    /**
     0번과 1번이 서로 신뢰하고 1번과 2번이 서로 불신하는 관계인데
     0번 타겟유저에게 1과 2번유저의 신뢰도 차이가 없는 틀린 예시
     user 0 : (0.510014,0.489986)
     user 1 : (0.50001,0.49999)
     user 2 : (0.50001,0.49999)
     
     3 0 4
     0 1 1 0 0
     1 0 1 0 0
     1 2 0 1 0
     2 1 0 1 0
     **/
    
    int M; // 간선 개수
    cin >> usernum >> targetUser >> M;
    
    PinTrust pinTrust(alpha, beta, epsilon, RF, usernum, targetUser);
    
    for(int i=1;i<=M;i++) {
        int u, v, trust, distrust, rating;
        cin >> u >> v >> trust >> distrust >> rating;
        
        pinTrust.InputTrust(u, v);
    }
    
    pinTrust.RunAll();
    
    // belifScore 출력
    for(int i=0;i<usernum; i++) {
        cout << "user " << i << " : (" << pinTrust.BeliefScore[i][0] << "," << pinTrust.BeliefScore[i][1] << ")" << endl;
    }
    
    return 0;
}