From b49e39e300f9d87310f6cce20018427a98f34486 Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Sun, 30 Nov 2014 23:17:41 -0500 Subject: convex_optimization first draft --- jpa_test/algorithms.py | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) (limited to 'jpa_test/algorithms.py') diff --git a/jpa_test/algorithms.py b/jpa_test/algorithms.py index 2a32f57..cf4ce50 100644 --- a/jpa_test/algorithms.py +++ b/jpa_test/algorithms.py @@ -2,13 +2,14 @@ import numpy as np import networkx as nx import cascade_creation from collections import Counter - from itertools import izip +import convex_optimization def greedy_prediction(G, cascades): """ Returns estimated graph from Greedy algorithm in "Learning Epidemic ..." + TODO: write cleaner code? """ G_hat = cascade_creation.InfluenceGraph(max_proba=None) G_hat.add_nodes_from(G.nodes()) @@ -33,6 +34,19 @@ def greedy_prediction(G, cascades): return G_hat +def sparserecovery(G, cascades): + """ + Returns estimated graph from following convex program: + min |theta_1| + lbda | exp(M theta) -(1- w)| + where theta = log (1 - p); w = 1_{infected}; lbda = lagrange cstt + """ + G_hat = cascade_creation.InfluenceGraph(max_proba=None) + G_hat.add_nodes_from(G.nodes()) + for node in G_hat.nodes(): + M, w = cascade_creation.icc_matrixvector_for_node(cascades, node) + edges_node = convex_optimization.l1regls(M,w) + + def correctness_measure(G, G_hat): """ Measures correctness of estimated graph G_hat to ground truth G @@ -54,6 +68,9 @@ def test(): import time t0 = time.time() A = cascade_creation.generate_cascades(G, .1, 100) + + sparserecovery(G, A) + G_hat = greedy_prediction(G, A) fp, fn, gp = correctness_measure(G, G_hat) print "False Positive: {}".format(len(fp)) -- cgit v1.2.3-70-g09d2