Статьи

Java / JBLAS: вычисление центральности собственного вектора матрицы смежности

Сентябрь 2, 2018

Недавно я наткнулся на очень интересный пост Кирана Хили, где он  просматривает кучу графовых алгоритмов,  чтобы узнать, сможет ли он обнаружить наиболее влиятельных людей, стоящих за американской революцией, на основе их членства в различных организациях.

Первым алгоритмом, который он рассмотрел, была центральность промежуточности, на которую  я смотрел ранее,  и которая используется для определения нагрузки и важности узла в графе.

Этот алгоритм назначит высокий балл узлам, к которым подключено множество узлов, даже если эти узлы не обязательно являются влиятельными узлами на графике.

Если мы хотим принять во внимание влияние других узлов, то мы можем использовать алгоритм, называемый центральностью собственного вектора .

Центральность собственного вектора — это мера влияния узла в сети. Он назначает относительные оценки всем узлам в сети на основе концепции, согласно которой  подключения к узлам с высоким показателем в большей степени влияют на оценку рассматриваемого узла,  чем равные подключения к узлам с низким показателем.

Google  PageRank  является вариантом меры центральности Eigenvector.

И центральность PageRank, и Eigenvector дают нам вероятность, которая описывает, как часто мы в конечном итоге посещали каждый узел при случайном обходе графика.

Насколько я могу судить, существует несколько различий между PageRank и центральностью Eigenvector (но я рад, что меня исправили, так как я все еще изучаю этот материал):

  1. PageRank вводит «демпфирующий фактор», чтобы имитировать идею, что некоторый процент времени мы можем решить не следовать ни одному из отношений узла, а вместо этого выбрать случайный узел на графике.
  2. PageRank гарантирует, что элементы в каждом столбце матрицы смежности суммируют до одного. Следовательно, если бы наш узел имел отношение ко всем остальным в графе, то каждый из них имел бы значение 1 / n, а не 1.

В этом случае, поскольку Хили хотел проанализировать влияние людей, а не веб-страниц, центральность собственного вектора имеет больше смысла.

За последние несколько дней я пытался немного лучше понять эту тему и нашел полезными следующие ресурсы:

Я рассчитал несколько составленных матриц вручную, но обнаружил, что после матрицы 3 × 3 это становится слишком трудным, поэтому я хотел найти библиотеку на основе Java, которую я мог бы использовать вместо этого.

матрица смежности

Это были те, с которыми я столкнулся:

  • JBLAS  — Линейная алгебра для Java
  • JAMA  — Пакет Java Matrix
  • Colt  — продвинутый компьютер для науки
  • Commons Math  — Математическая библиотека Apache Commons
  • la4j  — линейная алгебра для Java
  • MTJ  — Матрица Инструментарий Java

Я слышал о JBLAS и раньше, поэтому решил попробовать одну из матриц смежности, описанную в посте Мерфи Ваггонера об индексе Гулда,  и посмотреть, получу  ли я те же значения центральности собственного вектора.

Первым шагом было определение матрицы, которая может быть представлена ​​в виде массива массивов:

DoubleMatrix matrix = new DoubleMatrix(new double[][] {
{1,1,0,0,1,0,0},
{1,1,0,0,1,0,0},
{0,0,1,1,1,0,0},
{0,0,1,1,1,0,0},
{1,1,1,1,1,1,1},
{0,0,0,0,1,1,1},
{0,0,0,0,1,1,1},
});

Наша следующая остановка — определить собственные значения, которые мы можем сделать, используя следующую функцию:

ComplexDoubleMatrix eigenvalues = Eigen.eigenvalues(matrix);
for (ComplexDouble eigenvalue : eigenvalues.toArray()) {
System.out.print(String.format("%.2f ", eigenvalue.abs()));
}
4.00 2.00 0.00 1.00 2.00 0.00 0.00

Мы хотим получить соответствующий собственный вектор для собственного значения 4, и, насколько я могу судить,  функция Eigen # eigenvectors возвращает свои значения в том же порядке, что и   функция Eigen # eigenvalues, поэтому я написал следующий код для разработки главного собственного вектора:

List<Double> principalEigenvector = getPrincipalEigenvector(matrix);
System.out.println("principalEigenvector = " + principalEigenvector);
 
private static List<Double> getPrincipalEigenvector(DoubleMatrix matrix) {
int maxIndex = getMaxIndex(matrix);
ComplexDoubleMatrix eigenVectors = Eigen.eigenvectors(matrix)[0];
return getEigenVector(eigenVectors, maxIndex);
}
 
private static int getMaxIndex(DoubleMatrix matrix) {
ComplexDouble[] doubleMatrix = Eigen.eigenvalues(matrix).toArray();
int maxIndex = 0;
for (int i = 0; i < doubleMatrix.length; i++){
double newnumber = doubleMatrix[i].abs();
if ((newnumber > doubleMatrix[maxIndex].abs())){
maxIndex = i;
}
}
return maxIndex;
}

В  getMaxIndex  мы определяем , какому индексу в массиве принадлежит наибольшее собственное значение, чтобы мы могли искать его в массиве, который мы получаем из  собственных векторов # . Согласно документации, собственные векторы сохраняются в первой матрице, которую мы возвращаем, поэтому мы выбираем это во второй строке  getPrincipalEigenvector .

Это результат, который мы получаем при запуске:

principalEigenvector = [0.3162277660168381, 0.3162277660168376, 0.316227766016838, 0.316227766016838, 0.6324555320336759, 0.316227766016838, 0.316227766016838]

Наконец, мы нормализуем значения таким образом, чтобы все они складывались вместе равными 1, что означает, что наш результат сообщит% времени, когда случайный обход приведет вас к этому узлу:

System.out.println("normalisedPrincipalEigenvector = " + normalised(principalEigenvector));
 
private static List<Double> normalised(List<Double> principalEigenvector) {
double total = sum(principalEigenvector);
List<Double> normalisedValues = new ArrayList<Double>();
for (Double aDouble : principalEigenvector) {
normalisedValues.add(aDouble / total);
}
return normalisedValues;
}
normalisedPrincipalEigenvector = [0.12500000000000006, 0.12499999999999988, 0.12500000000000003, 0.12500000000000003, 0.25, 0.12500000000000003, 0.12500000000000003]

Мы получаем те же ответы, что и Мерфи, поэтому, я думаю, библиотека работает правильно!

Затем я думаю, что мне следует поэкспериментировать с PageRank на этом графике, чтобы увидеть, как отличается его мера центральности.

46
Share: