<jupyter_start><jupyter_text>CELF<jupyter_code>def celf_steps_live_edges(p_initial_infect, p_infect, lists_infected_dicts, num_detectors, n=2029, debug=False):
    
    runs_per_marginal_node = len(lists_infected_dicts)
    
    print 'Running CELF to minimize simulation steps w/ live edges'
    results = open("CELF_steps_live_edges.txt", "w")
    results.write("P_infect = " + str(p_infect) + " P_initial_infect = " + str(p_initial_infect) + " Runs per marginal node = " + str(runs_per_marginal_node))
    results.write("\nNode ID\tReward so Far\tMarginal gain\tRuntime (minutes)\n")
    
    final_steps = []
    final_runtimes = []
    
    rewards_so_far = 39265
    
    marginals = []
    start_time = time.time()
    
    # how to calculate simulation steps: look thru the keys in the dictionary, if it is not in the keys, then we automatically fill it w/ the max number of simulation steps
    for potential_detector in range(1,n+1): # calculate marginals for each node
        runs = [infected_dict[potential_detector] if potential_detector in infected_dict.keys() else 39265 for infected_dict in lists_infected_dicts]
        heapq.heappush(marginals, (sum(runs)/float(runs_per_marginal_node) - rewards_so_far, potential_detector))
    
    best_tuple = heapq.heappop(marginals)
    best_node = best_tuple[1]
    marginal = best_tuple[0]
    rewards_so_far = marginal + rewards_so_far
    runtime = ( time.time() - start_time ) / 60
    selected_detectors = [best_node] # we have found our first best node
    
    print "We have our first best node: "
    print selected_detectors
    print "Runtime (minutes) = " + str( runtime )
    final_steps.append(rewards_so_far)
    final_runtimes.append(runtime)
    
    results.write(str(best_node) + '\t' + str(rewards_so_far) + '\t' + str(marginal) + '\t' + str(runtime) + '\n' )
    
    for i in range(1, num_detectors): # select the next 19 detectors
        
        if debug:
            print "Trying to find the " + str(i+1) + "th detector"
        
        # need to re-evaluate the top node once, at least
        old_top_tuple = heapq.heappop(marginals)
        old_top_node = old_top_tuple[1]
        new_detectors = list(selected_detectors)
        new_detectors.append(old_top_node)

        # lazily evaluate for the top node
        runs = [] # records the results for each run
        for run in range(runs_per_marginal_node): # go thru the runs
            infected_dict = lists_infected_dicts[run]
            if bool(set(new_detectors) & set(infected_dict.keys() )): # detector is in the set of infected ids
                alerted_detectors = set(new_detectors) & set(infected_dict.keys() )  # grab the set of detectors that was alerted
                alert_times = [infected_dict[detector] for detector in alerted_detectors]
                runs.append(min(alert_times)) # get the first time of alert
            else: # outbreak not detected, so last simulation step
                runs.append(39265)
            
        heapq.heappush(marginals, (sum(runs) / float(runs_per_marginal_node) - rewards_so_far, old_top_node))
        new_top_tuple = heapq.heappop(marginals)
        new_top_node = new_top_tuple[1]
        
        while new_top_node != old_top_node: # this is where we need to re-evaluate the next top node
            old_top_node = new_top_node
            new_detectors = list(selected_detectors)
            new_detectors.append(old_top_node)
            
            runs = [] # records number of runs
            for run in range(runs_per_marginal_node): # go thru the runs
                infected_dict = lists_infected_dicts[run]
                if bool(set(new_detectors) & set(infected_dict.keys())): # detector is in the set of infected ids
                    alerted_detectors = set(new_detectors) & set(infected_dict.keys() ) # grab the set of detectors that was alerted
                    alert_times = [infected_dict[detector] for detector in alerted_detectors]
                    runs.append(min(alert_times)) # get the first time of alert
                else: # outbreak not detected, so last simulation step
                    runs.append(39265)            
            
            heapq.heappush(marginals, (sum(runs) / float(runs_per_marginal_node) - rewards_so_far, old_top_node))

            new_top_tuple = heapq.heappop(marginals)
            new_top_node = new_top_tuple[1]
        
        best_node = new_top_node
        
        print "After doing CELF, we have found the " + str (i+1) + "th detector w/ best marginal gain = " + str(best_node)
        selected_detectors.append(best_node)
        runtime = (time.time() - start_time)/60
        rewards_so_far = rewards_so_far + new_top_tuple[0] # update the rewards w/ the marginals gained by the current node
        results.write(str(best_node) + '\t' + str(rewards_so_far) + '\t' + str(new_top_tuple[0]) + '\t' + str(runtime) + '\n')
        final_steps.append(rewards_so_far)
        final_runtimes.append(runtime)
        print "Simulation steps so far: " + str(rewards_so_far)
        print "Runtime (minutes) = " + str(runtime)
        
        
            
    results.close()
    return final_steps, final_runtimes<jupyter_output><empty_output><jupyter_text>Pure Social Score<jupyter_code>def social_steps_live_edges(p_initial_infect, p_infect, lists_infected_dicts, num_detectors):

    final_steps = []
    final_runtimes = []
    
    with open("socialScore_modified_unpruned.txt") as social_file:
        lines = social_file.readlines()
        social_score_nodes = []
        for line in lines:
            social_score_nodes.append( int(line.split()[0]) )
    runs_per_marginal_node = len(lists_infected_dicts)
            
    rewards_so_far = 0
    marginal = 0
    start_time = time.time()
    selected_detectors = []
    for next_detector in range(num_detectors):
        selected_detectors.append(social_score_nodes[next_detector]) # add the next detector
        
        runs = [] # records number of runs
        for run in range(runs_per_marginal_node): # go thru the runs
            infected_dict = lists_infected_dicts[run]
            if bool(set(selected_detectors) & set(infected_dict.keys())): # detector is in the set of infected ids
                alerted_detectors = set(selected_detectors) & set(infected_dict.keys() ) # grab the set of detectors that was alerted
                alert_times = [infected_dict[detector] for detector in alerted_detectors]
                runs.append(min(alert_times)) # get the first time of alert
            else: # outbreak not detected, so last simulation step
                runs.append(39265) 
                    
        steps = sum(runs) / float(runs_per_marginal_node)
        marginal = steps - rewards_so_far
        rewards_so_far = steps
        final_steps.append(rewards_so_far)
        print "After doing Social Score, we have found the " + str(next_detector+1) + "th detector = " + str(social_score_nodes[next_detector])
        print "Population affected so far: " + str(rewards_so_far)
        print "Marginal gain = " + str(marginal)
        runtime = (time.time() - start_time) / 60
        print "Runtime (minutes) = " + str(runtime)
        final_runtimes.append(runtime)
    
    return final_steps, final_runtimes<jupyter_output><empty_output><jupyter_text>Speed up<jupyter_code>def speedup_steps_live_edges(p_initial_infect, p_infect, lists_infected_dicts, num_detectors, social_score_file, seed=0, n=2029, debug=False):
    
    runs_per_marginal_node = len(lists_infected_dicts)
    final_steps = []
    final_runtimes = []
    
    print 'Running Speedup to minimize steps affected w/ live edges'
    results = open("Speedup_steps_live_edge.txt", "w")
    results.write("P_infect = " + str(p_infect) + " P_initial_infect = " + str(p_initial_infect) + " Runs per marginal node = " + str(runs_per_marginal_node))
    results.write("\nNode ID\tReward so Far\tMarginal gain\tRuntime (minutes)\n")
    
    rewards_so_far = 39265
    
    marginals = [] # heap to track marginals
    
    # how we keep track of the social score nodes
    social_score_nodes = []
    with open(social_score_file) as social_file:
        lines = social_file.readlines()
        for line in lines:
            social_score_nodes.append( int(line.split()[0]) )   
   
    
    look_ahead = int(math.sqrt(n)) # how much we look ahead
    start_time = time.time()
    
    # we are calculated population saved
    # if the detector is in the infected nodes, we take the index of the detector b/c the infected nodes are in chronological order + 1 - length to represent how many we saved
    # if not, we just take 0 b/c we didnt save any
    # select the first node by exhuastively computing all marginal benefits
    # our metric = (population affected w/ detector) - population affected w/o detector
    # we are trying to minimize this metric
    for potential_detector in social_score_nodes[:look_ahead]: # calculate marginals for each node
        runs = [infected_dict[potential_detector] if potential_detector in infected_dict.keys() else 39265 for infected_dict in lists_infected_dicts]
        heapq.heappush(marginals, (sum(runs)/float(runs_per_marginal_node) - rewards_so_far, potential_detector))

        
    
    best_tuple = heapq.heappop(marginals)
    best_node = best_tuple[1]
    marginal = best_tuple[0]
    rewards_so_far = marginal + rewards_so_far
    
    selected_detectors = [best_node] # we have found our first best node
    
    print "We have our first best node: "
    print selected_detectors
    runtime = (time.time() - start_time) / 60
    print "Runtime (minutes) = " + str( runtime )
    final_steps.append(rewards_so_far)
    final_runtimes.append(runtime)
    
    results.write(str(best_node) + '\t' + str(rewards_so_far) + '\t' + str(marginal) + '\t' + str(runtime) + '\n' )
    
    for i in range(1, num_detectors): # select the next num_detectors-1 detectors
        
        if debug:
            print "Trying to find the " + str(i+1) + "th detector"
        
        # add one new detector from social score
        new_detectors=list(selected_detectors)
        additional_detector = social_score_nodes[look_ahead - 1 + i]
        new_detectors.append(additional_detector)
        runs = [] # records the results for each run
        for run in range(runs_per_marginal_node): # go thru the runs
            infected_dict = lists_infected_dicts[run]
            if bool(set(new_detectors) & set(infected_dict.keys())): # detector is in the set of infected ids
                alerted_detectors = set(new_detectors) & set(infected_dict.keys() ) # grab the set of detectors that was alerted
                alert_times = [infected_dict[detector] for detector in alerted_detectors]
                runs.append(min(alert_times)) # get the first time of alert
            else: # outbreak not detected, so last simulation step
                runs.append(39265) 
        heapq.heappush(marginals, (sum(runs) / float(runs_per_marginal_node) - rewards_so_far, additional_detector))
        
        
        # need to re-evaluate the top node once, at least
        old_top_tuple = heapq.heappop(marginals)
        old_top_node = old_top_tuple[1]
        new_detectors = list(selected_detectors)
        new_detectors.append(old_top_node)

        # lazily evaluate for the top node
        runs = [] # records the results for each run
        for run in range(runs_per_marginal_node): # go thru the runs
            infected_dict = lists_infected_dicts[run]
            if bool(set(new_detectors) & set(infected_dict.keys())): # detector is in the set of infected ids
                alerted_detectors = set(new_detectors) & set(infected_dict.keys() ) # grab the set of detectors that was alerted
                alert_times = [infected_dict[detector] for detector in alerted_detectors]
                runs.append(min(alert_times)) # get the first time of alert
            else: # outbreak not detected, so last simulation step
                runs.append(39265) 
        heapq.heappush(marginals, (sum(runs) / float(runs_per_marginal_node) - rewards_so_far, old_top_node))

        new_top_tuple = heapq.heappop(marginals)
        new_top_node = new_top_tuple[1]
        
        while new_top_node != old_top_node: # this is where we need to re-evaluate the next top node
            old_top_node = new_top_node
            new_detectors = list(selected_detectors)
            new_detectors.append(old_top_node)
            
            runs = [] # records number of runs
            for run in range(runs_per_marginal_node): # go thru the runs
                infected_dict = lists_infected_dicts[run]
                if bool(set(new_detectors) & set(infected_dict.keys())): # detector is in the set of infected ids
                    alerted_detectors = set(new_detectors) & set(infected_dict.keys() ) # grab the set of detectors that was alerted
                    alert_times = [infected_dict[detector] for detector in alerted_detectors]
                    runs.append(min(alert_times)) # get the first time of alert
                else: # outbreak not detected, so last simulation step
                    runs.append(39265)           
            heapq.heappush(marginals, (sum(runs) / float(runs_per_marginal_node) - rewards_so_far, old_top_node))
           
            new_top_tuple = heapq.heappop(marginals)
            new_top_node = new_top_tuple[1]
        
        
        
        best_node = new_top_node
        
        print "After doing speed up, we have found the " + str (i+1) + "th detector w/ best marginal gain = " + str(best_node)
        selected_detectors.append(best_node)
        runtime = (time.time() - start_time)/60
        rewards_so_far = rewards_so_far + new_top_tuple[0] # update the rewards w/ the marginals gained by the current node
        results.write(str(best_node) + '\t' + str(rewards_so_far) + '\t' + str(new_top_tuple[0]) + '\t' + str(runtime) + '\n')
        final_steps.append(rewards_so_far)
        final_runtimes.append(runtime)
        print "Steps so far: " + str(rewards_so_far)
        print "Runtime (minutes) = " + str(runtime)
        
        
        
            
    results.close()
    
    return final_steps, final_runtimes<jupyter_output><empty_output><jupyter_text>Comparisons P_initial = 0.001, p_infect = 0.3<jupyter_code>celf_steps_point001_point3, celf_steps_runtimes_point001_point3 = celf_steps_live_edges(0.001, 0.3, live_edges_200k_point001_point3_steps[:100000], 50)
