summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLars-Dominik Braun <lars@6xq.net>2015-05-20 11:00:27 +0200
committerLars-Dominik Braun <lars@6xq.net>2015-05-20 11:00:27 +0200
commit0deefd4d9d7ce24cc193ec0db47152957fdd3da3 (patch)
treea817038e0210dd6a260b0ac18210472e948c74af
parent725e08d259249402aec29d82017a1c0d694a1d4e (diff)
downloadcomatose-0deefd4d9d7ce24cc193ec0db47152957fdd3da3.tar.gz
comatose-0deefd4d9d7ce24cc193ec0db47152957fdd3da3.tar.bz2
comatose-0deefd4d9d7ce24cc193ec0db47152957fdd3da3.zip
Implement PageRank for protocol ranking
-rw-r--r--Main.hs27
-rw-r--r--data/script.js4
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);