-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathformation.py
124 lines (96 loc) · 3.98 KB
/
formation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
''' code for network formation model'''
import networkx as nx
import numpy as np
from random import choice, choices, shuffle
from itertools import combinations
def new(N, alpha, Tau_a, Tau_b):
''' new graph with N many nodes '''
G = nx.Graph()
for node in range(N):
tau = np.random.beta(Tau_a, Tau_b)
type = choices(['orange','blue'], [alpha, 1-alpha])
# track iteration arrived, and new trust if changed
G.add_node(node+1, trust = tau, type = type[0], arrived = 0, new_trust = 0)
return G
def node_enters(G, alpha, Tau_a, Tau_b, it):
''' add a new node and mark it as new '''
tau = np.random.beta(Tau_a, Tau_b)
type = choices(['orange','blue'], [alpha, 1-alpha])
G.add_node(len(G.nodes())+1, trust = tau, type = type[0], arrived = it, new_trust = 0)
def christakis(G, recs, it):
''' run the christakis network formation model '''
# each node gets a pairing
node_list = list(G.nodes())
shuffle(node_list)
num_accepted_prop = 0
for node in node_list:
got_rec = False
trust_flag_rec = False
#if not transparent_entity:
trust = G.nodes[node]['trust']
#else:
#trust = G.nodes[node]['new_trust']
# if entity can see agent trust, pay them payment_prop of difference between their trust and 1
#if transparent_agent_trust:
# payment = payment_prop*(1 - trust)
# trust += payment
# money_spent_entity += payment
trust_flag = choices([1,0], [trust, 1-trust])[0]
# if the node chooses to trust the public entity, add that edge
# only if the recommended node trusts it too
if recs[node] is not None:
got_rec = True
rec_node = recs[node]
trust_rec = G.nodes[rec_node]['trust']
trust_flag_rec = choices([1,0], [trust_rec, 1-trust_rec])[0]
if trust_flag:
if trust_flag_rec:
G.add_edge(node, rec_node)
num_accepted_prop+=1
# if not, then do christakis network formation model
if not trust_flag or not trust_flag_rec or not got_rec:
# do pairing
node_pair = get_pairing(G, node, it)
# if the edge already exists, we might delete it
# this only happens in the case we pick a random node
if G.has_edge(node, node_pair):
if edge_util(G, node, node_pair) < 0 or edge_util(G, node_pair, node) < 0:
G.remove_edge(node, node_pair)
# if it didn't exist, we'll see if it should be added
else:
if edge_util(G, node, node_pair) > 0 and edge_util(G, node_pair, node) > 0:
G.add_edge(node, node_pair)
return num_accepted_prop
def get_pairing(G, node, it):
''' gets random (or not so random) pairing for christakis model '''
if G.nodes[node]['arrived'] == it:
node_pair = choice([x for x in list(G.nodes()) if x != node])
else:
choice_set = [x for x in list(G.nodes()) if nx.has_path(G, x, node) and nx.shortest_path_length(G, x, node) == 2]
if len(choice_set) == 0:
node_pair = choice([x for x in list(G.nodes()) if x != node])
else:
node_pair = choice(choice_set)
return node_pair
def edge_util(G, u, v):
''' returns utility to u from forming an edge with v '''
# params for this context based on original work
b1 = -1
b2 = 0
omega = .25
a1 = -.25
a2 = 0
a3 = 2.75
a4 = 1.25
eps = np.random.logistic()
x_u = 1 if G.nodes[u]['type'] == 'orange' else 0
x_v = 1 if G.nodes[v]['type'] == 'orange' else 0
deg_v = G.degree(v)
if nx.has_path(G, u, v):
uv_2 = 1 if nx.shortest_path_length(G, u, v) == 2 else 0
uv_3 = 1 if nx.shortest_path_length(G, u, v) == 3 else 0
else:
uv_2 = 0
uv_3 = 0
util = b1 + b2*x_v - (omega*(x_u-x_v)**2) + a1*deg_v + (a2*(deg_v)**2) + a3*uv_2 + a4*uv_3 + eps
return util