Альфа-центральность - Alpha centrality

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

Определение

Учитывая граф с матрица смежности ${ displaystyle A_ {i, j}}$, Центральность Каца определяется следующим образом:

${ displaystyle { vec {x}} = (I- alpha A ^ {T}) ^ {- 1} { vec {e}} - { vec {e}} ,}$

куда ${ displaystyle e_ {j}}$ внешнее значение, придаваемое узлу ${ displaystyle j}$, и ${ displaystyle alpha}$ - неотрицательный коэффициент затухания, который должен быть меньше обратного значения спектральный радиус из ${ displaystyle A}$. Исходное определение Каца^[1]использовал постоянный вектор ${ displaystyle { vec {e}}}$. Хаббелл^[2]ввел использование общего ${ displaystyle { vec {e}}}$.

Полвека спустя Боначич и Ллойд^[3] определил альфа-центральность как

${ displaystyle { vec {x}} = (I- alpha A ^ {T}) ^ {- 1} { vec {e}} ,}$

что по существу идентично центральности Каца. Точнее оценка узла ${ displaystyle j}$ отличается точно на ${ displaystyle e_ {j}}$, так что если ${ displaystyle { vec {e}}}$ постоянна, порядок, наведенный на узлах, одинаков.

Мотивация

Чтобы понять альфа-центральность, нужно сначала понять центральность собственного вектора. Интуитивно понятный процесс вычисления центральности собственного вектора состоит в том, чтобы дать каждому узлу начальную случайную положительную величину влияния. Затем каждый узел равномерно распределяет свое влияние и делит его между своими внешними соседями, получая от своих внутренних соседей в натуральной форме. Этот процесс повторяется до тех пор, пока все не начнут отдавать столько, сколько получают, и система не достигнет устойчивого состояния. Степень влияния, которую они имеют в этом устойчивом состоянии, - это центральность их собственного вектора. Вычислительно этот процесс называется силовой метод. Мы знаем, что этот процесс сходится, когда вектор влияния изменяется только на константу следующим образом:

${ displaystyle x_ {i} = { frac {1} { lambda}} A_ {i, j} ^ {T} x_ {j}}$

куда ${ displaystyle x_ {i}}$ степень влияния этого узла ${ displaystyle i}$ несет, ${ displaystyle A_ {i, j}}$ матрица смежности и ${ displaystyle lambda}$ оказывается главным собственным значением.

Альфа-центральность усиливает этот процесс, позволяя узлам иметь внешние источники влияния. Степень влияния этого узла ${ displaystyle i}$ получает на каждом раунде кодируется в ${ displaystyle e_ {i}}$. Описанный выше процесс теперь должен остановиться, когда

${ displaystyle x_ {i} = alpha A_ {i, j} ^ {T} x_ {j} + e_ {i} ,}$

куда ${ displaystyle alpha}$ - константа, которая противопоставляет важность внешнего влияния важности связи. Когда ${ Displaystyle альфа = 0}$ имеет значение только внешнее влияние. Когда ${ displaystyle alpha}$ очень велико, то имеет значение только связность, т.е. мы сводимся к случаю центральности собственного вектора.

Вместо того, чтобы выполнять описанную выше итерацию, мы можем решить эту систему для ${ displaystyle x}$, получая следующее уравнение:

${ Displaystyle х = (I- альфа A ^ {T}) ^ {- 1} е ,}$

Приложения

Альфа-центральность реализована в библиотеке igraph для сетевого анализа и визуализации.^[4]

Смотрите также

• Кац центральность
• Центральность собственного вектора

Примечания и ссылки