Skip to content

Instantly share code, notes, and snippets.

@bowbowbow

bowbowbow/pintrust.cpp

Created November 7, 2017 06:48
Show Gist options
  • Save bowbowbow/69db6eb257c727566c65a79c4908e520 to your computer and use it in GitHub Desktop.
Save bowbowbow/69db6eb257c727566c65a79c4908e520 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
pintrust.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);
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
}
}
map<pair<int, int >, double> myFR;
double GetFR(int u, int v) {
return myFR[mp(u, 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];
//sum += log(Belief[u][q]) + log(psi[q][p]) + log(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();
for (int i = 0; i < U; i++) {
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
//MAT MSG = newMatrix(U, 2);
map<pair<int, int>, vector<double> > MSG;
//while not converged
for (int ite = 0; ite < 8; ite++) {
// for (int ty = 0; ty < 4; ty++) {
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
// if (ty != adj[i][j].second)continue;
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] += log10(MSG[mp(k, i)][di]);
}
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;
// if (type != ty)continue;
vector<double> msg_divided;
msg_divided = newMessage(2);
for (int p = 0; p < 2; p++) {
//msg_divided[p] = msg[p];
msg_divided[p] = msg[p] / MSG[mp(k, i)][p];
// msg_divided[p] -= log10(MSG[mp(k, i)][p]);//...
//너무 작으면 propagate할때 작은 값이 곱해져서 -nan나오는걸 방지
}
// double mini = min(msg_divided[0], msg_divided[1]);
// msg_divided[0] -= mini, msg_divided[1] -= mini;
// msg_divided[0] = pow(10, msg_divided[0]), msg_divided[1] = pow(10, msg_divided[1]);
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);
//Globalmsg[i][0] += log10(MSG[mp(neighbor, i)][0]);
//Globalmsg[i][1] += log10(MSG[mp(neighbor, i)][1]);
}
//prior belief score
Globalmsg[i][0] *= Belief[i][0];
Globalmsg[i][1] *= Belief[i][1];
//while (Globalmsg[i][0] < 0.1 && Globalmsg[i][1] < 0.1)Globalmsg[i][0] *= 10.0, Globalmsg[i][1] *= 10.0;
/*
Globalmsg[i][0] += log10(Belief[i][0]);
Globalmsg[i][1] += log10(Belief[i][1]);
double minV = min(Globalmsg[i][0], Globalmsg[i][1]);
Globalmsg[i][0] -= minV;
Globalmsg[i][1] -= minV;
Globalmsg[i][0] = pow(10, Globalmsg[i][0]);
Globalmsg[i][1] = pow(10, Globalmsg[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;//1e-1
double beta = 1e-5;//1e-6
double epsilon = 0.005;
double RF = 0.1;
int usernum = 10;
int targetUser = 0;
struct info {
int a, b;
double rate;
};
struct inputting {
int u, v, tr;
double rating;
};
int main(int argc, char ** argv) {
string cutRate(argv[1]);
cout << "cutRate : " << cutRate << endl;
int cutRateNum = stoi(cutRate);
cout << "cutRateNum : " << cutRateNum << endl;
clock_t start;
double duration;
start = clock();
int M; // 간선 개수
M = 841372; usernum = 131828;//120053, 121067, 122162
int u, v, trust, distrust;
double rating;
ifstream in("input.txt");
vector<inputting> fi, se;
int trcnt[1318888] = { 0, };
while (!(
in >> u >> v >> trust >> rating).eof()) {
if (trust == 1)trcnt[u]++;
fi.push_back({ u, v, trust, rating });
}
in.close();
in.open("zero_injection_only.txt");
while (!(
in >> u >> v >> rating).eof()) {
if (u < 0 || v < 0 || u >= 131828 || v >= 131828) {
puts("what"); continue;
}
se.push_back({ u, v, 0, rating });
}
ofstream out("myout_"+cutRate+".txt");
vector<int> targetarr = { 120053, 117979, 117517, 2586, 115058,
10695, 114376, 113465, 52620, 103690, 120302, 51143, 51655, 52188,
52334};
for (int iii = 0; iii < targetarr.size(); iii++) {
//if (!(25<= trcnt[targetarr[iii]] && trcnt[targetarr[iii]]<50))continue;//그룹 제한
int myfriend[131828] = { 0, }; myfriend[targetarr[iii]] = 1;
vector<info> hitsave, restoresave;
for (int jjj = 0; jjj < 1; jjj++) {
cout << targetarr[iii] << "번 유저 진행중" << endl;
int flag = 0;
int mmm = cutRateNum;//0이면 25%, 1이면 50%, 2이면 75%, 3이면 100%
set<int> cut, alive;
targetUser = targetarr[iii];
PinTrust pinTrust(alpha, beta, epsilon, RF, usernum, targetUser);
ifstream in("input.txt");
for (int i = 0; i < fi.size(); i++) {
u = fi[i].u, v = fi[i].v, trust = fi[i].tr, rating = fi[i].rating;
if (u == targetUser && (trust == 1)) {
int key = gen(); ++flag;
if (flag % 4 <= mmm) {
cut.insert(v);
continue;
}
alive.insert(v); myfriend[v] = 1;
}
if (trust == 1)
pinTrust.InputTrust(u, v);
else if (trust == -1) {
pinTrust.InputDisTrust(u, v);
}
else {
//if (u == targetUser)myfriend[v] = 1;
//if (pinTrust.Trust.find(mp(u, v)) != pinTrust.Trust.end())
if (u == targetUser)myfriend[v] = 1;;
pinTrust.myFR[mp(u, v)] = rating;
pinTrust.adj[u].push_back({ v, 0 });
pinTrust.adj[v].push_back({ u, 2 });
}
}
//if (jjj == 0)goto there;
int cnt[131828] = { 0, };
int tag = 0;
for (int i = 0; i < se.size(); i++) {
u = se[i].u, v = se[i].v, rating = se[i].rating;
if (!myfriend[u])continue;
if (cnt[u] == 400)continue;
if (u < 0 || v < 0 || u >= 131828 || v >= 131828) {
puts("what"); continue;
}
if (pinTrust.Trust.find({ u, v }) != pinTrust.Trust.end()) {
continue;
}
if (cnt[u] == 0)++tag;
cnt[u]++;
pinTrust.InputDisTrust(u, v);
}
printf("tag %d\n", tag);
//there:
int oo = (int)cut.size() + (int)alive.size();
printf("trust 는 %d\n", (int)cut.size() + (int)alive.size());
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());
out << fixed;
out.precision(1);
int hit = 0, restore = 0;
int sz1 = (int)alive.size();
int sz2 = (int)cut.size();
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;
}
double rate = 100.0*(double)hit / (double)sz1;
double rate2 = 100.0*(double)restore / (double)sz2;
if (i%oo == 0 && oo <= i && i <= 5 * oo) {
hitsave.push_back({ hit, sz1, rate }); restoresave.push_back({ restore, sz2, rate2 });
//out << "top " << i << ", " << hit << "/" << (int)alive.size() << "(" << 100.0*(double)hit / (double)sz1 << "%)"
// ", " << restore << "/" << (int)cut.size() << "(" << 100.0*(double)restore / (double)sz2 << "%)" << endl;
}
if (i > 5 * oo)break;
}
if (jjj == 0) {
out << targetUser << "user" << endl;
out << "[정확도]" << endl;
out << "전체 신뢰 관계 개수" << (int)alive.size() + (int)cut.size() << endl;
for (int i = 0; i < 5; i++) {
out << "top " << oo*(i + 1) << ", " << hitsave[i].a << "/" << sz1 << "(" << hitsave[i].rate << "%)"
<< ", " << restoresave[i].a << "/" << sz2 << "(" << restoresave[i].rate << "%)" << endl;
}
}
out << endl << endl;
duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
cout << "duration: " << duration << endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment