Степень посредничества

Степень посредничества — это мера центральности в графе, основанная на кратчайших путях. Для любой пары вершин в связном графе существует по меньшей мере один (кратчайший) путь между вершинами, для которого минимально либо число рёбер, по которым путь проходит, (для невзвешенных графов), либо сумма весов этих рёбер (для взвешенных графов). Степень посредничества для каждой вершины равна числу этих кратчайших путей через вершину.

Степень посредничества находит широкое применение в теории сетей^[англ.] — она отражает степень, в которой вершины оказываются между другими вершинами. Например, в телекоммуникационной сети, узел с наивысшей степенью посредничества имел бы больший контроль сети, поскольку больше информации проходит через этот узел. Степень посредничества была разработана как общая мера центральности — она может быть применена к широкой области задач в теории сетей, включая задачи, связанные с социальными сетями^[англ.], биологической, транспортной и научной кооперации^[1].

Хотя прежние авторы интуитивно описывали центральность на основе степени посредничества, Фриман^[2] дал первое формальное определение степени посредничества.

Степень посредничества узла ${\displaystyle v}$ задаётся выражением:

${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$,

где ${\displaystyle \sigma _{st}}$ равно общему числу кратчайших путей из узла ${\displaystyle s}$ в узел ${\displaystyle t}$, а ${\displaystyle \sigma _{st}(v)}$ равно числу этих путей, проходящих через ${\displaystyle v}$.

Заметим, что степень посредничества равна части пар узлов с условием, определённым условием суммирования. Поэтому имеются пары узлов, кратчайшие пути которых не включают ${\displaystyle v}$, так, что ${\displaystyle g\in [0,1]}$. Деление осуществляется на ${\displaystyle (N-1)(N-2)}$ для ориентированных графов и на ${\displaystyle (N-1)(N-2)/2}$ для неориентированных графов, где ${\displaystyle N}$ равно числу узлов в наибольшей компоненте. Заметим, что эта величина принимает наибольшее значение, когда одна вершина содержится в любом отдельном кратчайшем пути. Часто это не выполняется и нормализацию можно осуществить без потери точности

${\displaystyle {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

что приводит к

${\displaystyle \max(normal)=1}$

${\displaystyle \min(normal)=0}$

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

${\displaystyle s_{i}=\sum _{j=1}^{N}a_{ij}w_{ij}}$

Когда ${\displaystyle a_{ij}}$ и ${\displaystyle w_{ij}}$ являются матрицами смежности и весов между узлами ${\displaystyle i}$ и ${\displaystyle j}$ соответственно. Аналогично степенному закону распределения степени, обнаруженному в масштабно-инвариантных сетях, степень данного узла подчиняется также степенному закону.

${\displaystyle s(k)\approx k^{\beta }}$

Изучение среднего значения ${\displaystyle s(b)}$ силы вершин со степенью посредничества ${\displaystyle b}$ показывает, что функциональное поведение может быть аппроксимировано выражением^[3]

${\displaystyle s(b)\approx b^{\alpha }}$

Центральность просачивания является версией взвешенной степени посредничества, но учитывает «состояние» узла-источника и узла-цели каждого кратчайшего пути при вычислении веса. «Просачивание» возникает в сложных сетях в большом числе сценариев. Например, вирусная или бактериальная инфекция может распространяться по социальным сетям людей, известным как сети контактов. Распространение болезни может также рассматриваться на высоком уровне абстракции путём рассмотрения сети городов или центров сосредоточения людей, соединённых шоссейными и железными дорогами или авиалиниями. Компьютерные вирусы могут распространяться по компьютерным сетям. Слухи и новости о деловых предложениях и сделках могут распространяться также через социальные сети людей. Во всех этих сценариях «зараза» распространяется по связям сложной сети, меняя «состояния» узлов обратимо или необратимо. Например, в эпидемиологическом сценарии индивидиумы переходят от состояния «восприимчивый» к состоянию «заражён». Состояния конкретных узлов по мере распространения «заразы» могут принимать в приведённых выше примерах двоичные значения (такие как «порция новостей получена/не получена»), дискретные значения (восприимчив/заражён/вылечен), или даже непрерывные (такие как пропорция заражённых людей в городе). Общее во всех этих сценариях в том, что распространение «заразы» приводит к изменению состояния узлов сети. Принимая это во внимание, была предложена центральность просачивания (англ. Percolation centrality, PC), которая измеряет важность узла в терминах способствования просачивания через сеть. Эту меру предложили Пайравинан с соавторами^[4].

Центральность просачивания определяется для заданного узла и в данное время как пропорция «путей просачивания», которые проходят через узел. «Путь просачивания» — это кратчайший путь между парой узлов, где узел-источник в состоянии просачивания (например, заражён). Целевой узел может находиться в состоянии просачивания, непросачивания или в состоянии частичного просачивания.

${\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}}$

где ${\displaystyle \sigma _{sr}}$ равно общему числу кратчайших путей из узла ${\displaystyle s}$ в узел ${\displaystyle r}$, а ${\displaystyle \sigma _{sr}(v)}$ равно числу таких путей, проходящих через ${\displaystyle v}$. Состояние просачивания узла ${\displaystyle i}$ в момент ${\displaystyle t}$ обозначается как ${\displaystyle {x^{t}}_{i}}$ и есть два специальных случая, когда ${\displaystyle {x^{t}}_{i}=0}$, что показывает состояние непротекаемости в момент ${\displaystyle t}$, и когда ${\displaystyle {x^{t}}_{i}=1}$, что говорит о полной протекаемости в момент времени ${\displaystyle t}$. Значения между этим величинами показывают состояния частичного просачивания (например, в сети городов это может быть процент заражённых людей в городе).

Веса путей просачивания зависят от уровней просачивания, назначенных исходным узлам, исходя из постулата, что чем выше уровень просачивания исходного узла, тем более важны пути, исходящие из этого узла. Узлы, которые лежат на кратчайших путях, начинающихся в узлах с высоким просачиванием, поэтому потенциально более важны для просачивания. Определение PC можно также расширить, чтобы включить также веса целевых узлов. Вычисление центральности просачивания осуществляется за время ${\displaystyle O(NM)}$ при эффективной реализации, позаимствованной у быстрого алгоритма Брандеса, а если при вычислениях требуется учёт весов конечных узлов, время худшего случая равно ${\displaystyle O(N^{3})}$.

При вычислении степеней посредничества и степеней близости всех вершин в графе требуется вычисление кратчайших путей между всеми парами вершин графа, что занимает время ${\displaystyle \Theta (|V|^{3})}$ при использовании алгоритма Флойда — Уоршелла, модифицированного для нахождения всех путей, а не одного пути для выделенных двух узлов. На разреженных графах Алгоритм Джонсона или алгоритм Брандеса может быть более эффективным, оба алгоритма работают за время ${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$. На невзвешенных графах вычисление степени посредничества с помощью алгоритма Брандеса занимает время ${\displaystyle O(|V||E|)}$^[5].

При вычислении степеней посредничества и степеней близости всех вершин графа предполагается, что графы неориентированы, связны и разрешены кратные рёбра. Когда работа идёт с сетевыми графами, графы часто не имеют циклов или кратных рёбер, отражая простые связи (здесь рёбра представляют связь между людьми). В этом случае при использовании алгоритма Брандеса конечное значение центральности делят на 2, чтобы учесть, что каждый кратчайший путь учитывается два раза^[6].

Другой алгоритм обобщает степень посредничества Фримана на геодезических и степень посредничества Ньюмана на всех путях путём введения параметра, контролирующего взаимообмен между исследованием и использованием. Временная сложность равна числу рёбер на число узлов в графе^[7].

Концепция центральности была распространена также на групповой уровень^[8]. Групповая степень посредничества показывает долю геодезических, соединяющих пары не принадлежащих группе членов, которые проходят через группу узлов. Алгоритм Брандеса для вычисления степени посредничества всех вершин был модифицирован для вычисления групповой степени посредничества одной группы узлов с тем же асимптотическим временем работы^[8].

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

Мартшрутная степень посредничества обобщает степень посредничества при применении к любой схеме определения простых путей без циклов на основе лишь критерия кратчайшего пути^[9].

• Центральность