pintrust_log_and_bigfloat.py

from collections import defaultdict
import math
import bigfloat
import time


class Pintrust:
    # parameter
    target_user = 0  # 5332
    alpha = 1e-2
    beta = 1e-5
    eps = 0.005
    RF = 0.1
    user_num = 10  # 233432
    iteration = 10
    topk = 200

    # belief score
    prior_belief_score = []
    final_belief_score = []

    # file path
    input_file_path = "./user_user_matrix_test.txt"
    output_file_path = "./output.txt"

    # timer
    start_time = 0

    # input data
    trust = {}
    distrust = {}
    rating = {}

    adj = {}

    edge_type = {
        'positive': 0,
        'positive_reverse': 1,
        'distrust': 2,
        'distrust_reverse': 3
    }

    def __init__(self):
        self.start_time = time.time()

        self.init_belief_score()

        # set dictionary default value to list
        self.adj = defaultdict(lambda: [])
        self.rating = defaultdict(lambda: [])

    def check_time(self, title):
        print("[" + str(time.time() - self.start_time) + " seconds] [" + title + "]")

    def add_trust(self, u, v):
        self.trust[(u, v)] = 1

    def add_distrust(self, u, v):
        self.distrust[(u, v)] = 1

    def add_rating(self, u, v, r):
        self.rating[(u, v)].append(r)

    def init_belief_score(self):
        # init belief_score
        self.prior_belief_score = [[1.0, 1.0]] * self.user_num
        self.final_belief_score = [[1.0, 1.0]] * self.user_num

        for i in range(0, self.user_num):
            self.prior_belief_score[i] = [math.log10(0.5 + self.beta), math.log10(0.5 - self.beta)]

        self.prior_belief_score[self.target_user] = [math.log10(0.5 + self.alpha), math.log10(0.5 - self.alpha)]

    def make_trust_edge(self):
        tmp_adj = {}

        for key, value in self.trust.items():
            u = key[0]
            v = key[1]
            tmp_adj[(u, v)] = 1

        for key, value in self.rating.items():
            u = key[0]
            v = key[1]
            tmp_adj[(u, v)] = 1

        for key, value in tmp_adj.items():
            u = key[0]
            v = key[1]

            self.adj[u].append((v, self.edge_type['positive']))
            # reverse edge
            self.adj[v].append((u, self.edge_type['positive_reverse']))

    def make_distrust_edge(self):
        for key, value in self.distrust.items():
            u = key[0]
            v = key[1]

            self.adj[u].append((v, self.edge_type['distrust']))
            # reverse edge
            self.adj[v].append((u, self.edge_type['distrust_reverse']))

    def get_FR(self, u, v):
        rating_cnt = 0
        rating_sum = 0
        rating_aver = 0

        if (u, v) in self.rating:
            rating_cnt = len(self.rating[(u, v)])

            rating_list = self.rating[(u, v)]
            for r in range(len(rating_list)):
                rating_sum += r

            rating_aver = rating_sum / (rating_cnt + 1e-9)

        if rating_cnt == 0:
            return 0

        if rating_cnt >= 64:
            if rating_aver <= 3: return 0

            if rating_cnt <= 127: return 0.75
            if rating_cnt <= 255: return 0.80
            if rating_cnt <= 511: return 0.85
            return 0.85

        if rating_cnt == 1:
            if rating_aver <= 3:
                return 0.01
            else:
                return 0.05

        if rating_cnt <= 3:
            if rating_aver <= 3:
                return 0.01
            else:
                return 0.1

        if rating_cnt <= 7:
            if rating_aver <= 3:
                return 0.01
            else:
                return 0.3

        if rating_cnt <= 15:
            if rating_aver <= 3:
                return 0.02
            else:
                return 0.4

        if rating_cnt <= 31:
            if rating_aver <= 3:
                return 0.03
            else:
                return 0.55

        if rating_cnt <= 63:
            if rating_aver <= 3:
                return 0.02
            else:
                return 0.7

        return 0

    def get_propagation_matrix(self, u, v, edge_type):
        mat = [[0.0, 0.0], [0.0, 0.0]]

        trust_relation = 0
        if (u, v) in self.trust:
            trust_relation = 1

        if edge_type == self.edge_type['positive']:
            mat[0][0] = mat[1][1] = 0.5 + self.eps * trust_relation + self.get_FR(u, v)
            mat[1][0] = mat[0][1] = 0.5 - self.eps * trust_relation + self.get_FR(u, v)

        elif edge_type == self.edge_type['positive_reverse']:
            mat[0][0] = mat[1][1] = 0.5 + self.eps * trust_relation + self.get_FR(u, v) * self.RF
            mat[1][0] = mat[0][1] = 0.5 - self.eps * trust_relation + self.get_FR(u, v) * self.RF

        elif edge_type == self.edge_type['distrust']:
            mat[0][0] = mat[1][1] = 0.5 - self.eps
            mat[1][0] = mat[0][1] = 0.5 + self.eps

        elif edge_type == self.edge_type['distrust_reverse']:
            mat[0][0] = mat[1][1] = 0.5 - self.eps * self.RF
            mat[1][0] = mat[0][1] = 0.5 + self.eps * self.RF

        return mat

    def propagate_msg(self, u, v, divided_received_msg, edge_type):
        msg = [1.0, 1.0]

        psi = self.get_propagation_matrix(u, v, edge_type)

        trust_to_trust = self.prior_belief_score[u][0] + math.log10(psi[0][0]) + divided_received_msg[0]
        distrust_to_trust = self.prior_belief_score[u][1] + math.log10(psi[1][0]) + divided_received_msg[1]
        trust_to_distrust = self.prior_belief_score[u][0] + math.log10(psi[0][1]) + divided_received_msg[0]
        distrust_to_distrust = self.prior_belief_score[u][1] + math.log10(psi[1][1]) + divided_received_msg[1]

        mn = min(trust_to_trust, distrust_to_trust, trust_to_distrust, distrust_to_distrust)

        trust_to_trust -= mn
        distrust_to_trust -= mn
        trust_to_distrust -= mn
        distrust_to_distrust -= mn

        trust_to_trust = bigfloat.pow(10, trust_to_trust)
        distrust_to_trust = bigfloat.pow(10, distrust_to_trust)
        trust_to_distrust = bigfloat.pow(10, trust_to_distrust)
        distrust_to_distrust = bigfloat.pow(10, distrust_to_distrust)

        trust_probability = trust_to_trust + distrust_to_trust
        distrust_probability = trust_to_distrust + distrust_to_distrust

        sum = trust_probability + distrust_probability

        msg[0] = trust_probability / sum
        msg[1] = distrust_probability / sum

        return msg

    def normalize_msg(self, msg):
        sum = 0.0

        for i in range(0, 2):
            sum += msg[i]
        for i in range(0, 2):
            msg[i] = msg[i] / sum

        return msg

    def run_belief_propagation(self):
        self.make_trust_edge()
        self.make_distrust_edge()

        MSG = defaultdict(lambda: [1.0, 1.0])

        for ite in range(0, self.iteration):
            received_msg = [[0.0, 0.0]] * self.user_num
            for u in range(0, self.user_num):
                if u % 1000 == 0:
                    self.check_time("[received] user u : "+ str(u))

                for i in range(0, len(self.adj[u])):
                    edge = self.adj[u][i]
                    v = edge[0]

                    received_msg[u][0] += math.log10(MSG[(v, u)][0])
                    received_msg[u][1] += math.log10(MSG[(v, u)][1])

            for u in range(0, self.user_num):
                if u % 1000 == 0:
                    self.check_time("[propatae] user u : "+ str(u))
                for i in range(0, len(self.adj[u])):
                    edge = self.adj[u][i]
                    v = edge[0]
                    type = edge[1]

                    divided_received_msg = [0.0, 0.0]
                    for p in range(0, 2):
                        divided_received_msg[p] = received_msg[u][p] - math.log10(MSG[(v, u)][p])

                    MSG[(u, v)] = self.propagate_msg(u, v, divided_received_msg, type)

            self.check_time('iteration ' + str(ite) + ' finish')

        for u in range(0, self.user_num):
            msg = [0.0, 0.0]
            for i in range(0, len(self.adj[u])):
                edge = self.adj[u][i]
                v = edge[0]
                msg[0] += math.log10(MSG[(v, u)][0])
                msg[1] += math.log10(MSG[(v, u)][1])

            for p in range(0, 2):
                msg[p] = msg[p] + math.log10(self.prior_belief_score[u][p])

            mn = min(msg[0], msg[1])

            msg[0] -= mn
            msg[1] -= mn

            msg[0] = bigfloat.pow(10, msg[0])
            msg[1] = bigfloat.pow(10, msg[1])

            sum = msg[0] + msg[1]
            msg[0] = msg[0] / sum
            msg[1] = msg[1] / sum

            self.final_belief_score[u] = msg

    def run(self):
        self.check_time('start run pintrust')

        self.read_input()
        self.check_time('read_input finish')

        self.run_belief_propagation()
        self.check_time('run_belief_propagation finish')

        output = []
        for i in range(0, len(self.final_belief_score)):
            trust = self.final_belief_score[i][0]
            distrust = self.final_belief_score[i][1]
            output.append((i, trust, distrust))

        output.sort(key=lambda x: x[1], reverse=True)

        self.write_output(output)
        self.check_time('write_output finish')

    def read_input(self):
        f = open(self.input_file_path, "r")

        while True:
            line = f.readline()
            if not line: break
            p = line.split()

            u = int(p[0])
            v = int(p[1])
            t = int(p[2])
            r = int(p[3])

            if t == 0:
                pintrust.add_rating(u, v, r)
            elif t == 1:
                pintrust.add_trust(u, v)
            elif t == -1:
                pintrust.add_distrust(u, v)

        f.close()

    def write_output(self, output):
        f = open(self.output_file_path, "w")

        for i in range(0, min(len(output), self.topk)):
            u = str(output[i][0])
            trust = str(output[i][1])
            distrust = str(output[i][2])

            f.write("user: " + u + " (" + trust + "," + distrust + ") \n")

        f.close()

pintrust = Pintrust()
pintrust.run()