pintrust_v5.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<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];
      }
      if (sum <= 1e-12) {
         return;
      }
      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];
               }
            }

            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++) {
         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++) {
            Globalmsg[i][di] /= sum;
         }
         for (int di = 0; di < 2; di++) {
            BeliefScore[i][di] = Globalmsg[i][di];
         }
      }
   }

};


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

int main() {

   //freopen("/Users/bowbowbow/Desktop/pintrust/soc-Epinions1.txt", "r", stdin);
   //freopen("/Users/bowbowbow/Desktop/pintrust/soc-Epinions1_v1.output", "w", stdout);
   //freopen("Network3.txt", "r", stdin);
   //freopen("out3...번째.txt", "w", stdout);

   /**
   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;
   //usernum = 76000; targetUser = 0, M=508837;
   cin >> usernum >> targetUser >> M;
   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 >> distrust >> rating;
      if (trust)
         pinTrust.InputTrust(u, v);
      else
         pinTrust.InputDisTrust(u, v);
      // pinTrust.InputRating(u, v, 5);
   }
   pinTrust.RunAll();

   // belifScore 출력
   for (int i = 0; i<usernum; i++) {
      cout << "user " << i << " : (" << pinTrust.BeliefScore[i][0] << "," << pinTrust.BeliefScore[i][1] << ")" << endl;
   }

   return 0;
}

reverse edge 추가했고 그에 따라서 propagateMessage 전파행렬 호출이 조금 바뀜
그리고 propagationMatrix2, 3번에 size만 잡고 할당을 안해놨었어서 그것도 수정함

reverse edge안쓸 거면 adj[v].push_back({u, 2}), adj[v].push_back({u, 3}) 두줄만 주
석처리하면 됨