search

scramblingbalam / IIT_in_orgs

Applying Information Integration Theory
0 stars 0 forks source link

Find a way to get all simple paths using iGraph #6

Closed scramblingbalam closed 7 years ago

scramblingbalam commented 7 years ago

Since it has become clear that the most computationally intensive thing I will want to do using the network library is finding all paths between two nodes, I should front load this task as it may determine which library I can use.

scramblingbalam commented 7 years ago

Found a written by one of the authors of iGraph at: https://stackoverflow.com/questions/29314795/python-igraph-get-all-possible-paths-in-a-directed-graph/29324009#29324009 It is probably better than anything I could write so I will accept it as the best python-iGraph can do.

scramblingbalam commented 7 years ago

Based on networks created in NetworkX usiing code from issue #3 Times for networkX and igraph find_all_simple_paths functions are:

Num Nodes 20 Num Edges 95 Reciprocity Ratio 0.5052631578947369 Average Clustering 0.632196392358931 ALL path time NetworkX 12.869640588760376 ALL path time iGraph 7.349468946456909

Num Nodes 20 Num Edges 95 Reciprocity Ratio 0.5052631578947369 Average Clustering 0.6503672144848616 ALL path time NetworkX 1.7008583545684814 ALL path time iGraph 1.0613124370574951

Num Nodes 20 Num Edges 96 Reciprocity Ratio 0.4583333333333333 Average Clustering 0.6420560648501825 ALL path time NetworkX 1.2905442714691162 ALL path time iGraph 0.7000069618225098

Num Nodes 20 Num Edges 95 Reciprocity Ratio 0.4 Average Clustering 0.6644009688282134 ALL path time NetworkX 7.763059616088867 ALL path time iGraph 4.6494996547698975

scramblingbalam commented 7 years ago

iGraph find_all_paths runing with nodes = 100 and edges = 872 throws a memory error ...