pagerank.cpp

// ////////////////////////////////////////////////////////////////
// PageRank を求める
// 参考: http://homepage2.nifty.com/baba_hajime/wais/pagerank.html
// ////////////////////////////////////////////////////////////////
#include <iostream>

#include <tnt_array1d.h>
#include <tnt_array1d_utils.h>
#include <tnt_array2d.h>
#include <tnt_array2d_utils.h>
#include <jama_eig.h>

TNT::Array1D<double>
calc_abs(const TNT::Array1D<double>& real, const TNT::Array1D<double>& imag)
{
  TNT::Array1D<double> v(real.dim1());
  int i;
  for (i = 0; i < v.dim1(); ++i) {
    v[i] = sqrt(real[i]*real[i] + imag[i]*imag[i]);
  }
  return v;
}

int
max_index(const TNT::Array1D<double>& v)
{
  int index = 0;
  int i;
  for (i = 0; i < v.dim1(); ++i) {
    if (v[i] > v[index]) index = i;
  }
  return index;
}

int
main(int, char *[])
{
  double a[] = {
    0.0,     1.0, 1.0/2.0, 0.0,     1.0/4.0, 1.0/2.0, 0.0,
    1.0/5.0, 0.0, 1.0/2.0, 1.0/3.0, 0.0,     0.0,     0.0,
    1.0/5.0, 0.0, 0.0,     1.0/3.0, 1.0/4.0, 0.0,     0.0,
    1.0/5.0, 0.0, 0.0,     0.0,     1.0/4.0, 0.0,     0.0,
    1.0/5.0, 0.0, 0.0,     1.0/3.0, 0.0,     1.0/2.0, 1.0,
    0.0,     0.0, 0.0,     0.0,     1.0/4.0, 0.0,     0.0,
    1.0/5.0, 0.0, 0.0,     0.0,     0.0,     0.0,     0.0,
  };
  TNT::Array2D<double> m(7, 7);

  int i, j, k = 0;
  for (i = 0; i < m.dim1(); ++i) {
    for (j = 0; j < m.dim2(); ++j, ++k) {
      m[i][j] = a[k];
    }
  }

  JAMA::Eigenvalue<double> eig(m);
  TNT::Array1D<double> d, e;
  eig.getRealEigenvalues(d);
  eig.getImagEigenvalues(e);
  int n = max_index(calc_abs(d, e));

  TNT::Array2D<double> V;
  eig.getV(V);
  double norm = 0.0;
  for (i = 0; i < V.dim1(); ++i) {
    norm += fabs(V[i][n]);
  }
  TNT::Array1D<double> PageRank(V.dim1());
  for (i = 0; i < V.dim1(); ++i) {
    PageRank[i] = V[i][n] / norm;
  }
  std::cout << "PageRank:" << std::endl;
  std::cout << PageRank << std::endl;

  return 0;
}