diff options
| -rw-r--r-- | src/algorithms.py | 23 | ||||
| -rw-r--r-- | src/cascade_creation.py | 12 | ||||
| -rw-r--r-- | src/convex_optimization.py | 12 | ||||
| -rw-r--r-- | src/make_plots.py | 31 | ||||
| -rw-r--r-- | src/rip_condition.py | 4 |
5 files changed, 27 insertions, 55 deletions
diff --git a/src/algorithms.py b/src/algorithms.py index 5b07f78..c880a7b 100644 --- a/src/algorithms.py +++ b/src/algorithms.py @@ -2,7 +2,6 @@ import numpy as np import networkx as nx import cascade_creation from collections import Counter -from itertools import izip import convex_optimization import timeout @@ -15,7 +14,7 @@ def greedy_prediction(G, cascades): G_hat = cascade_creation.InfluenceGraph(max_proba=None) G_hat.add_nodes_from(G.nodes()) for node in G_hat.nodes(): - print node + print(node) # Avoid cases where infection time is None or 0 tmp = [cascade for cascade in cascades if cascade.infection_time(node) [0]] @@ -41,14 +40,14 @@ def recovery_l1obj_l2constraint(G, cascades, floor_cstt, passed_function, G_hat = cascade_creation.InfluenceGraph(max_proba=None) G_hat.add_nodes_from(G.nodes()) for node in G_hat.nodes(): - print node + print(node) try: M, w = cascade_creation.icc_matrixvector_for_node(cascades, node) p_node, __ = passed_function(M,w, *args, **kwargs) G_hat = cascade_creation.add_edges_from_proba_vector(G=G_hat, p_node=p_node, node=node, floor_cstt=floor_cstt) except timeout.TimeoutError: - print "TimeoutError, skipping to next node" + print("TimeoutError, skipping to next node") return G_hat @@ -69,14 +68,14 @@ def correctness_measure(G, G_hat, print_values=False): f1_score = 2.* tp / (2 * tp + fp + fn) if print_values: - print "False Positives: {}".format(fp) - print "False Negatives: {}".format(fn) - print "True Positives: {}".format(tp) - print "True Negatives: {}".format(tn) - print "-------------------------------" - print "Precision: {}".format(precision) - print "Recall: {}".format(recall) - print "F1 score: {}".format(f1_score) + print("False Positives: {}".format(fp)) + print("False Negatives: {}".format(fn)) + print("True Positives: {}".format(tp)) + print("True Negatives: {}".format(tn)) + print("-------------------------------") + print("Precision: {}".format(precision)) + print("Recall: {}".format(recall)) + print("F1 score: {}".format(f1_score)) return fp, fn, tp, tn diff --git a/src/cascade_creation.py b/src/cascade_creation.py index 1d77bd2..4c47d8b 100644 --- a/src/cascade_creation.py +++ b/src/cascade_creation.py @@ -1,7 +1,7 @@ import networkx as nx import numpy as np import collections -from itertools import izip +#from itertools import izip from sklearn.preprocessing import normalize class InfluenceGraph(nx.DiGraph): @@ -30,7 +30,7 @@ class InfluenceGraph(nx.DiGraph): def mat(self): if not hasattr(self, '_mat'): self._mat = (self.max_proba * np.random.rand(len(self), len(self)) - * np.asarray(nx.adjacency_matrix(self))) + * np.asarray(nx.adjacency_matrix(self).todense())) return self._mat @property @@ -52,7 +52,7 @@ class Cascade(list): Returns lists of infections times for node i in cascade """ infected_times = [] - for t, infected_set in izip(xrange(len(self)), self): + for t, infected_set in zip(range(len(self)), self): if infected_set[node]: infected_times.append(t) if not infected_times: @@ -96,7 +96,7 @@ def generate_cascades(G, p_init, n_cascades): """ returns list of cascades """"" - return [icc_cascade(G,p_init) for i in xrange(n_cascades)] + return [icc_cascade(G,p_init) for i in range(n_cascades)] def icc_matrixvector_for_node(cascades, node): @@ -116,10 +116,12 @@ def icc_matrixvector_for_node(cascades, node): t_i = cascade.infection_time(node)[0] if t_i != 0: indicator = np.zeros(len(cascade[:t_i])) - if t_i > 0: + if t_i: indicator[-1] = 1 w.append(indicator) M.append(np.array(cascade[:t_i])) + if not M: + print("Node {} was never infected at t != 0".format(node)) M = np.vstack(M) w = np.hstack(w) return M, w diff --git a/src/convex_optimization.py b/src/convex_optimization.py index 2661e25..02787d3 100644 --- a/src/convex_optimization.py +++ b/src/convex_optimization.py @@ -32,10 +32,10 @@ def sparse_recovery(M_val, w_val, lbda): y = (theta_).norm(1) + lbda * ( tensor.exp(M.dot(theta_)) - (1 - w)).norm(2) - return diff_and_opt(theta, theta_, M, w, lbda, y) + return diff_and_opt(theta, theta_, M, M_val, w, lbda, y) -def diff_and_opt(theta, theta_, M, w, lbda, y): +def diff_and_opt(theta, theta_, M, M_val, w, lbda, y): z = tensor.row().T z_ = z.flatten() @@ -60,15 +60,15 @@ def diff_and_opt(theta, theta_, M, w, lbda, y): cvxopt.matrix(y_diff.astype("float64")).T, \ cvxopt.matrix(y_hess.astype("float64")) - G = cvxopt.spdiag([1 for i in xrange(n)]) + G = cvxopt.spdiag([1 for i in range(n)]) h = cvxopt.matrix(0.0, (n,1)) cvxopt.solvers.options['show_progress'] = False try: theta = cvxopt.solvers.cp(F, G, h)['x'] except ArithmeticError: - print "ArithmeticError thrown, change initial point"+\ - " given to the solver" + print("ArithmeticError thrown, change initial point"+\ + " given to the solver") return 1 - np.exp(theta), theta @@ -83,7 +83,7 @@ def test(): A = cascade_creation.generate_cascades(G, .1, 2000) M_val, w_val = cascade_creation.icc_matrixvector_for_node(A, 0) p_vec, theta = l1obj_l2penalization(M_val, w_val, lbda) - print p_vec + print(p_vec) if __name__=="__main__": test() diff --git a/src/make_plots.py b/src/make_plots.py index 1951576..5aab683 100644 --- a/src/make_plots.py +++ b/src/make_plots.py @@ -6,32 +6,6 @@ import algorithms import rip_condition -def plot_rip_numberofnodes(max_proba, n_min, n_max, p_init, n_cascades, K_max): - """ - Plots the RIP constant for varying number of nodes (n_max included) - """ - x = np.arange(n_min, n_max+1) - y = [] - - for n_nodes in x: - print(n_nodes) - G = cascade_creation.InfluenceGraph(max_proba=.3) - G.erdos_init(n=n_nodes, p=.1) # TODO: handle different inits! - cascades = cascade_creation.generate_cascades(G, p_init=p_init, - n_cascades=n_cascades) - M, __ = cascade_creation.icc_matrixvector_for_node(cascades, None) - M = cascade_creation.normalize_matrix(M) - y.append(rip_condition.find_kth_rip_constants(M, 4)) # - - print(y) - - plt.clf() - plt.plot(x, y) - #plt.show() - - return x, y - - def compare_greedy_and_lagrange_cs284r(): """ Compares the performance of the greedy algorithm on the @@ -40,7 +14,7 @@ def compare_greedy_and_lagrange_cs284r(): """ G = cascade_creation.InfluenceGraph(max_proba = .8) G.import_from_file("../datasets/subset_facebook_SNAPnormalize.txt") - A = cascade_creation.generate_cascades(G, p_init=.05, n_cascades=2000) + A = cascade_creation.generate_cascades(G, p_init=.05, n_cascades=100) #Greedy G_hat = algorithms.greedy_prediction(G, A) @@ -57,9 +31,6 @@ def test(): """ unit test """ - if 0: - plot_rip_numberofnodes(max_proba=.3, n_min=30, n_max=30, - p_init=.01, n_cascades=100, K_max=4) if 1: compare_greedy_and_lagrange_cs284r() diff --git a/src/rip_condition.py b/src/rip_condition.py index fccf9a4..634895e 100644 --- a/src/rip_condition.py +++ b/src/rip_condition.py @@ -11,7 +11,7 @@ def find_kth_rip_constants(M, k): 1 - A_2 = arg min |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = kx """ delta = 0 - print M.shape + print(M.shape) for col_set in itertools.combinations(xrange(M.shape[1]), k): M_kcol = M[:,list(col_set)] delta_upper, delta_lower = upperlower_bound_rip(M_kcol) @@ -42,7 +42,7 @@ def test(): cascades = cascade_creation.generate_cascades(G, p_init=.3, n_cascades=10) M, __ = cascade_creation.icc_matrixvector_for_node(cascades, None) M = cascade_creation.normalize_matrix(M) - print find_kth_rip_constants(M, 5) + print(find_kth_rip_constants(M, 5)) if __name__=="__main__": |