Взаимность (сетевая наука)

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

Мотивация

В реальных сетевых задачах людей интересует определение вероятности возникновения двойных связей (с противоположными направлениями) между парами вершин. Эта проблема является фундаментальной для несколькихпричины. Во-первых, в сетях, передающих информацию или материалы (таких как сети электронной почты, Всемирная паутина (WWW), Всемирная торговая сеть, или Arc.Ask3.Ru ), взаимные связи облегчают процесс перевозки. Во-вторых, при анализе направленных сетей люди для простоты часто рассматривают их как ненаправленные; следовательно, информация, полученная в результате исследований взаимности, помогает оценить ошибку, вносимую, когда направленная сеть рассматривается как ненаправленная (например, при измерении коэффициента кластеризации ). Наконец, обнаружение нетривиальных закономерностей взаимности может выявить возможные механизмы и принципы организации, которые формируют топологию наблюдаемой сети.

Определения

Традиционное

Традиционный способ определения взаимности $r$ использует соотношение количества ссылок, указывающих в обоих направлениях $L^{<->}$ к общему количеству ссылок L $r={\frac {L^{<->}}{L}}$

Используя это определение, $r=1$ предназначен для чисто двунаправленной сети, в то время как $r=0$ для чисто однонаправленного. Реальные сети имеют промежуточное значение между 0 и 1.

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

Лоффредо

Чтобы преодолеть недостатки приведенного выше определения, Гарлашелли и Лоффредо определили взаимность как коэффициент корреляции между элементами матрицы смежности ориентированного графа ( $a_{ij}=1$ если ссылка с $i$ к $j$ существует, и $a_{ij}=0$ если не):

$\rho \equiv {\frac {\sum _{i\neq j}(a_{ij}-{\bar {a}})(a_{ji}-{\bar {a}})}{\sum _{i\neq j}(a_{ij}-{\bar {a}})^{2}}}$,

где среднее значение ${\bar {a}}\equiv {\frac {\sum _{i\neq j}a_{ij}}{N(N-1)}}={\frac {L}{N(N-1)}}$.

${\bar {a}}$ измеряет соотношение наблюдаемых и возможных направленных связей (плотность связей), а самосвязывающиеся петли теперь исключены из $L$ с $i$ не равен $j$.

Определение можно записать в следующей простой форме:

$\rho ={\frac {r-{\bar {a}}}{1-{\bar {a}}}}$

Новое определение взаимности дает абсолютную величину, которая позволяет непосредственно различать взаимные ( $\rho >0$) и антивзаимный ( $\rho <0$) сети, в которых взаимные связи встречаются чаще и реже случайных соответственно.

Если все связи встречаются взаимными парами, $\rho =1$; если $r=0$, $\rho =\rho _{min}$. $\rho _{min}\equiv {\frac {-{\bar {a}}}{1-{\bar {a}}}}$

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