Пусть G будет nxn матрица смежности взвешенного ориентированного графа.Определите вектор центральности Каца как c = ( I - a G ) ^ {- 1}. b , где I - единичная матрица, a - положительный скаляр, b - вектор-столбец, и.обозначает точечное произведение.Я работаю с разреженным графом G из 1 миллиона узлов.
Предположим, что упомянутое обратное существует.Я пытаюсь вычислить для каждого узла i вклад узла i в его центральность Каца.То есть меня интересует вектор d , определяемый как:
d = diag [( I - a G ) ^ {- 1}]. b ,
, где diag [ G ] - диагональматрицы G .
Библиотека графических инструментов содержит функцию katz для эффективного вычисления вектора c .Однако, похоже, что у него нет какой-либо функции для вычисления вектора d .
Я попытался вычислить d , расширив обратное, чтобы вычислить:
d = diag [I]. b + diag [a G]. b + diag [a ^ 2 G ^ 2]. b + ...
Однако G ^ k очень быстро становится плотным с k, и моему компу не хватает памяти.Расширение до k = 10 будет работать для меня.Любое предложение о том, как рассчитать d , когда G является разреженной матрицей?
У меня на компе 16 ГБ ОЗУ.