WARNING

This is NOT a complete, nor even a very good, PageRank implementation. This was a learning implementation and, as such, should be treated as a simple learning project. Use at your own risk.

PageRank

Timothy Asp (@timothyasp)

Caleb Carlton (@ccarlton)

Run Instructions:

NOTE: NetworkX is required for installation. Run sudo easy_install networkx

For directed data, run: python pageRank.py <datasource> directed For undirected data, run: python pageRank.py <datasource> undirected

Implementation

Generates a directed or undirected graph of the data, then runs the PageRank algorithm, iterating over every node checking the neighbors (undirected) and out-edges (directed). We used NetworkX (http://networkx.lanl.gov/) for out graphs which is a great python library for creating and maintaining these graphs. For D, which is the probability that the user will randomly go to a different page, we chose .85 which is what the book had as the probability for D. The graph is iterated over 10 times, to calculate the rank best.

State Borders

Analysis: The top ranked states are all high density area states, meaning they have lots of state borders, which makes sense and matches expected output.

   MO                             :0.0315971844476
   KY                             :0.0311331684216
   TN                             :0.0310935756102
   MA                             :0.0287725140929
   PA                             :0.0269173607527
   MD                             :0.0267222576413
   GA                             :0.0262810787353
   NY                             :0.0261652680999
   SD                             :0.0259332059378
   WY                             :0.0256935355929
   IA                             :0.0255032593163
   CO                             :0.0252932994762
   VA                             :0.0250814382815
   ID                             :0.0250734427792
   AR                             :0.023278072507
   OK                             :0.0223321781313
   NV                             :0.0216708088742
   NB                             :0.0214511655309
   NE                             :0.0214511655309
   OH                             :0.021122132435
   WV                             :0.02097603798
   TX                             :0.0203753104517
   NH                             :0.0203612457806
   UT                             :0.0201041909315
   IL                             :0.0194874330536
   OR                             :0.0186831020097
   KS                             :0.0182382396929
   AL                             :0.0180729949833
   VT                             :0.0180524967929
   NC                             :0.017964064708
   CT                             :0.0177488522188
   AZ                             :0.0175795169308
   MS                             :0.0171642829093
   IN                             :0.0170252621532
   WI                             :0.0167143241873
   MT                             :0.0164648690288
   MN                             :0.0164414868817
   NM                             :0.0163676118695
   NJ                             :0.0154237955317
   DE                             :0.0149027237957
   CA                             :0.014328872014
   MI                             :0.0137016010819
   LA                             :0.0133453258507
   ND                             :0.0130759232999
   RI                             :0.0128664771188
   FL                             :0.0104997265484
   SC                             :0.0104816930419
   WA                             :0.0104611056458
   DC                             :0.0102730766081
   MV                             :0.0100317563706
   ME                             :0.00871019610841

Political Blogs

   855                            :0.0123982365159
   155                            :0.0102073178341
   963                            :0.0085996555082
   1051                           :0.00779787367556
   641                            :0.00740159936356
   55                             :0.00708484611118
   1245                           :0.0059611211307
   1153                           :0.00569707706033
   1437                           :0.00562599374973
   729                            :0.00547134446998
   1112                           :0.00527363212751
   1479                           :0.00487418572979
   1041                           :0.00469773070457
   454                            :0.00469567338062
   1101                           :0.00464578664097
   363                            :0.00447834018621
   323                            :0.00435790083927
   1000                           :0.0038614062333
   798                            :0.00381999172434
   642                            :0.00370102086354
   741                            :0.0036547261639
   979                            :0.00362174829003
   434                            :0.0036180870679
   1179                           :0.00350056696695
   493                            :0.00346775923273
   512                            :0.0034349511101
   880                            :0.00342661996956
   180                            :0.00341641339595
   996                            :0.00340638815647
   1270                           :0.00340087077945
   387                            :0.00339655223689
   1461                           :0.00332533847476
   878                            :0.00324778609618
   756                            :0.0032359049905
   1306                           :0.00315517498621
   144                            :0.00312457924806
   483                            :0.00309610699993
   535                            :0.00308475291018
   99                             :0.00307278802084
   1330                           :0.00301907244338
   189                            :0.00301478979974
   1209                           :0.00300901159605
   980                            :0.00299508763393
   170                            :0.00298107564567
   1463                           :0.00283380952926
   762                            :0.00280848085965
   856                            :0.00279802241224
   644                            :0.00276932320703
   1384                           :0.00276752568959
   547                            :0.0027426663457
   514                            :0.00273565583007
   72                             :0.00273238941209
   919                            :0.00273076502953
   664                            :0.00272610535733
   687                            :0.00270819350753
   150                            :0.00269966673637
   524                            :0.00268026659323
   826                            :0.00266091439199
   119                            :0.00265691688035
   297                            :0.00264045909771
   935                            :0.00263408868513
   892                            :0.00261845274543
   … trimmed

NCAA

Analysis: A quick look through the 2009 season results show that most of the teams ranked the highest we’re the division leaders and winning teams.

   Boise State                    :0.00733262361219
   Utah                           :0.00722435930833
   Montana                        :0.00709947017054
   Tulsa                          :0.00670055195551
   Ball State                     :0.0063758368291
   Texas                          :0.00636546801443
   Rice                           :0.00636420852951
   Alabama                        :0.00625447664103
   Florida                        :0.00624166939591
   TCU                            :0.00612222447911
   Texas Tech                     :0.00602273860572
   Penn State                     :0.00583129342948
   Cincinnati                     :0.00575753270947
   Oklahoma                       :0.0056904527237
   Richmond                       :0.00547645775694
   East Carolina                  :0.00529388406925
   Missouri                       :0.00524749922454
   Ohio State                     :0.00522310227913
   Brigham Young                  :0.00514457541395
   Weber State                    :0.00513022880521
   Nebraska                       :0.00504668897937
   USC                            :0.00499134298746
   New Hampshire                  :0.00498805759706
   Georgia                        :0.00496366497189
   Michigan State                 :0.00492355290029
   Iowa                           :0.00491360116607
   Western Michigan               :0.00488826180424
   James Madison                  :0.00488409341977
   Houston                        :0.00487147333886
   Northwestern                   :0.00485804367807
   Troy                           :0.00481302701871
   Pittsburgh                     :0.00480537805717
   Louisiana Tech                 :0.00476687389604
   Air Force                      :0.00472795714934
   Oklahoma State                 :0.00472453412691
   Buffalo                        :0.00469183049703
   West Virginia                  :0.00468412914986
   Virginia Tech                  :0.00467792833048
   Villanova                      :0.00461018702304
   Mississippi                    :0.00460722692705
   LSU                            :0.00458586681751
   South Carolina State           :0.00457632203178
   Navy                           :0.00455469420055
   Oregon                         :0.00455031908469
   Boston College                 :0.00453703396878
   Fresno State                   :0.00444681070456
   Rutgers                        :0.00440682553538
   Florida Atlantic               :0.00439888351631
   Connecticut                    :0.00437901660454
   Florida A&M                    :0.00437700673944
   Kansas                         :0.00437053073582
   Southern Miss