From 0deefd4d9d7ce24cc193ec0db47152957fdd3da3 Mon Sep 17 00:00:00 2001
From: Lars-Dominik Braun <lars@6xq.net>
Date: Wed, 20 May 2015 11:00:27 +0200
Subject: Implement PageRank for protocol ranking

---
 Main.hs        | 27 ++++++++++++++++++++-------
 data/script.js |  4 +++-
 2 files changed, 23 insertions(+), 8 deletions(-)

diff --git a/Main.hs b/Main.hs
index 39c636c..4ee68ac 100644
--- a/Main.hs
+++ b/Main.hs
@@ -40,7 +40,7 @@ data Protocol = Protocol {
 	-- “related work” section
 	, prelated :: [String]
 	-- |Relevance of this protocol, calculated (pun intended)
-	, prank :: Int
+	, prank :: Float
 	} deriving Show
 
 -- |A MAC protocol feature
@@ -111,14 +111,27 @@ readDb f = do
 	let (Right bibdb) = bibres
 	return $ calcRank $ yamldb { dpublications = bibdb }
 
--- |Protocol rank/popularity, currently just the number of citations, but could
--- be something more fancy in the future
+-- |Protocol rank/popularity, uses the pagerank algorithm
 calcRank db =
 	let
-		algos = dalgos db
-		pincoming ident = filter (\(_, x) -> ident `elem` prelated x) $ M.toList algos
-		modify ident p = p { prank = length (pincoming ident) }
-	in db { dalgos = M.mapWithKey modify algos }
+		initalgos = M.mapWithKey initial $ dalgos db
+		n = fromIntegral $ M.size $ dalgos db
+		d = 0.85
+		initial ident p = p { prank = 1.0/n }
+		-- Get all incoming references
+		pincoming algos ident = filter (\(_, x) -> ident `elem` prelated x) $ M.toList algos
+		-- Calculate new rank for p
+		modify algos ident p = p { prank = (1-d)/n + d*sum (map inrank (pincoming algos ident)) }
+		-- Incoming rank for p
+		inrank (_, p) = prank p / fromIntegral (length (prelated p))
+		absdiff :: M.Map String Protocol -> (String, Protocol) -> Float
+		absdiff b (ident, p) = abs (prank (b M.! ident) - prank p)
+		rankdiff :: M.Map String Protocol -> M.Map String Protocol -> Float
+		rankdiff a b = 1/n * M.foldlWithKey (\x ident p -> x + absdiff b (ident, p)) 0 a
+		iterateUntil fiter fcmp a = let b = fiter a in if fcmp a b then iterateUntil fiter fcmp b else b
+		run algos = M.mapWithKey (modify algos) algos
+		stop prevalgos algos = rankdiff prevalgos algos > 0.00001
+	in db { dalgos = (iterateUntil run stop initalgos) }
 
 maybeToHtml = maybe (toHtml ("" :: String)) toHtml
 
diff --git a/data/script.js b/data/script.js
index 7e8bef3..9d7354e 100644
--- a/data/script.js
+++ b/data/script.js
@@ -5,7 +5,9 @@ $(document).ready (function () {
 		items.detach ().sort (function (nodeA, nodeB) {
 			var a = $(nodeA).data (by);
 			var b = $(nodeB).data (by);
-			if (typeof a == 'number' || typeof b == 'number') {
+			if (by == 'rank') {
+				a = parseFloat (a);
+				b = parseFloat (b);
 				return a > b ? 1 : (a < b ? -1 : 0);
 			} else {
 				return a.localeCompare (b);
-- 
cgit v1.2.3