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

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

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

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

[math]\displaystyle{ g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} }[/math],

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

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

[math]\displaystyle{ \mbox{normal}(g(v))=\frac{g(v) - \min(g)}{\max(g) - \min(g)} }[/math]

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

[math]\displaystyle{ \max(normal)=1 }[/math]

[math]\displaystyle{ \min(normal)=0 }[/math]