Градиентная сеть

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

Определение

Транспортировка осуществляется по фиксированной сети. $G=G(V,E)$ называется графом подложки. Он имеет N узлов, $V=\{0,1,...,N-1\}$ и наборкраев $E=\{(i,j)|i,j\in V\}$. Учитывая узел i , мы можем определить его набор соседей в G с помощью _Si ⁽¹⁾ = {j ∈ V | (i,j)€ E}.

Пример градиентной сети.

Давайте также рассмотрим скалярное поле h = { h ₀ , .., h _{N −1} }, определенное на множестве узлов V, так что каждый узел i имеет связанное с ним скалярное значение h _i .

Градиент ∇ h _i в сети : ∇ h _i $=$(я, ц(я)) т.е. направленное ребро от i до µ(i) , где µ ( i ) ∈ S _i ⁽¹⁾ ∪ {i}, а h _µ имеет максимальное значение в ${h_{j}|j\in S_{i}^{(1)}\cup {i}}$.

Градиентная сеть : ∇ $G=$ ∇ $G$ $(V,F)$где F множество ребер градиента на G. —

В общем, скалярное поле зависит от времени из-за потока, внешних источников и приемников в сети. Следовательно, градиентная сеть ∇ $G$ будет динамичным.

Мотивация и история

Концепция градиентной сети была впервые представлена ​​Торочкаем и Басслером (2004).

Как правило, сети реального мира (такие как графы цитирования , Интернет , клеточные метаболические сети, всемирная сеть аэропортов), которые часто развиваются в транспортные объекты, такие как информация, автомобили, электроэнергия, вода, силы и т. д., не являются глобальными. спроектирован; вместо этого они развиваются и растут посредством местных изменений. Например, если маршрутизатор в Интернете часто перегружен и из-за этого пакеты теряются или задерживаются, он будет заменен несколькими взаимосвязанными новыми маршрутизаторами.

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

Недавние исследования исследует связь между топологией сети и эффективностью транспортировки.

Градиент в узле i представляет собой направленное ребро, указывающее на наибольшее увеличение скалярного потенциала в окрестности узла.

Распределение градиентных сетей по степени

В градиентной сети степень входа узла i, k _i ^(в) — количество ребер градиента, указывающих на i, а распределение по степеням — $R(l)=P\{k_{i}^{(in)}=l\}$ .

Распределение степеней градиентной сети и подложки ( модель BA ).

Когда подложка G представляет собой случайный граф и каждая пара узлов соединена с вероятностью P (т. е. случайный граф Эрдёша – Реньи ), скаляры h _i являются iid (независимыми одинаково распределенными), точное выражение для R (l) определяется выражением

$R(l)={\frac {1}{N}}\sum _{n=0}^{N-1}\mathrm {C} _{l}^{N-1-n}[1-p(1-p)]^{N-1-n-l}[p(1-p)^{n}]^{l}]$

В пределе $N\to \infty$ и $P\to 0$, распределение степеней становится степенным законом

$R(l)\approx l^{-1}$

В этом пределе это показывает, что градиентная сеть случайной сети не имеет масштаба.

Более того, если сеть подложек G не имеет масштаба, как в модели Барабаши-Альберта , то градиентная сеть также подчиняется степенному закону с тем же показателем степени, что и у G.

Перегруженность сетей

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

Иллюстрация влияния структуры на потоки.

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

$J=1-\langle \langle {\frac {N_{\text{receive}}}{N_{\text{send}}}}\rangle _{h}\rangle _{\text{network}}=R(0)$

где N _{получения} — это количество узлов, которые получают градиентный поток, а N _{отправки} — это количество узлов, которые отправляют градиентный поток.Значение J находится между 0 и 1; $J=0$ означает отсутствие пробок и $J=1$ соответствует максимальной загруженности.В пределе $N\to \infty$, для случайного графа Эрдеша – Реньи коэффициент перегрузки принимает вид

$J(N,P)=1-{\frac {\ln N}{N\ln({\frac {1}{1-P}})}}\left[1+O({\frac {1}{N}})\right]\rightarrow 1.$

Этот результат показывает, что случайные сети максимально перегружены в этом пределе.Напротив, для безмасштабной сети J является константой для любого N , а это означает, что безмасштабные сети не склонны к максимальным помехам.

Рис.7. Коэффициент перегрузки для случайных графов и безмасштабных сетей.

Подходы к борьбе с перегрузками

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

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

Ана Л Пасторе и Пионтти и др. (2008) показали, что релаксационная динамика может уменьшить перегрузку сети.

Пан и др. (2011) изучали свойства помех в схеме, где ребрам присваиваются веса степени скалярной разности между потенциалами узлов.

Ниу и Пан (2016) показали, что перегрузку можно уменьшить, введя корреляцию между полем градиента и топологией локальной сети.

<n(k)> — среднее количество пакетов в зависимости от степени возможностей обработки пакетов: 0 (кружки), 0,05 (квадратики), 0,1 (звездочки).

Сравнение эффективного подхода (кружки) с расширенными возможностями верхних 3% узлов степени и обычного подхода (звездочки) с улучшенными возможностями всех узлов. (а) возможность обработки пакетов равна 0,05, (б) возможность обработки пакетов равна 0,1. <n(k)> — среднее число пакетов как функция степени.

См. также

• Сетевая динамика
• Топология сети
• Квантовая комплексная сеть