pagerank_test 18-Feb-2019 18:26:44 pagerank_test MATLAB version. Test pagerank. Test 1: 5 node graph with a cycle. 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 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 POWER_GRAPH: Given an NxN adjacency 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 1: 0.6 0.2 0.2 2: 0.2 0.6 0.2 3: 0 0 0 4: 0 0 0 5: 0.2 0.2 0.6 SURF_GRAPH: Given an NxN adjacency matrix A, compute the transition 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.32881 0.29388 0.0555 0.05529 0.26652 Test 2: 16 node graph. a = Columns 1 through 15 0 1 1 0 0 1 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 1 1 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 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 1 0 0 0 0 0 0 1 0 1 1 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 1 0 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 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 1 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 Column 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 t = Columns 1 through 9 0 0 0 0 0 0 0 0 0 0.3333 0 0 0 0 0 0 0 0 0.3333 0 0 0 0 0 0 0 0 0 1.0000 0.5000 0 0 0 0 0 0 0 0 0.5000 1.0000 0 0.5000 0 0 0 0.3333 0 0 0 0 0 0 0 0 0 0 0 0 0.5000 0.5000 0 0.3333 0 0 0 0 0 0.5000 0 0 0 0 0 0 0 0 0 0 0 0.3333 0 0 0 0 0 0 0 0 0.3333 1.0000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.0000 0 0 0 0 0 0 0 0 0 0 0 Columns 10 through 16 0 0 0 0 0 0 1.0000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.2000 0 0 0 0 0 0 0.2000 0 0 0 0 0 0 0.2000 0 0 0 0 0 0 0.2000 0 0 0 0 0 0 0 1.0000 1.0000 1.0000 1.0000 0 0 0 0 0 0 0 1.0000 0 POWER_GRAPH: Given an NxN adjacency 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 1: 0.139535 0.139535 0.139535 2: 0.0465117 0.0465117 0.0465117 3: 0.0465117 0.0465117 0.0465117 4: 0.0697674 0.0697675 0.0697675 5: 0.116279 0.116279 0.116279 6: 0.0465117 0.0465117 0.0465117 7: 0.108527 0.108527 0.108527 8: 0.0581394 0.0581395 0.0581396 9: 0.0193798 0.0193798 0.0193798 10: 0.0387597 0.0387596 0.0387596 11: 0.00775194 0.00775193 0.00775193 12: 0.00775194 0.00775193 0.00775193 13: 0.00775194 0.00775193 0.00775193 14: 0.00775194 0.00775193 0.00775193 15: 0.139535 0.139535 0.139535 16: 0.139535 0.139535 0.139535 SURF_GRAPH: Given an NxN adjacency matrix A, compute the transition 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.11056 0.04416 0.0434 0.06478 0.0944 0.04406 0.08677 0.05057 0.02895 0.05141 0.02536 0.02452 0.02434 0.02459 0.15274 0.12939 Test 3: 6 node graph. 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 0 0 1 0 0 0 0 0 t = 0 0 0 1.0000 0 1.0000 0.5000 0 0 0 0 0 0 0.5000 0 0 0 0 0 0.5000 0.3333 0 0 0 0 0 0.3333 0 0 0 0.5000 0 0.3333 0 0 0 POWER_GRAPH: Given an NxN adjacency 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 1: 0.0109619 0.0106074 0.0102642 2: 0.00566419 0.00548097 0.00530368 3: 0.00292677 0.0028321 0.00274049 4: 0.00393497 0.00380768 0.00368452 5: 0.0010082 0.000975589 0.000944032 6: 0.00667239 0.00645656 0.00624771 SURF_GRAPH: Given an NxN adjacency matrix A, compute the transition 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.30001 0.16306 0.11545 0.14353 0.08476 0.19319 Test 4: 6 node graph. 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 t = 0 0 0.5000 1.0000 0 0 1.0000 0 0 0 0.5000 0 0 0.5000 0 0 0 0 0 0 0.5000 0 0 1.0000 0 0.5000 0 0 0 0 0 0 0 0 0.5000 0 v1 = Columns 1 through 4 0.4867 + 0.0000i 0.5122 + 0.0000i 0.5122 + 0.0000i 0.1806 - 0.3307i 0.6489 + 0.0000i 0.0240 - 0.4869i 0.0240 + 0.4869i -0.5984 + 0.0000i 0.3244 + 0.0000i -0.3381 - 0.0672i -0.3381 + 0.0672i 0.3612 + 0.2204i 0.3244 + 0.0000i 0.2221 + 0.3919i 0.2221 - 0.3919i -0.1677 + 0.1559i 0.3244 + 0.0000i -0.3381 - 0.0672i -0.3381 + 0.0672i 0.3612 + 0.2204i 0.1622 + 0.0000i -0.0820 + 0.2295i -0.0820 - 0.2295i -0.1368 - 0.2661i Columns 5 through 6 0.1806 + 0.3307i 0.0000 + 0.0000i -0.5984 + 0.0000i -0.0000 + 0.0000i 0.3612 - 0.2204i 0.8165 + 0.0000i -0.1677 - 0.1559i -0.4082 + 0.0000i 0.3612 - 0.2204i 0.0000 + 0.0000i -0.1368 + 0.2661i -0.4082 + 0.0000i l1 = Columns 1 through 4 1.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.1036 + 0.6995i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.1036 - 0.6995i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i -0.6036 + 0.3684i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i Columns 5 through 6 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i -0.6036 - 0.3684i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i ans = 1.0e-15 * 0 0.2113 -0.0961 -0.2776 -0.0961 0.0872 POWER_GRAPH: Given an NxN adjacency 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 1: 0.214286 0.214286 0.214286 2: 0.285714 0.285714 0.285714 3: 0.142857 0.142857 0.142857 4: 0.142857 0.142857 0.142857 5: 0.142857 0.142857 0.142857 6: 0.0714286 0.0714286 0.0714286 SURF_GRAPH: Given an NxN adjacency matrix A, compute the transition 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.21293 0.25098 0.1375 0.16404 0.13841 0.09614 pagerank_test Normal end of execution. 18-Feb-2019 18:26:48 diary off