FitNesse测试之Script table
Java 读取 doc docx pdf rtf txt html 文件文本内容

PageRank on undirected and weighted graph

Jimmy posted @ 2012年3月03日 16:29 in Java Programming , 4189 阅读

最近需要用PageRank算法实现无向带权图节点的ranking,具体的PageRank算法介绍可以参考维基百科http://en.wikipedia.org/wiki/Pagerank

最初的PageRank算法是针对有向图的,迭代方程为:$PR(P_{i}) = \frac{1-d}{n}+d \sum_{p_{j}\in M(p_{i})} \frac{PR(p_{j})}{L(p_{j})}$,其中$PR(p_{i})$是顶点$p_{i}$的PageRank值,$L(p_{j})$是顶点$p_{j}$的出度。

在无向带权图中,改进迭代方程:$PR(P_{i}) = \frac{1-d}{n}+d \sum_{p_{j}\in M(p_{i})} \frac{weight(p_{j}) \times PR(p_{j})}{degree(p_{j})}$ 其中$weight(p_{j})$是边$(p_{i}, p_{j})$的权重,$degree(p_{j})$是顶点$p_{j}$的度数。

在实际迭代计算式,选择好的数据结构很重要,上面迭代公式中主要的计算就是边$(p_{i}, p_{j})$的权重与顶点$p_{j}$的度数。使用Map<String, ArrayList<MapEntry>> 来表示边(node1, <node2, weight>),这样计算权重与度数是都很方便。

实现代码与测试数据可在github上下载:https://github.com/jia1546/PageRank

Avatar_small
Jacky Tsai 说:
2015年4月12日 19:34

你好,我透過github下載了您的程式,但是我不瞭解輸入該放甚麼。
我今天有undirected的關係圖如:
1 2 //代表1 & 2 有關連
1 3 //代表1 & 3 有關連
2 3
3 4 ...等等的關係文件,但是因為沒有weight值不能運算。

不知道能不能請教您"1 2" 的weight要放多少又或是該如何計算weight值,謝謝您。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter