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 directed For undirected data, run: python pageRank.py 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 :0.00434165382392
Colorado State :0.00433892942647
Nevada :0.00432803496027
South Florida :0.00431247388258
Florida State :0.00430781518633
Appalachian State :0.0042855078864
Maine :0.00427719960866
San Jose State :0.00421017077414
Georgia Tech :0.00417210375934
Central Michigan :0.00416730758325
Wake Forest :0.00404176127288
Minnesota :0.00399261481722
Bethune-Cookman :0.00395345951099
Louisiana-Lafayette :0.00394932125891
Montana State :0.00392668285699
California :0.0038692041512
Wisconsin :0.00385875981679
Memphis :0.00382804688824
Maryland :0.00380882019124
North Carolina :0.0038077233882
Notre Dame :0.00380022455306
Kentucky :0.0037939751987
Vanderbilt :0.00378971204221
Arizona :0.0037893865312
Oregon State :0.00377213824036
Cal Poly :0.00374115053075
Hawaii :0.0037386301266
Eastern Washington :0.00369986078233
South Carolina :0.00366865310273
Arkansas State :0.0036312635554
Wofford :0.00362089389909
Miami (FL) :0.00361898361937
Northern Arizona :0.00356914337631
Bowling Green :0.00355155219836
UTEP :0.0034868669963
William & Mary :0.00345594533534
Colgate :0.00343346141159
Northern Iowa :0.00341207809157
Clemson :0.00340172846317
Central Arkansas :0.00339275926671
Kansas State :0.00336454093013
Florida International :0.00330978664396
Elon :0.00330964240795
Morgan State :0.00329645553639
Harvard :0.00324203805793
Grambling State :0.00319995545647
Les Miserables
Analysis: The main characters are ranked the highest, which is as expected
Valjean :0.0758308901974
Myriel :0.0429505779458
Gavroche :0.0359160666477
Marius :0.0310172618335
Javert :0.0304815194381
Thenardier :0.0280510981415
Fantine :0.027191326266
Enjolras :0.0219890272928
Cosette :0.0207014337229
MmeThenardier :0.0196084909871
Bossuet :0.0190434224611
Courfeyrac :0.0186615760305
Eponine :0.0178862752016
Mabeuf :0.0175458955297
Joly :0.0172827540076
Bahorel :0.0172689775792
Babet :0.0167910676219
Gueulemer :0.0167728629274
Claquesous :0.0166377902786
MlleGillenormand :0.0163128064923
Feuilly :0.0159647347833
Combeferre :0.0159634323963
Tholomyes :0.0157308656902
Bamatabois :0.0156663859666
Montparnasse :0.0152477377714
Gillenormand :0.0150159848507
Grantaire :0.014524331992
Prouvaire :0.0131993961441
Favourite :0.0126897550776
Fameuil :0.0126870828847
Dahlia :0.0126820677133
Blacheville :0.0126796581368
Zephine :0.0126773324066
Listolier :0.0126750883243
Cochepaille :0.0125074398829
Chenildieu :0.0125030179402
Judge :0.0124920149995
Champmathieu :0.0124884594437
Brevet :0.0124851057688
Brujon :0.0119298962133
Fauchelevent :0.0116775047428
MmeHucheloup :0.0107290724039
MlleBaptistine :0.0103332200281
MmeMagloire :0.0103247490448
Simplice :0.00911030673281
LtGillenormand :0.00874898560852
MmeBurgon :0.00782036048117
Pontmercy :0.0073937575872
Toussaint :0.00686488659601
Woman2 :0.00686488659601
Anzelma :0.00633806764306
MotherInnocent :0.00621997328001
MmePontmercy :0.00602616566625
Child1 :0.0058066429878
Child2 :0.00580537558791
Champtercier :0.00560655179602
Geborand :0.00560655179602
Napoleon :0.00560655179602
Count :0.00560655179602
OldMan :0.00559885107345
Cravatte :0.00559885107345
CountessDeLo :0.00559885107345
Perpetue :0.00542796568708
Magnon :0.00528924458944
Marguerite :0.0052793453439
Jondrette :0.00527170515255
Woman1 :0.00526257949406
BaronessT :0.00516084129531
Gribier :0.0044295217059
MlleVaubois :0.00393126768321
Scaufflaire :0.00373850352216
Labarre :0.00373850352216
Isabeau :0.00373850352216
Gervais :0.00373850352216
MmeDeR :0.00373850352216
Boulatruelle :0.00343826653682
MotherPlutarch :0.00330387114808
Karate
Analysis: Looking through the data, the top people the most connections, thus making them the highest ranked, so itโs as expected
34 :0.100779659381
1 :0.097005456951
33 :0.071576888392
3 :0.0570213307483
2 :0.0528547897183
32 :0.037117301531
4 :0.0358484502685
24 :0.0314579138303
9 :0.0297284975846
14 :0.0295173382004
7 :0.0291367362044
6 :0.0291334696727
30 :0.0262477118839
28 :0.0256009815829
31 :0.0245624539154
8 :0.0244823644259
5 :0.0219971434271
11 :0.0219885658829
25 :0.0210407262397
26 :0.0209763705902
20 :0.0195946521061
29 :0.0195468185624
17 :0.0167941834548
27 :0.0150190551952
13 :0.0146437100611
22 :0.0145596783316
18 :0.0145570208576
19 :0.0145207772694
21 :0.0145118570135
23 :0.0145118570135
15 :0.0145118570135
16 :0.0145118570135
10 :0.014293551594
12 :0.0095651796064
Dolphins
Grin :0.032098769619
Jet :0.0318806892333
Trigger :0.0312662964391
Web :0.0302903715199
SN4 :0.0298427560105
Topless :0.0294801891168
Scabs :0.0283966864331
Patchback :0.0264319121028
Gallatin :0.0263223854408
Beescratch :0.0247553683412
Kringel :0.0246260790508
SN63 :0.0239144788977
Feather :0.0235998207139
SN9 :0.0219581962847
Upbang :0.0217432490668
Stripes :0.0216651111975
SN100 :0.0206241003106
DN21 :0.0201591774591
Haecksel :0.019855361239
Jonah :0.0193677489256
TR99 :0.019209987275
SN96 :0.0176136632619
TR77 :0.0173381999006
Number1 :0.0171934420037
Double :0.0170864915312
Beak :0.0169533238355
MN105 :0.0169216400508
MN83 :0.0168828868947
Hook :0.0166108587996
SN90 :0.0162182764868
Shmuddel :0.015898717753
DN63 :0.0156906891579
PL :0.0153202288699
Fish :0.0150996337083
Oscar :0.0148566792738
Zap :0.0147590831571
DN16 :0.0145192871451
Ripplefluke :0.0133626577398
Bumper :0.0133280233838
Knit :0.0129680844496
Thumper :0.0128173211756
TSN103 :0.0120603851553
Mus :0.0115560295913
Notch :0.0112467062498
Zipfel :0.0110318043671
MN60 :0.00985621187565
CCL :0.00962034429327
TR88 :0.00887000341
TR120 :0.00881850953712
Wave :0.00836058683041
TSN83 :0.00817461979539
SN89 :0.00778446718663
Vau :0.00748623884361
Zig :0.00620544119831
Quasi :0.0054370288389
MN23 :0.00543030882186
TR82 :0.00528011214892
Cross :0.00507523069316
Five :0.00507523069316
Whitetip :0.0049602682216
SMN5 :0.00491419391454
Fork :0.00483181375568
Conclusion
PageRank worked well for most of the datasets, but it worked best for datasets with Directed graphs. The results seemed less relevant for undirected graphs because each edge specifies a two way relation between two nodes. Directed graphs are more specific in that a link to a page does not necessarily imply that page links back. For this reason we conclude that pageRank is much more useful on directed graphs. Also, at first we only iterated over the graph once, but realizing that we need to recalibrate the links after every run, we ran it over the graph multiple times, which yielded much better results.