In [16]:
import netcomp as nc
We're going to test the timing (absolute, and complexity) for the algorithms we've got implemented so far.
We'll do this in the following manner. We'll set up a script for running multiple timing runs in parallel, then we'll take the average time (or maybe average of $n$ lowest?) in order to start examining the complexity.
In [22]:
# Import things we'll use to analyze the timing
from sklearn.linear_model import LinearRegression
%load_ext line_profiler
def complexity_plot(log_range,times,label=None):
"Make a logarithmic complexity plot, report best-fit line slope."
logtime = np.log(times).reshape(-1,1)
logn = np.log(log_range).reshape(-1,1)
regr = LinearRegression()
regr.fit(logn,logtime)
slope = float(regr.coef_)
fit_line = np.exp(regr.predict(logn))
plt.figure();
plt.loglog(log_range,times,'o');
plt.loglog(log_range,fit_line,'--');
plt.xlabel('Size of Problem');
plt.ylabel('Time Elapsed');
if label is not None:
plt.title('Complexity of ' + label)
print('Best fit line for {} has slope {:0.03f}.'.format(label,slope))
else:
print('Best fit line has slope {:.03f}.'.format(slope))
The line_profiler extension is already loaded. To reload it, use:
%reload_ext line_profiler
In [2]:
data_dict = pickle.load(open('graph_distance_timing.p','rb'))
In [4]:
print(data_dict['description'])
Time each of our metrics to discover
computational complexity.
In [5]:
df = data_dict['results_df']
In [6]:
df
Out[6]:
Edit
Resistance Dist.
DeltaCon
NetSimile
Lambda (Adjacency)
Lambda (Laplacian)
Lambda (Normalized Laplacian)
Edit
Resistance Dist.
DeltaCon
...
Lambda (Adjacency)
Lambda (Laplacian)
Lambda (Normalized Laplacian)
Edit
Resistance Dist.
DeltaCon
NetSimile
Lambda (Adjacency)
Lambda (Laplacian)
Lambda (Normalized Laplacian)
10
0.00028348
0.222237
0.00820446
0.155957
0.000599384
0.0318468
0.00213671
0.000197411
0.0945263
0.0390024
...
0.000494242
0.00204062
0.00241899
5.55515e-05
0.00218225
0.00351286
0.0290842
0.000563383
0.00170541
0.0019412
30
4.57764e-05
0.302673
0.00330758
0.972329
0.000780106
0.0020709
0.00264382
5.57899e-05
0.301902
0.00316405
...
0.000786543
0.0181258
0.00707316
5.4121e-05
0.0881832
0.00327969
1.43964
0.0011487
0.0091393
0.00272584
100
8.96454e-05
0.183244
0.165371
8.45824
0.186596
0.0797551
0.0687363
8.10623e-05
0.472628
0.204094
...
0.120481
0.24446
0.503008
0.000215054
0.0893686
0.130405
9.89184
0.197206
0.150302
0.154846
300
0.000606298
1.16293
0.159863
25.7166
2.63298
3.79907
3.31286
0.000564814
0.608195
0.133687
...
5.36296
6.76249
6.377
0.000378847
0.409895
0.090127
26.4921
0.725003
0.584409
0.812854
1000
0.0154662
9.41187
1.00786
155.145
32.3615
42.97
43.1355
0.00598025
5.61302
1.06776
...
12.0492
17.0299
15.4275
0.00331473
1.94809
0.34633
156.875
5.04571
4.75076
4.89122
3000
0.369191
299.135
3.47908
273.29
564.239
477.134
560.69
0.370803
187.179
19.5115
...
472.193
186.07
123.262
0.0430229
29.1903
2.08132
1974.56
282.375
145.252
59.3902
6 rows × 700 columns
In [7]:
labels = df.columns.unique()
In [8]:
df_dict = {}
In [10]:
df['Edit'].T
Out[10]:
10
30
100
300
1000
3000
Edit
0.00028348
4.57764e-05
8.96454e-05
0.000606298
0.0154662
0.369191
Edit
0.000197411
5.57899e-05
8.10623e-05
0.000564814
0.00598025
0.370803
Edit
0.000216246
4.43459e-05
7.98702e-05
0.0258429
0.0320714
0.239238
Edit
0.000275612
4.52995e-05
6.91414e-05
0.000577211
0.00949001
0.244957
Edit
0.000202894
4.62532e-05
7.51019e-05
0.000561237
0.0184975
0.370901
Edit
0.00029397
4.52995e-05
7.9155e-05
0.00056529
0.00492525
0.302423
Edit
0.000118732
4.52995e-05
7.82013e-05
0.000560999
0.0178421
0.408601
Edit
0.000142336
4.72069e-05
9.91821e-05
0.000623703
0.00508285
0.322326
Edit
0.000145674
4.48227e-05
0.000103474
0.00056982
0.0406191
0.510803
Edit
0.00028491
4.62532e-05
8.7738e-05
0.000611305
0.00784707
0.253818
Edit
0.000200033
3.52859e-05
8.65459e-05
0.000569105
0.00455499
0.379067
Edit
0.000190973
4.50611e-05
7.4625e-05
0.000567913
0.0204105
0.313604
Edit
0.000103235
4.81606e-05
0.000126362
0.000588417
0.0201089
0.502235
Edit
0.000200033
4.55379e-05
0.000131845
0.000624895
0.0173266
0.336385
Edit
0.000199795
5.84126e-05
9.03606e-05
0.000575304
0.0579138
0.302057
Edit
0.000113487
2.98023e-05
0.000117302
0.000631094
0.00911355
0.340617
Edit
0.000103235
5.03063e-05
7.86781e-05
0.00058794
0.0154772
0.3358
Edit
0.000117779
5.84126e-05
0.000117064
0.000590086
0.0203865
0.31888
Edit
0.000203609
3.55244e-05
0.000110626
0.000581026
0.0177763
0.360284
Edit
0.000222921
4.76837e-05
6.8903e-05
0.000571251
0.00486159
0.409907
Edit
0.000100851
6.41346e-05
0.000112534
0.000606298
0.0599113
0.117487
Edit
6.05583e-05
8.10623e-05
0.0001266
0.000300646
0.0341403
0.148152
Edit
5.62668e-05
6.48499e-05
0.000183344
0.000627756
0.0193818
0.230133
Edit
6.05583e-05
0.000118256
9.46522e-05
0.000367165
0.0267262
0.218837
Edit
8.03471e-05
0.000126362
0.000107527
0.0161557
0.0543747
0.379593
Edit
9.58443e-05
0.000174761
0.0376918
0.000381947
0.039829
0.372713
Edit
7.36713e-05
8.03471e-05
0.00021863
0.000302315
0.0811725
0.256876
Edit
6.81877e-05
6.69956e-05
8.46386e-05
0.00110316
0.0713711
0.452341
Edit
5.26905e-05
6.74725e-05
9.799e-05
0.000343323
0.00329924
0.234745
Edit
5.91278e-05
9.39369e-05
9.82285e-05
0.0168324
0.058032
0.264047
...
...
...
...
...
...
...
Edit
5.79357e-05
6.67572e-05
0.000139952
0.000785828
0.0182071
0.263054
Edit
0.000189781
0.00015831
9.91821e-05
0.000528336
0.0174797
0.0825362
Edit
6.36578e-05
9.89437e-05
0.000165462
0.000321865
0.010603
0.221422
Edit
6.22272e-05
6.41346e-05
9.36985e-05
0.000463247
0.0279763
0.259271
Edit
5.53131e-05
6.67572e-05
8.96454e-05
0.00028348
0.00350404
0.0781689
Edit
6.03199e-05
6.7234e-05
9.84669e-05
0.000288248
0.0303786
0.108067
Edit
5.96046e-05
7.15256e-05
0.000112295
0.000309944
0.0295844
0.0876651
Edit
5.57899e-05
6.10352e-05
0.000103235
0.0447133
0.046418
0.0760965
Edit
5.88894e-05
9.34601e-05
9.58443e-05
0.000294209
0.0291274
0.0407164
Edit
5.36442e-05
6.34193e-05
9.94205e-05
0.000397682
0.0187783
0.0356209
Edit
6.07967e-05
7.22408e-05
0.000258207
0.000315666
0.0341394
0.186528
Edit
5.53131e-05
0.000107765
9.77516e-05
0.00032115
0.0276186
0.147884
Edit
7.7486e-05
8.46386e-05
0.000612974
0.000521898
0.0254531
0.221212
Edit
7.08103e-05
7.41482e-05
0.00010848
0.000302792
0.0469444
0.182513
Edit
6.8903e-05
6.74725e-05
0.000104904
0.000324726
0.00325584
0.237404
Edit
6.86646e-05
8.03471e-05
0.000146627
0.000370979
0.08916
0.227283
Edit
6.93798e-05
8.29697e-05
0.000107527
0.000365734
0.0677176
0.314513
Edit
0.000149727
9.41753e-05
0.000114441
0.000779629
0.046108
0.368344
Edit
5.38826e-05
6.65188e-05
9.65595e-05
0.00188541
0.0161653
0.342402
Edit
6.48499e-05
6.31809e-05
9.32217e-05
0.0003829
0.0215144
0.120729
Edit
0.000106335
7.1764e-05
0.000112772
0.000779629
0.0222611
0.186024
Edit
5.76973e-05
9.39369e-05
9.77516e-05
0.000374317
0.0146379
0.190964
Edit
0.000102043
0.021872
0.000219584
0.000350952
0.0381646
0.1529
Edit
8.17776e-05
7.7486e-05
0.0131552
0.0205743
0.0205081
0.281375
Edit
6.53267e-05
7.48634e-05
9.27448e-05
0.000552177
0.0180812
0.27703
Edit
5.98431e-05
8.53539e-05
9.41753e-05
0.000318289
0.0241232
0.208313
Edit
5.60284e-05
0.000104666
9.39369e-05
0.000702381
0.0276973
0.0578537
Edit
5.74589e-05
7.22408e-05
0.000216246
0.000584364
0.025069
0.0741835
Edit
6.7234e-05
7.51019e-05
0.000115871
0.000340462
0.0193155
0.0608673
Edit
5.55515e-05
5.4121e-05
0.000215054
0.000378847
0.00331473
0.0430229
100 rows × 6 columns
In [11]:
n = 100
for label in labels:
df_temp = df[label].T
df_temp.index = range(100)
df_dict[label] = df_temp
In [14]:
df_total = pd.concat(df_dict,axis=1)
In [15]:
df_total
Out[15]:
DeltaCon
Edit
...
NetSimile
Resistance Dist.
10
30
100
300
1000
3000
10
30
100
300
...
100
300
1000
3000
10
30
100
300
1000
3000
0
0.00820446
0.00330758
0.165371
0.159863
1.00786
3.47908
0.00028348
4.57764e-05
8.96454e-05
0.000606298
...
8.45824
25.7166
155.145
273.29
0.222237
0.302673
0.183244
1.16293
9.41187
299.135
1
0.0390024
0.00316405
0.204094
0.133687
1.06776
19.5115
0.000197411
5.57899e-05
8.10623e-05
0.000564814
...
7.54827
20.9183
116.988
437.527
0.0945263
0.301902
0.472628
0.608195
5.61302
187.179
2
0.0255492
0.00326967
0.134615
0.2121
1.35013
20.7121
0.000216246
4.43459e-05
7.98702e-05
0.0258429
...
3.04235
18.7939
69.3679
424.551
0.0662394
0.329336
0.366627
0.60622
5.28801
286.318
3
0.00254083
0.0031991
0.0675135
0.289525
1.2284
18.9496
0.000275612
4.52995e-05
6.91414e-05
0.000577211
...
3.46615
15.0995
76.0705
1164.6
0.0367355
0.289481
0.161982
0.386847
7.01957
286.356
4
0.00373173
0.00378919
0.123849
0.139059
0.71292
6.24403
0.000202894
4.62532e-05
7.51019e-05
0.000561237
...
7.13728
29.5192
131.814
284.094
0.108705
0.351261
0.372429
0.796469
7.88605
310.052
5
0.010268
0.00323176
0.145001
0.394451
0.889508
10.9971
0.00029397
4.52995e-05
7.9155e-05
0.00056529
...
3.69945
15.4404
71.9671
962.901
0.0287809
0.286721
0.0342119
0.643994
9.9891
401.197
6
0.00732493
0.0032835
0.142652
0.122106
1.71077
7.25871
0.000118732
4.52995e-05
7.82013e-05
0.000560999
...
9.35148
13.8124
171.157
383.63
0.0609736
0.316966
0.204251
0.376051
4.84392
219.087
7
0.0634875
0.00327587
0.134998
0.148662
0.628493
6.32107
0.000142336
4.72069e-05
9.91821e-05
0.000623703
...
5.67684
42.9957
156.593
826.862
0.0581741
0.284809
0.333027
0.493491
5.38635
272.664
8
0.00247455
0.00315833
0.238209
0.128114
1.12096
13.2293
0.000145674
4.48227e-05
0.000103474
0.00056982
...
5.68893
19.5079
90.1442
707.171
0.0392709
0.346845
0.408748
0.451287
6.31324
338.808
9
0.0185492
0.00331211
0.220097
0.123091
1.45278
19.683
0.00028491
4.62532e-05
8.7738e-05
0.000611305
...
7.40615
19.6082
74.8941
376.752
0.064425
0.360898
0.166249
0.574641
9.71514
308.576
10
0.00246906
0.00330091
0.105686
0.354446
1.63971
15.1695
0.000200033
3.52859e-05
8.65459e-05
0.000569105
...
3.81637
13.9831
104.885
728.491
0.0466452
0.257225
0.223319
1.30637
7.14932
306.006
11
0.0235674
0.00328159
0.0674219
0.138284
1.06574
11.6472
0.000190973
4.50611e-05
7.4625e-05
0.000567913
...
4.37711
18.2324
102.386
296.851
0.0717518
0.343324
0.149315
0.475544
7.3124
346.756
12
0.0299931
0.00333881
0.320308
0.140428
0.753508
6.85036
0.000103235
4.81606e-05
0.000126362
0.000588417
...
3.32854
36.7943
163.731
1323.01
0.0829215
0.34898
0.219229
0.673227
5.08562
226.097
13
0.0198274
0.00331926
0.132601
0.450442
0.869783
16.4244
0.000200033
4.55379e-05
0.000131845
0.000624895
...
8.0428
36.0131
75.1092
393.946
0.0961423
0.294921
0.134118
0.448892
5.25793
305.277
14
0.0398979
0.00331473
0.282356
0.167487
1.78895
11.1853
0.000199795
5.84126e-05
9.03606e-05
0.000575304
...
3.26578
12.8642
82.2807
318.312
0.0905228
0.319452
0.465786
0.714469
6.24104
406.607
15
0.00579095
0.00381613
0.133854
0.243878
0.53689
9.99625
0.000113487
2.98023e-05
0.000117302
0.000631094
...
2.9404
42.9733
106.815
299.544
0.0158229
0.260389
0.349355
0.965806
7.55051
289.761
16
0.00652194
0.00316167
0.117872
0.178213
1.41665
12.0191
0.000103235
5.03063e-05
7.86781e-05
0.00058794
...
3.70223
33.8596
114.352
377.378
0.0421722
0.26601
0.194582
0.730792
8.13302
253.171
17
0.0037322
0.00333786
0.105466
0.197984
1.59124
5.5716
0.000117779
5.84126e-05
0.000117064
0.000590086
...
3.16932
27.4833
132.772
342.497
0.0762393
0.308653
0.146093
1.46753
5.81154
272.882
18
0.00249028
0.00324774
0.158101
0.287137
1.50268
2.5454
0.000203609
3.55244e-05
0.000110626
0.000581026
...
8.05726
16.3483
183.262
312.721
0.0249312
0.292686
0.303927
0.731482
8.13812
257.194
19
0.0350316
0.00318265
0.0870342
0.229768
0.977381
10.9638
0.000222921
4.76837e-05
6.8903e-05
0.000571251
...
4.04973
19.8607
140.327
753.634
0.0936012
0.30969
0.13713
0.598171
7.03823
261.466
20
0.00315642
0.0509071
0.252518
0.565023
1.85396
11.4247
0.000100851
6.41346e-05
0.000112534
0.000606298
...
40.9044
176.153
488.329
763.664
0.00217104
0.105391
0.585435
1.49593
15.6418
175.558
21
0.0703032
0.00404811
0.578033
0.353467
1.28807
10.9359
6.05583e-05
8.10623e-05
0.0001266
0.000300646
...
37.767
153.539
417.211
773.88
0.00197649
0.186705
0.258148
1.91176
17.2154
168.516
22
0.0383575
0.041707
0.431826
0.37448
1.12623
8.54068
5.62668e-05
6.48499e-05
0.000183344
0.000627756
...
33.3566
157.035
385.872
683.128
0.0373538
0.0551326
0.266732
1.73766
20.8298
252.76
23
0.0401249
0.00505853
0.271244
0.377284
1.34504
10.9792
6.05583e-05
0.000118256
9.46522e-05
0.000367165
...
32.383
125.333
379.993
619.949
0.0577505
0.0818896
0.181272
1.90132
19.3298
225.051
24
0.0363102
0.00368142
0.123279
0.290556
1.66722
11.3701
8.03471e-05
0.000126362
0.000107527
0.0161557
...
31.3307
120.558
367.725
618.596
0.00286388
0.0667305
0.18289
1.63502
24.8362
191.847
25
0.00356483
0.00354505
0.272037
0.299258
1.08178
11.4604
9.58443e-05
0.000174761
0.0376918
0.000381947
...
32.3313
118.203
369.642
608.396
0.047744
0.0994029
0.531896
1.50364
15.9397
170.523
26
0.0383987
0.112523
0.164367
0.362127
1.11254
6.63539
7.36713e-05
8.03471e-05
0.00021863
0.000302315
...
29.5611
113.711
354.963
645.559
0.00248456
0.153606
0.200012
1.93583
17.4286
222.579
27
0.0267434
0.0327902
0.10284
0.238473
0.864369
7.71238
6.81877e-05
6.69956e-05
8.46386e-05
0.00110316
...
27.774
115.812
313.698
663.518
0.0411949
0.078248
0.158036
0.908624
21.2324
186.154
28
0.00316405
0.0187602
0.169974
0.137836
1.00438
11.2765
5.26905e-05
6.74725e-05
9.799e-05
0.000343323
...
25.0697
103.779
327.332
722.827
0.0395265
0.0964274
0.351207
0.849531
14.3489
167.171
29
0.0454853
0.0173705
0.118016
0.218685
1.57731
5.00993
5.91278e-05
9.39369e-05
9.82285e-05
0.0168324
...
23.0361
104.01
363.297
685.268
0.00203586
0.0399907
0.14689
1.34373
23.6519
181.885
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
70
0.0221875
0.00478601
0.203532
0.195059
0.755858
7.37219
5.79357e-05
6.67572e-05
0.000139952
0.000785828
...
20.1595
95.0164
441.813
575.968
0.00234365
0.0498929
0.149518
1.5206
9.44375
166.049
71
0.0266867
0.0034945
0.122632
0.200907
0.729664
6.03421
0.000189781
0.00015831
9.91821e-05
0.000528336
...
25.1566
84.6385
436.033
734.326
0.00241542
0.0651419
0.127522
1.64205
11.9583
153.42
72
0.0216017
0.0241156
0.0987835
0.135259
1.18199
6.2178
6.36578e-05
9.89437e-05
0.000165462
0.000321865
...
19.4583
79.4992
445.041
617.057
0.0363936
0.0648901
0.0928342
1.43396
12.1885
135.448
73
0.0126171
0.00331187
0.102618
0.461809
0.64116
3.95158
6.22272e-05
6.41346e-05
9.36985e-05
0.000463247
...
16.5918
74.4532
437.51
1011.45
0.0020082
0.0479052
0.141966
0.872335
7.55138
142.963
74
0.00331283
0.00361419
0.136445
0.0892792
1.07894
4.61254
5.53131e-05
6.67572e-05
8.96454e-05
0.00028348
...
16.6964
75.106
419.636
723.292
0.015305
0.0511754
0.122267
1.42161
10.6903
144.138
75
0.0207899
0.00347638
0.377512
0.11098
0.87001
5.01065
6.03199e-05
6.7234e-05
9.84669e-05
0.000288248
...
19.1428
82.8759
415.194
820.765
0.0175529
0.0731101
0.132956
1.27241
12.1347
68.5179
76
0.0200582
0.00362062
0.0971103
0.203827
1.42324
3.61205
5.96046e-05
7.15256e-05
0.000112295
0.000309944
...
20.0881
86.6134
388.782
1320.35
0.0177104
0.0815868
0.141449
1.44218
19.2873
98.2618
77
0.0229545
0.00340271
0.120472
0.542338
1.68286
3.79592
5.57899e-05
6.10352e-05
0.000103235
0.0447133
...
25.9848
86.4087
386.427
1551.21
0.00232625
0.0898879
0.162069
1.24732
20.606
79.3052
78
0.00324655
0.0245507
0.223871
0.184385
0.995938
3.82391
5.88894e-05
9.34601e-05
9.58443e-05
0.000294209
...
19.4843
82.8619
308.528
1552.65
0.00199056
0.0793159
0.137465
1.26285
14.7202
75.4733
79
0.0399075
0.0200801
0.103044
0.212389
1.15255
2.37331
5.36442e-05
6.34193e-05
9.94205e-05
0.000397682
...
21.3017
89.5381
259.461
1821.54
0.00201917
0.0216198
0.109902
1.69047
27.8197
75.3377
80
0.035527
0.00375414
0.532439
0.404772
1.51675
8.31719
6.07967e-05
7.22408e-05
0.000258207
0.000315666
...
39.2255
160.007
635.21
940.132
0.0020864
0.0531466
0.228098
2.30744
32.4833
134.867
81
0.0354512
0.0463622
0.212068
0.271919
1.53248
10.7588
5.53131e-05
0.000107765
9.77516e-05
0.00032115
...
28.7231
154.394
607.673
865.007
0.0272379
0.103535
0.192799
1.63943
12.7567
258.762
82
0.0584714
0.0430498
0.171326
0.289474
0.847046
9.27352
7.7486e-05
8.46386e-05
0.000612974
0.000521898
...
38.3272
144.591
564.026
826.382
0.0439725
0.0781062
0.134982
2.04452
18.0174
267.903
83
0.0792615
0.00361729
0.206428
0.275465
1.38957
10.6554
7.08103e-05
7.41482e-05
0.00010848
0.000302792
...
35.1668
136.899
527.727
901.435
0.00212622
0.294862
0.206567
1.52487
13.4985
131.153
84
0.00346994
0.00500035
0.179486
0.737461
1.34554
8.63438
6.8903e-05
6.74725e-05
0.000104904
0.000324726
...
31.7289
134.146
504.352
799.212
0.0021987
0.0955625
0.176665
2.14557
18.8681
191.115
85
0.0411093
0.00357485
0.206932
0.223555
1.36813
8.43188
6.86646e-05
8.03471e-05
0.000146627
0.000370979
...
30.1444
125.013
522.019
818.913
0.00361514
0.0801191
0.188461
1.97422
18.1579
234.733
86
0.0232716
0.0298278
0.140514
0.464055
1.62925
8.13316
6.93798e-05
8.29697e-05
0.000107527
0.000365734
...
26.4046
121.995
510.979
736.415
0.0291243
0.0895164
0.182347
1.12704
19.7729
218.865
87
0.00319791
0.0296748
0.128548
0.654692
1.30826
6.3271
0.000149727
9.41753e-05
0.000114441
0.000779629
...
29.0845
121.213
487.977
761.874
0.00220513
0.0892253
0.165562
1.5611
21.3043
168.555
88
0.0320525
0.0337968
0.170508
0.236835
1.12896
6.49818
5.38826e-05
6.65188e-05
9.65595e-05
0.00188541
...
33.0258
122.565
513.899
853.68
0.0527539
0.0590501
0.167497
2.0806
22.177
167.309
89
0.0188746
0.00455403
0.17303
0.250048
0.83953
6.67258
6.48499e-05
6.31809e-05
9.32217e-05
0.0003829
...
22.0971
86.8921
505.164
866.656
0.0261919
0.0771041
0.156201
1.34541
11.719
161.827
90
0.0298221
0.0544572
0.267794
0.236287
1.06179
6.83444
0.000106335
7.1764e-05
0.000112772
0.000779629
...
18.4411
84.4593
508.354
784.863
0.0274999
0.0698869
0.409035
1.80838
11.9296
117.131
91
0.0192378
0.021419
0.131151
0.22551
0.733673
9.10781
5.76973e-05
9.39369e-05
9.77516e-05
0.000374317
...
19.6784
84.7171
485.348
710.333
0.023351
0.0490839
0.121492
1.42748
12.9422
146.072
92
0.00487614
0.0207679
0.211021
0.222272
1.8271
4.85606
0.000102043
0.021872
0.000219584
0.000350952
...
20.4142
91.615
503.385
965.821
0.0189078
0.0106602
0.378006
1.6321
25.0955
154.101
93
0.00327659
0.00739121
0.295464
0.416258
1.11788
3.95077
8.17776e-05
7.7486e-05
0.0131552
0.0205743
...
20.0036
87.3383
521.452
879.857
0.0200162
0.0557923
0.136731
2.37452
20.3286
152.069
94
0.0204937
0.0255022
0.319885
0.155387
1.03905
4.48649
6.53267e-05
7.48634e-05
9.27448e-05
0.000552177
...
19.0064
83.9567
475.22
830.873
0.00249386
0.0521882
0.172211
1.29354
16.7002
146.748
95
0.0187821
0.00358224
0.153645
0.164125
0.867605
3.67033
5.98431e-05
8.53539e-05
9.41753e-05
0.000318289
...
20.1804
88.4705
479.735
1031.1
0.018559
0.0536823
0.130244
1.32246
16.1566
113.799
96
0.0196774
0.00339079
0.390221
0.272635
0.812143
4.70923
5.60284e-05
0.000104666
9.39369e-05
0.000702381
...
18.5417
79.1443
276.093
1520.78
0.00216317
0.0201104
0.383921
1.6588
13.3962
99.488
97
0.00361419
0.0187836
0.203906
0.150442
0.959997
3.22343
5.74589e-05
7.22408e-05
0.000216246
0.000584364
...
16.694
71.8677
221.063
1512.7
0.0235848
0.109781
0.104036
1.31046
20.5147
88.9696
98
0.0141919
0.0243754
0.165395
0.220182
1.1008
3.67256
6.7234e-05
7.51019e-05
0.000115871
0.000340462
...
15.9247
67.543
233.497
1717.78
0.0161595
0.0676987
0.169985
1.40358
15.3727
73.6181
99
0.00351286
0.00327969
0.130405
0.090127
0.34633
2.08132
5.55515e-05
5.4121e-05
0.000215054
0.000378847
...
9.89184
26.4921
156.875
1974.56
0.00218225
0.0881832
0.0893686
0.409895
1.94809
29.1903
100 rows × 42 columns
In [27]:
ran = [10,30,100,300,1000,3000]
for label in labels:
complexity_plot(ran[2:],np.array(df_total[label].median())[2:],label=label)
plt.title('Complexity of ' + label)
Best fit line for Edit has slope 2.340.
Best fit line for Resistance Dist. has slope 2.024.
Best fit line for DeltaCon has slope 1.159.
Best fit line for NetSimile has slope 1.065.
Best fit line for Lambda (Adjacency) has slope 2.183.
Best fit line for Lambda (Laplacian) has slope 2.227.
Best fit line for Lambda (Normalized Laplacian) has slope 2.177.
Hrmm... I don't really trust these results, because a lot of them don't look that linear. We'd better take a look at the statistics, and the code, to make sure taht we're not accidentally taking any unexpected algorithmic shortcuts here.
In [ ]:
Content source: peterewills/NetComp
Similar notebooks: