<jupyter_start><jupyter_text>Measure runtime of stats algorithmsNovember 14, 2018**Overview:**We are planning on adding algorithms to NDMG. @GaneshArvapalli compiled all of the algorithms into a single [python script](https://github.com/NeuroDataDesign/the-ents/blob/master/src/features/stats_explained.md). In this notebook, we measure the runtime of each of the algorithms and see how runtime relates to the size of the graph (n) and the connectivity of the graph (p).<jupyter_code>import numpy as np
import networkx as nx
import os

from src.data.edgelist_io import read_edgelist
from timing import measure_runtime

import matplotlib.pyplot as plt
%matplotlib inline
def estimate_phat(G):

    # Get matrix
    A = nx.to_numpy_matrix(G)
    n = A.shape[0]

    # Count upper triangular elements
    edges = np.count_nonzero(np.triu(A))
    num_upper = n * (n + 1) / 2

    # Estimate phat
    phat = edges / num_upper
    return n, phat
filepath='../../data/raw/hbn/'
atlases = os.listdir(filepath)

for i in ['DS72784', '.DS_Store']:
    atlases.remove(i)
results = {}

for atlas in atlases:
    
    print(atlas)
    p_i = []
    
    filelist = os.listdir(filepath + atlas)
    filelist = np.random.choice(filelist, 10)
    
    for file in filelist:
        path = filepath + atlas + '/' + file
        G = read_edgelist(path)
        
        try:
            n, phat_i = estimate_phat(G)
            p_i += [phat_i]
        except:
            pass

        # Attach to dictionary
        p_hat = np.mean(p_i)
        results[atlas] = [n, p_hat]
pprint.pprint(results)
timing_res = {}

for key, value in results.items():
    
    print(key)
    n, phat = value
    
    if n <= 1000:
        atlas = key
        times = measure_runtime(n, phat)
        timing_res[atlas] = times
from src.features.summary import Stats
from src.random.bernoulli import RandomGraph
A = RandomGraph(**{'n': 5, 'p': 0.1})
s = Stats(A)

public_method_names = [method for method in dir(s) if callable(
    getattr(s, method)) if not method.startswith('_')]
for method in ['return_stats', 'khop_locality', 'scan_statistic']:
    public_method_names.remove(method)
for i, method in enumerate(public_method_names):
    x, y = [], []
    for key, value in timing_res.items():
        x += [value[0]]
        y += [value[i+2]]
        
    plt.scatter(x, y)
    
    plt.xlabel('num_nodes')
    plt.ylabel('runtime (s)')
    plt.title(method)
    plt.show()
d = {method:time for method,time in zip(public_method_names, timing_res['Talairach'][2:])}
a = sorted(d.items(), key=lambda x: x[1])

print('timing results:')
pprint.pprint([(i[0], round(i[1], 4)) for i in a])
x, y = [], []
for key, value in timing_res.items():
    x += [value[0]]
    y += [sum(value[2:])]

plt.scatter(x, y)

plt.xlabel('num_nodes')
plt.ylabel('runtime (s)')
plt.title('total runtime')

plt.text(850, 176+220, 'slab907')
plt.arrow(899, 176+200, 0, -130, head_width=40)

plt.show()
x, y = [], []
for key, value in timing_res.items():
    x += [value[0] * value[1]]
    y += [sum(value[2:])]

plt.scatter(x, y)

plt.xlabel(r'num_nodes * connectivity ($n*p$)')
plt.ylabel('runtime (s)')
plt.title('total runtime')

plt.text(x[-4]-4, 350, 'slab907')
plt.arrow(x[-4], 340, 0, -130, head_width=1, head_length=30)

plt.show()
n = 25
y = []

for phat in np.linspace(0,1,11):
    print(phat)
    y += [sum(measure_runtime(n=n, p=phat)[2:])]

plt.scatter(np.linspace(0,1,11), y)
plt.title(r'runtime is proportional to $p$')
plt.ylabel('runtime (s)')
plt.xlabel(r'connectivity ($p$)')
plt.text(0, 3, r'n={}'.format(n))
p = 0.25
y = []

for n in np.linspace(1,75,11):
    print(phat)
    y += [sum(measure_runtime(n=n, p=p)[2:])]

plt.scatter(np.linspace(0,1,11), y)
plt.title(r'runtime is proportional to $n$')
plt.ylabel('runtime (s)')
plt.xlabel(r'num_nodes ($n$)')
plt.text(0, 2, r'p={}'.format(p))<jupyter_output>1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
{'fraction_non_alphanumeric': 0.16278474532889686, 'fraction_numerical': 0.033529562324033785, 'mean_word_length': 3.391011235955056, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 1, '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': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '67687', 'license': 'FTL', 'n_tokens_mistral': 1625, 'n_tokens_neox': 1523, 'n_words': 372, 'path': 'notebooks/1.0-vg-runtime-simulation/runtime.ipynb', 'repo_name': 'v715/py-U-Rerf', 'size': '3907'}