social_steps_point001_point3, social_steps_runtimes_point001_point3 = social_steps_live_edges(0.001, 0.3, live_edges_200k_point001_point3_steps[:100000], 50)
speedup_steps_point001_point3, speedup_steps_runtimes_point001_point3 = speedup_steps_live_edges(0.001, 0.3, live_edges_200k_point001_point3_steps[:100000], 50, "socialScore_modified_unpruned.txt")
plt.plot(range(1, 51), celf_steps_point001_point3, label="CELF")
plt.plot(range(1, 51), social_steps_point001_point3, label="Social Score only")
plt.plot(range(1, 51), speedup_steps_point001_point3, label="Speed up")
plt.title("100K runs, P_infect = 0.3, P_initial_infect = 0.001")
plt.ylabel("Steps")
plt.xlabel("# of Detectors")
plt.legend()
plt.plot(range(1, 51), celf_steps_runtimes_point001_point3, label="CELF")
plt.plot(range(1, 51), [runtime + 7 for runtime in social_steps_runtimes_point001_point3], label="Social Score only")
plt.plot(range(1, 51), [runtime + 7 for runtime in speedup_steps_runtimes_point001_point3], label="Speed up")
plt.title("100K runs, P_infect = 0.3, P_initial_infect = 0.001")
plt.ylabel("Runtime (minutes)")
plt.xlabel("# of Detectors")
plt.legend()<jupyter_output><empty_output><jupyter_text>P_initial = 0.001, p_infect = 0.5<jupyter_code>celf_steps_point001_point5, celf_steps_runtimes_point001_point5 = celf_steps_live_edges(0.001, 0.5, live_edges_200k_point001_point5_steps[:100000], 50)
social_steps_point001_point5, social_steps_runtimes_point001_point5 = social_steps_live_edges(0.001, 0.5, live_edges_200k_point001_point5_steps[:100000], 50)
speedup_steps_point001_point5, speedup_steps_runtimes_point001_point5 = speedup_steps_live_edges(0.001, 0.5, live_edges_200k_point001_point5_steps[:100000], 50 , "socialScore_modified_unpruned.txt")
plt.plot(range(1, 51), celf_steps_point001_point5, label="CELF")
plt.plot(range(1, 51), social_steps_point001_point5, label="Social Score only")
plt.plot(range(1, 51), speedup_steps_point001_point5, label="Speed up")
plt.title("Time to Detection: 100K runs, P_infect = 0.5, P_initial_infect = 0.001")
plt.ylabel("Number of e-mails sent before outbreak alerted")
plt.xlabel("# of Detectors")
plt.legend()
plt.plot(range(1, 51), celf_steps_runtimes_point001_point5, label="CELF")
plt.plot(range(1, 51), [runtime + 7 for runtime in social_steps_runtimes_point001_point5], label="Social Score only")
plt.plot(range(1, 51), [runtime + 7 for runtime in speedup_steps_runtimes_point001_point5], label="Speed up")
plt.title("Time to Detection: 100K runs, P_infect = 0.5, P_initial_infect = 0.001")
plt.ylabel("Runtime (minutes)")
plt.xlabel("# of Detectors")
plt.legend()<jupyter_output><empty_output><jupyter_text>P_initial = 0.005, p_infect = 0.3<jupyter_code>celf_steps_point005_point3, celf_steps_runtimes_point005_point3 = celf_steps_live_edges(0.005, 0.3, live_edges_200k_point005_point3_steps[:5000], 50)
social_steps_point005_point3, social_steps_runtimes_point005_point3 = social_steps_live_edges(0.005, 0.3, live_edges_200k_point005_point3_steps[:100000], 50)
speedup_steps_point005_point3, speedup_steps_runtimes_point005_point3 = speedup_steps_live_edges(0.005, 0.3, live_edges_200k_point005_point3_steps[:100000], 50, "socialScore_modified_unpruned.txt")
celf_10k_runtimes = celf_steps_runtimes_point005_point3
celf_5k_runtimes = celf_steps_runtimes_point005_point3
plt.plot(range(1, 51), celf_10k_runtimes, label="CELF 10K runs")
plt.plot(range(1, 51), celf_5k_runtimes, label="CELF 5K runs")
plt.plot(range(1, 51), [runtime + 7 for runtime in social_steps_runtimes_point005_point3], label="Social Score only, 100K Runs")
plt.plot(range(1, 51), [runtime + 7 for runtime in speedup_steps_runtimes_point005_point3], label="Speed up, 100K Runs")
plt.title("Runtime Comparison for Time to Detection Metric:\nP_infect = 0.3, P_initial_infect = 0.005")
plt.ylabel("Runtime (minutes)")
plt.xlabel("# of Detectors")
plt.legend()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09245109196336639, 'fraction_numerical': 0.0300222186094402, 'mean_word_length': 3.3523584905660377, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '384302', 'license': 'MIT', 'n_tokens_mistral': 6504, 'n_tokens_neox': 5962, 'n_words': 1370, 'path': 'sim_outbreak/Final Project - Steps.ipynb', 'repo_name': 'ppsekhar/CS224W', 'size': '18453'}