pintrust_latest.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <ctime>
#include <fstream>
#include <cmath>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
#define mp make_pair

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

mt19937 engine(time(NULL));
uniform_int_distribution<> dist(1, 4);
auto gen = bind(dist, engine);
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 < 10; 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-5;
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);
   freopen("user_user_matrix.txt", "r", stdin);

   clock_t start;
   double duration;
   start = clock();

   int M; // 간선 개수
   targetUser = 5332; M = 841372; usernum = 233432;
   PinTrust pinTrust(alpha, beta, epsilon, RF, usernum, targetUser);

   int u, v, trust, distrust, rating;
   int flag = 0;
   set<int> cut, alive;;
   while (!(
      cin >> u >> v >> trust >> rating).eof()) {

      if (u == targetUser && trust == 1) {
         int key = gen();
         if (key == 1) {
            cut.insert(v);
            continue;
         }
         alive.insert(v);
      }

      if (trust == 1)
         pinTrust.InputTrust(u, v);
      else if (trust == -1) {
         pinTrust.InputDisTrust(u, v);
      }
      else {
         pinTrust.InputRating(u, v, rating);
      }
   }
   cout << "input ok" << endl;
   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 hit = 0, knum = 0;
   ofstream out("myout.txt");
   for (int i = 0; i < output.size(); i++) {
      double TS = -output[i].first;
      double DS = output[i].second.first;
      int uu = output[i].second.second;
      if (cut.find(uu) != cut.end())++hit, ++knum;
      else if (alive.find(uu) != alive.end()) {
         ++knum;
      }
      if (i == 27 || i == 50 || i == 100) {
         out << "누적 개수 : " << i << "  찾은 원래 정보개수 : " << knum << "  회복 개수: " << hit << endl;
      }
      if (knum == 27) {
         cout << "누적 개수 : " << i << "  찾은 원래 정보개수 : " << knum << "  회복 개수 : " << hit << endl;
         break;
      }
   }
   /*
   int topK = 100;
   for (int i = 0; i < topK; i++) {
   double TS = -output[i].first;
   double DS = output[i].second.first;
   out << "user " << output[i].second.second
   << " : " << "( " << TS << ", " << DS << " )" << endl;
   }
   */
   duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
   cout << "duration: " << duration << endl;

   return 0;
}