pintrust_final.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> > >
#define double long double
mt19937 engine(time(NULL));
uniform_int_distribution<> dist(1, 4);
auto gen = bind(dist, engine);

ofstream out("myout.txt");
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();
         if (Ratingcnt == 0)return 0;
         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 0.8;
         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);
            vector<double> msg(2, 1);
            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가 너무 작아져 -nan나오는걸 방지
               NormalizeMessage(msg, 2);
            }
            
            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] / MSG[mp(k, i)][p];
               }
               //이 노멀라이즈는 정확도 차이가 없지만 혹시 모를 nan발생 대비를 위해 처리
               NormalizeMessage(msg_divided, 2);
               MSG[mp(i, k)] = PropagateMessage(i, k, msg_divided, 2, type);

               NormalizeMessage(MSG[mp(i, k)], 2);
            }
         }
         printf("iteration %d fin\n", ite);
         
      }

      // nomalize 되기 전 최종 belif score를 여기서 계산 함
      for (int i = 0; i < U; i++) {
         Globalmsg[i][0] = Globalmsg[i][1] = 1;
         for (int j = 0; j < adj[i].size(); j++) {
            int neighbor = adj[i][j].first;
            //multiply message
            Globalmsg[i][0] *= MSG[mp(neighbor, i)][0];
            Globalmsg[i][1] *= MSG[mp(neighbor, i)][1];
            NormalizeMessage(Globalmsg[i], 2);
         }
         //prior belief score
         Globalmsg[i][0] *= Belief[i][0];
         Globalmsg[i][1] *= Belief[i][1];
         

         NormalizeMessage(Globalmsg[i], 2);

      }
   }

   void RunAll() {
      run();

      BeliefScore.resize(U);
      for (int i = 0; i < U; i++) {
         BeliefScore[i].resize(2);
      }
      for (int i = 0; i < U; i++) {
         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;
int targetUser;

int main() {
   freopen("realinfo.txt", "r", stdin);

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

   int M; // 간선 개수
   targetUser = 131124; M = 841372; usernum = 131828;
   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;
   printf("끊긴 개수 %d\n", (int)cut.size());
   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, restore = 0;
   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())++restore;
      else if (alive.find(uu) != alive.end()) {
         ++hit;
      }
      if (i == 100 || i == 500 || i == 1000 || i == 2000) {
         out << "누적 개수 : " << i << endl;
         out << "전체 신뢰관계는 " << (int)alive.size() + (int)cut.size() << endl;
         out << "끊어지지 않았던 관계는 " << (int)alive.size() << "개 이고 이중 " << hit << "개가 들어왔습니다" << endl;
         out << "끊어졌던 관계는 " << (int)cut.size() << " 이고 이중 " << restore << "개가 들어왔습니다" << endl;
         
      }
   }
   out.precision(40);
   for (int i = 0; i <output.size(); i++) {
      double TS = -output[i].first;
      double DS = output[i].second.first;
      out << i << "번째유저 " << output[i].second.second << " : " << TS << ", " << DS << endl;
   }

   duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
   cout << "duration: " << duration << endl;

   return 0;
}