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();
}
}
