Sun Aug 7 20:50:03 2022 pagerank_test(): Python version: 3.6.9 pagerank() demonstrates several page rank algorithms. Test 0 5 node MacCormick example with a cycle Incidence matrix A: [[0. 1. 0. 0. 0.] [0. 0. 0. 0. 1.] [1. 0. 0. 0. 0.] [1. 0. 0. 0. 0.] [1. 0. 0. 0. 0.]] Transition matrix T: [[0. 0. 1. 1. 1.] [1. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 1. 0. 0. 0.]] // mac1 digraph { 0 [label=0] 1 [label=1] 2 [label=2] 3 [label=3] 4 [label=4] 0 -> 1 1 -> 4 2 -> 0 3 -> 0 4 -> 0 } Graphics saved as "mac1.png" google_rank(): Given an NxN incidence matrix A, compute the Google matrix G, Then start with a vector of N values 1/N, and repeatedly compute x <= G*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, G*x, G*G*x [[0.33216717 0.33216714 0.33216714] [0.31234207 0.3123421 0.31234207] [0.03 0.03 0.03 ] [0.03 0.03 0.03 ] [0.29549076 0.29549076 0.29549078]] power_rank(): Given an NxN incidence matrix A, compute the transition matrix T, Then start with a vector of N values 1/N, and repeatedly compute x <= T*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, T*x, T*T*x [[0.6 0.2 0.2] [0.2 0.6 0.2] [0. 0. 0. ] [0. 0. 0. ] [0.2 0.2 0.6]] surf_rank(): Given an NxN incidence matrix A, compute the Google matrix T, and then repeatedly visit nodes, keeping track of how often you visited. 15 per cent of the time, simply take a random jump to a node. The rest of the time, follow a random link from the current node. When done, the node weight is the number of visits normalized by the total number of visits. Node weights: [0.3293 0.3143 0.03 0.0293 0.2971] Test 1 16 node MacCormick example Incidence matrix A: [[0. 1. 1. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 1. 0. 1. 1. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 1. 1. 1. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.] [1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]] Transition matrix T: [[0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. ] [0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 1. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0.5 1. 0. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0.5 0.5 0. 0.33333333 0. 0.2 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0.33333333 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0.33333333 1. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.2 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.2 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.2 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.2 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 1. 1. 1. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. ]] // mac2 digraph { 0 [label=0] 1 [label=1] 2 [label=2] 3 [label=3] 4 [label=4] 5 [label=5] 6 [label=6] 7 [label=7] 8 [label=8] 9 [label=9] 10 [label=10] 11 [label=11] 12 [label=12] 13 [label=13] 14 [label=14] 15 [label=15] 0 -> 1 0 -> 2 0 -> 5 1 -> 3 2 -> 3 2 -> 4 3 -> 4 4 -> 6 4 -> 7 5 -> 4 5 -> 6 6 -> 14 7 -> 6 7 -> 8 7 -> 9 8 -> 9 9 -> 6 9 -> 10 9 -> 11 9 -> 12 9 -> 13 10 -> 14 11 -> 14 12 -> 14 13 -> 14 14 -> 15 15 -> 0 } Graphics saved as "mac2.png" google_rank(): Given an NxN incidence matrix A, compute the Google matrix G, Then start with a vector of N values 1/N, and repeatedly compute x <= G*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, G*x, G*G*x [[0.12464052 0.12464052 0.12464052] [0.04468981 0.04468981 0.04468981] [0.04468981 0.04468981 0.04468981] [0.06635451 0.06635451 0.06635451] [0.10376268 0.10376268 0.10376268] [0.04468981 0.04468981 0.04468981] [0.09533174 0.09533174 0.09533174] [0.05347414 0.05347414 0.05347414] [0.02452601 0.02452601 0.02452601] [0.04537311 0.04537311 0.04537311] [0.01708843 0.01708843 0.01708843] [0.01708843 0.01708843 0.01708843] [0.01708843 0.01708843 0.01708843] [0.01708843 0.01708843 0.01708843] [0.14850764 0.14850764 0.14850764] [0.13560649 0.13560649 0.13560649]] power_rank(): Given an NxN incidence matrix A, compute the transition matrix T, Then start with a vector of N values 1/N, and repeatedly compute x <= T*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, T*x, T*T*x [[0.13953502 0.13953496 0.13953486] [0.04651167 0.04651167 0.04651165] [0.04651167 0.04651167 0.04651165] [0.06976744 0.0697675 0.06976751] [0.11627898 0.1162791 0.11627917] [0.04651167 0.04651167 0.04651165] [0.10852702 0.10852707 0.10852715] [0.05813945 0.05813949 0.05813955] [0.01937982 0.01937982 0.01937983] [0.03875966 0.03875964 0.03875965] [0.00775194 0.00775193 0.00775193] [0.00775194 0.00775193 0.00775193] [0.00775194 0.00775193 0.00775193] [0.00775194 0.00775193 0.00775193] [0.13953486 0.1395348 0.13953481] [0.13953496 0.13953486 0.1395348 ]] surf_rank(): Given an NxN incidence matrix A, compute the Google matrix T, and then repeatedly visit nodes, keeping track of how often you visited. 15 per cent of the time, simply take a random jump to a node. The rest of the time, follow a random link from the current node. When done, the node weight is the number of visits normalized by the total number of visits. Node weights: [0.1265 0.0413 0.0454 0.0616 0.1007 0.0465 0.0924 0.054 0.0261 0.0463 0.0176 0.0174 0.0191 0.0157 0.1522 0.1372] Test 2 6 node Moler example Incidence matrix A: [[0. 1. 0. 0. 0. 1.] [0. 0. 1. 1. 0. 0.] [0. 0. 0. 1. 1. 1.] [1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 1. 0.] [1. 0. 0. 0. 0. 0.]] Transition matrix T: [[0. 0. 0. 1. 0. 1. ] [0.5 0. 0. 0. 0. 0. ] [0. 0.5 0. 0. 0. 0. ] [0. 0.5 0.33333333 0. 0. 0. ] [0. 0. 0.33333333 0. 1. 0. ] [0.5 0. 0.33333333 0. 0. 0. ]] // moler digraph { 0 [label=0] 1 [label=1] 2 [label=2] 3 [label=3] 4 [label=4] 5 [label=5] 0 -> 1 0 -> 5 1 -> 2 1 -> 3 2 -> 3 2 -> 4 2 -> 5 3 -> 0 4 -> 4 5 -> 0 } Graphics saved as "moler.png" google_rank(): Given an NxN incidence matrix A, compute the Google matrix G, Then start with a vector of N values 1/N, and repeatedly compute x <= G*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, G*x, G*G*x [[0.23527488 0.23527488 0.23527488] [0.12499183 0.12499183 0.12499183] [0.07812153 0.07812153 0.07812153] [0.10025596 0.10025596 0.10025596] [0.31422955 0.31422955 0.31422955] [0.14712626 0.14712626 0.14712626]] power_rank(): Given an NxN incidence matrix A, compute the transition matrix T, Then start with a vector of N values 1/N, and repeatedly compute x <= T*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, T*x, T*T*x [[0.01096194 0.01060736 0.01026425] [0.00566419 0.00548097 0.00530368] [0.00292677 0.0028321 0.00274049] [0.00393497 0.00380768 0.00368452] [0.96983974 0.97081533 0.97175936] [0.00667239 0.00645656 0.00624771]] surf_rank(): Given an NxN incidence matrix A, compute the Google matrix T, and then repeatedly visit nodes, keeping track of how often you visited. 15 per cent of the time, simply take a random jump to a node. The rest of the time, follow a random link from the current node. When done, the node weight is the number of visits normalized by the total number of visits. Node weights: [0.2178 0.1206 0.0749 0.0932 0.3598 0.1337] Test 3 6 node example Incidence matrix A: [[0. 1. 0. 0. 0. 0.] [0. 0. 1. 0. 1. 0.] [1. 0. 0. 1. 0. 0.] [1. 0. 0. 0. 0. 0.] [0. 1. 0. 0. 0. 1.] [0. 0. 0. 1. 0. 0.]] Transition matrix T: [[0. 0. 0.5 1. 0. 0. ] [1. 0. 0. 0. 0.5 0. ] [0. 0.5 0. 0. 0. 0. ] [0. 0. 0.5 0. 0. 1. ] [0. 0.5 0. 0. 0. 0. ] [0. 0. 0. 0. 0.5 0. ]] // six digraph { 0 [label=0] 1 [label=1] 2 [label=2] 3 [label=3] 4 [label=4] 5 [label=5] 0 -> 1 1 -> 2 1 -> 4 2 -> 0 2 -> 3 3 -> 0 4 -> 1 4 -> 5 5 -> 3 } Graphics saved as "six.png" google_rank(): Given an NxN incidence matrix A, compute the Google matrix G, Then start with a vector of N values 1/N, and repeatedly compute x <= G*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, G*x, G*G*x [[0.21593282 0.21593282 0.21593282] [0.26748179 0.26748179 0.26748179] [0.13867976 0.13867976 0.13867976] [0.15528696 0.15528696 0.15528696] [0.13867976 0.13867976 0.13867976] [0.0839389 0.0839389 0.0839389 ]] power_rank(): Given an NxN incidence matrix A, compute the transition matrix T, Then start with a vector of N values 1/N, and repeatedly compute x <= T*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, T*x, T*T*x [[0.21428571 0.21428571 0.21428571] [0.28571429 0.28571429 0.28571429] [0.14285714 0.14285714 0.14285714] [0.14285714 0.14285714 0.14285714] [0.14285714 0.14285714 0.14285714] [0.07142857 0.07142857 0.07142857]] surf_rank(): Given an NxN incidence matrix A, compute the Google matrix T, and then repeatedly visit nodes, keeping track of how often you visited. 15 per cent of the time, simply take a random jump to a node. The rest of the time, follow a random link from the current node. When done, the node weight is the number of visits normalized by the total number of visits. Node weights: [0.2156 0.2708 0.1356 0.1517 0.1434 0.0829] Test 4 15 node Sauer example Incidence matrix A: [[0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.] [0. 0. 1. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 1. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0. 0.] [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.] [0. 0. 0. 0. 1. 1. 0. 0. 0. 1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.] [0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 1. 0. 1.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 1. 0.]] Transition matrix T: [[0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0.5 0. 0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0.33333333 0. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. ] [0. 0.33333333 0. 0. 0. 0. 0. 0. 0.33333333 0. 0. 0. 0. 0. 0. ] [0. 0. 0.33333333 0. 0. 0. 0. 0. 0.33333333 0. 0. 0. 0. 0. 0. ] [0. 0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.33333333 0. 0. 0. ] [0. 0. 0.33333333 0. 0. 0. 0. 0. 0. 0. 0. 0.33333333 0. 0. 0. ] [0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.5 0. 0. ] [0. 0. 0. 0. 0.5 0.5 0.5 0. 0.33333333 0. 0. 0. 0. 0.25 0. ] [0. 0. 0. 0. 0. 0.5 0.5 0.5 0. 0. 0. 0.33333333 0. 0.25 0. ] [0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.5 ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.25 0. ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.5 0. 0.5 ] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.25 0. ]] // sauer digraph { 0 [label=0] 1 [label=1] 2 [label=2] 3 [label=3] 4 [label=4] 5 [label=5] 6 [label=6] 7 [label=7] 8 [label=8] 9 [label=9] 10 [label=10] 11 [label=11] 12 [label=12] 13 [label=13] 14 [label=14] 0 -> 1 0 -> 8 1 -> 2 1 -> 4 1 -> 6 2 -> 1 2 -> 5 2 -> 7 3 -> 2 3 -> 11 4 -> 0 4 -> 9 5 -> 9 5 -> 10 6 -> 9 6 -> 10 7 -> 3 7 -> 10 8 -> 4 8 -> 5 8 -> 9 9 -> 12 10 -> 14 11 -> 6 11 -> 7 11 -> 10 12 -> 8 12 -> 13 13 -> 9 13 -> 10 13 -> 12 13 -> 14 14 -> 11 14 -> 13 } Graphics saved as "sauer.png" google_rank(): Given an NxN incidence matrix A, compute the Google matrix G, Then start with a vector of N values 1/N, and repeatedly compute x <= G*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, G*x, G*G*x [[0.02682457 0.02682457 0.02682457] [0.02986108 0.02986108 0.02986108] [0.02986108 0.02986108 0.02986108] [0.02682457 0.02682457 0.02682457] [0.03958722 0.03958722 0.03958722] [0.03958722 0.03958722 0.03958722] [0.03958722 0.03958722 0.03958722] [0.03958722 0.03958722 0.03958722] [0.07456439 0.07456439 0.07456439] [0.10631995 0.10631995 0.10631995] [0.10631995 0.10631995 0.10631995] [0.07456439 0.07456439 0.07456439] [0.12509164 0.12509164 0.12509164] [0.11632789 0.11632789 0.11632789] [0.12509164 0.12509164 0.12509164]] power_rank(): Given an NxN incidence matrix A, compute the transition matrix T, Then start with a vector of N values 1/N, and repeatedly compute x <= T*x After many steps, compare last three iterates. If they are close, we are probably at an eigenvector associated with the eigenvalue 1. x, T*x, T*T*x [[0.01544402 0.01544402 0.01544402] [0.01158301 0.01158301 0.01158301] [0.01158301 0.01158301 0.01158301] [0.01544402 0.01544402 0.01544402] [0.03088803 0.03088803 0.03088803] [0.03088803 0.03088803 0.03088803] [0.03088803 0.03088803 0.03088803] [0.03088803 0.03088803 0.03088803] [0.08108108 0.08108108 0.08108108] [0.11003861 0.11003861 0.11003861] [0.11003861 0.11003861 0.11003861] [0.08108108 0.08108108 0.08108108] [0.14671815 0.14671815 0.14671815] [0.14671815 0.14671815 0.14671815] [0.14671815 0.14671815 0.14671815]] surf_rank(): Given an NxN incidence matrix A, compute the Google matrix T, and then repeatedly visit nodes, keeping track of how often you visited. 15 per cent of the time, simply take a random jump to a node. The rest of the time, follow a random link from the current node. When done, the node weight is the number of visits normalized by the total number of visits. Node weights: [0.0268 0.0251 0.0281 0.0263 0.0412 0.0413 0.0406 0.0382 0.0725 0.1069 0.1082 0.0754 0.1258 0.1176 0.126 ] pagerank_test(): Normal end of execution. Sun Aug 7 20:50:03 2022