Эффективность (сетевая наука)

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

Определение

Определение эффективности связи предполагает, что эффективность обратно пропорциональна расстоянию, поэтому в математических терминах

$\epsilon _{ij}={\frac {1}{d_{ij}}}$

где $\epsilon _{ij}$ - попарная эффективность узлов $i,j\in V$ в сети $G=(V,E)$ и $d_{ij}$ это их расстояние .

Средняя эффективность связи сети $G$ затем определяется как среднее по парным эффективностям:

$E(G)={\frac {1}{N(N-1)}}\sum _{i\neq j\in V}{\frac {1}{d_{ij}}}$

где $N=|V|$ обозначает количество узлов в сети.

Расстояния можно измерять разными способами, в зависимости от типа сетей. Наиболее естественным расстоянием для невзвешенных сетей является длина кратчайшего пути между узлами. $i$ и $j$, то есть кратчайший путь между $i,j$ — путь с минимальным количеством ребер, а количество ребер — это его длина. Заметьте, что если $i=j$ затем $d_{ij}=0$— и именно поэтому приведенная выше сумма закончилась $i\neq j$— а если нет пути, соединяющего $i$ и $j$, $d_{ij}=\infty$ и их парная эффективность равна нулю. Существование $d_{ij}$ счет, для $i\neq j$ $d_{ij}\geq 1$ и так $E(G)$ ограничен между 0 и 1, т.е. является нормализованным дескриптором.

Взвешенные сети

Расстояние кратчайшего пути также можно обобщить на взвешенные сети, см. взвешенное расстояние кратчайшего пути , но в этом случае $d_{ij}^{W}\in [0,+\infty ]$ и средняя эффективность связи должна быть должным образом нормализована, чтобы быть сопоставимой между различными сетями.

В авторы предложили нормализовать $E(G)$ разделив его на эффективность идеализированной версии сети $G$:

$E_{\text{glob}}(G)={\frac {E(G)}{E(G^{\text{ideal}})}}.$

$G^{\text{ideal}}$ это «идеальный» график на $N$ узлы, в которых присутствуют все возможные ребра. В невзвешенном случае каждое ребро имеет унитарный вес, $G^{\text{ideal}}$ это клика , полная сеть, и $E(G^{\text{ideal}})=1$. Когда ребра взвешены, достаточное условие (для правильной нормализации, т.е. $E_{\text{glob}}(G)\in [0,1]$) о расстояниях в идеальной сети, называемой на этот раз $l_{ij}$, является

$l_{ij}\leq d_{ij}$

для $i,j=1,...,N$. $l_{ij}$ должно быть известно (и отличаться от нуля) для всех пар узлов. Обычно их выбирают как географические или физические расстояния в пространственных сетях. или как максимальная стоимость по всем ссылкам, например $l_{ij}={\frac {1}{w_{\max }}}$ где $w_{\max }$ указывает на максимальную силу взаимодействия в сети. Однако в авторы освещают проблемы такого выбора при работе с сетями реального мира, которые характеризуются неоднородной структурой и потоками. Например, выбирая $l_{ij}={\frac {1}{w_{\max }}}$ делает глобальную меру очень чувствительной к выбросам в распределении весов и имеет тенденцию недооценивать фактическую эффективность сети. Авторы также предлагают процедуру нормализации, т.е. способ построения $G^{\text{ideal}}$ используя всю и только информацию, содержащуюся в весах ребер (и никаких других метаданных, таких как географические расстояния), что является статистически надежным и физически обоснованным.

Эффективность и поведение в маленьком мире

Глобальная эффективность сети — это мера, сравнимая с $1/L$, а не просто средняя длина пути $L$ сам. Ключевое отличие состоит в том, что, хотя $1/L$ измеряет эффективность в системе, где через сеть передается только один пакет информации, $E_{\text{glob}}(G)$ измеряет эффективность параллельной связи, то есть когда все узлы одновременно обмениваются пакетами информации друг с другом.

Локальное среднее значение эффективности парной связи можно использовать в качестве альтернативы коэффициенту кластеризации сети. Локальная эффективность сети $G$ определяется как:

$E_{loc}(G,i)={\frac {1}{N}}\sum _{i\in G}E(G_{i})$

где $G_{i}$ — локальный подграф, состоящий только из узла $i$непосредственные соседи, но не узел $i$ сам.

Приложения

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

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

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