HITS算法Java實現

　　HITS算法是重要的鏈接分析算法很多書上是用矩陣的形式來描述HITS算法

　　

　　其中為鄰接矩陣和分別為權威值和中心值冪法迭代算法如下

　　

　　但是為了空間的考慮我們在存儲Web圖的時候一般都是用的鄰接矩陣表示

　　經過分析發現一個頁面的權威值其實是指向它的頁面的中心值之和一個頁面的中心值是它指向的頁面的權威值的過程這是一個相互加強的過程

　　下面是用Java實現的代碼

　　package cnedudlutwisdom;

　　import itunimidsiwebgraphImmutableGraph;

　　import itunimidsiwebgraphLazyIntIterator;

　　import itunimidsiwebgraphNodeIterator;

　　import itunimidsiwebgraphTransform;

　　import orgapachelogjLogger;

　　/**

　　*

　　* @author You Wang

　　*/

　　public class HITS {

　　/**

　　* 正向圖

　　*/

　　private ImmutableGraph g;

　　/**

　　* 反向圖

　　*/

　　private ImmutableGraph ig;

　　/**

　　* 日志

　　*/

　　private final Logger logger;

　　/**

　　* 結點數目

　　*/

　　private int numNodes;

　　/**

　　* 權威分數

　　*/

　　private double[] authorityScores;

　　/**

　　* 中心分數

　　*/

　　private double[] hubScores;

　　/**

　　* 兩次權威分數之差絕對值的和

　　*/

　　private double authorityNorm;

　　/**

　　* 兩次中心分數之差絕對值的和

　　*/

　　private double hubNorm;

　　/**

　　* 迭代次數

　　*/

　　private double numIter = ;

　　/**

　　* 獲取中心差值

　　* @return

　　*/

　　public double getHubNorm() {

　　return hubNorm;

　　}

　　/**

　　* 獲取權威差值

　　* @return

　　*/

　　public double getAuthorityNorm() {

　　return authorityNorm;

　　}

　　/**

　　* 獲取權威分數

　　* @return

　　*/

　　public double[] getAuthorityScores() {

　　return  authorityScores;

　　}

　　/**

　　* 獲取中心分數

　　* @return

　　*/

　　public double[] getHubScores() {

　　return hubScores;

　　}

　　/**

　　* 構造函數

　　* @param g 要計算的Web圖

　　*/

　　public HITS(ImmutableGraph g) {

　　thisg = g;

　　ig = Transformtranspose(g);

　　numNodes = gnumNodes();

　　authorityScores = new double[numNodes];

　　hubScores = new double[numNodes];

　　double is = / numNodes;

　　for (int i = ; i < numNodes; i++) {

　　authorityScores[i] = is;

　　hubScores[i] = is;

　　}

　　logger = LoggergetLogger(HITSclass);

　　}

　　/**

　　* 設定初始權威分數

　　* @param scores

　　*/

　　public void setInitialAuthorityScores(double[] scores) {

　　if (scoreslength != numNodes)

　　throw new IllegalArgumentException(array length mismatch);

　　thisauthorityScores = scores;

　　}

　　/**

　　* 設定初始中心分數

　　* @param scores

　　*/

　　public void setInitialHubScores(double[] scores) {

　　if (scoreslength != numNodes)

　　throw new IllegalArgumentException(array lenght mismatch);

　　thishubScores = scores;

　　}

　　/**

　　* 迭代中的一步

　　*/

　　public void step() {

　　(iter + ++numIter);

　　authorityNorm = ;

　　hubNorm = ;

　　NodeIterator nit = gnodeIterator();

　　NodeIterator init = ignodeIterator();

　　double[] as = new double[numNodes];

　　double[] hs = new double[numNodes];

　　while(nithasNext() && inithasNext()) {

　　int i = nitnextInt();

　　int j = initnextInt();

　　assert (i == j);

　　LazyIntIterator it = initsuccessors();

　　as[i] = ;

　　int k;

　　while ((k = itnextInt()) != ) {

　　as[i] += hubScores[k];

　　}

　　hs[i] = ;

　　it = nitsuccessors();

　　while ((k = itnextInt()) != ) {

　　hs[i] += authorityScores[k];

　　}

　　}

　　// 歸一化處理

　　normalize(as);

　　normalize(hs);

　　authorityNorm = computeNorm(authorityScores as);

　　hubNorm = computeNorm(hubScores hs);

　　authorityScores = as;

　　hubScores = hs;

　　(authority norm: + authorityNorm);

　　(hub norm: + hubNorm);

　　}

　　/**

　　* 歸一化

　　* @param a

　　*/

　　private void normalize(double[] a) {

　　double s = ;

　　for (double d : a)

　　s += d;

　　for (int i = ; i < alength; i++)

　　a[i] /= s;

　　}

　　/**

　　* 計算絕對差和

　　* @param a

　　* @param b

　　* @return

　　*/

　　private double computeNorm(double[] a double[] b) {

　　if (alength != blength)

　　throw new IllegalArgumentException(array length mismath);

　　double norm = ;

　　for (int i = ; i < alength; i++) {

　　norm += Mathabs(a[i] b[i]);

　　}

　　return norm;

　　}

　　/**

　　* 一直迭代知道達到最大次數限制

　　* @param iter 最大迭代次數

　　*/

　　public void stepUntil(int iter) {

　　while (iter > )

　　step();

　　}

　　/**

　　* 一直迭代直到達到規定的停止基准

　　* @param stopNorm 停止基准

　　*/

　　public void stepUntil(double stopNorm) {

　　while (authorityNorm > stopNorm || hubNorm > stopNorm)

　　step();

　　}

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26820.html