پیش‌نویس:شبکه‌ی گرادیان

در علم شبکه، شبکه‌ی گرادیان یک زیرشبکه‌ی جهت‌دار از یک شبکه‌ی "بستری (substrate)" است که هر گره یا راس یک پتانسیل نرده‌ای (عددی) و یک یال خروجی دارد که این یال به راسی با کم‌ترین (یا بیش‌ترین) پتانسیل در همسایگی خود، متشکل از خود آن راس و رئوس مجاور آن، متصل شده است.

تعاریف

انتقالات بر روی شبکه‌ی ثابت $G=G(V,E)$، که شبکه‌ی بستری نامیده می‌شود، صورت می‌گیرد. این شبکه از $N$ گره $V=\{0,1,...,N-1\}$ و مجموعه‌ای از یا‌ل‌ها $E=\{(i,j)\ |\ i,j\in V\}$ ساخته شده است. برای راس دل‌خواه $i$ می‌توان مجموعه‌ی رئوس مجاور در $G$ را به صورت $S_{i}^{(1)}=\{j\in V\ |\ (i,j)\in E\}$ تعریف نمود.

مثالی از یک شبکه‌ی گرادیان.

با تعریف میدان نرده‌ای $h=\{h_{0},\ h_{1},\ \dotsc ,\ h_{N-1}\}$ بر روی مجموعه رئوس $V$، به گونه‌ای که راس $i$ مقدار نرده‌ای $h_{i}$ را داشته باشد، تعاریف زیر را می‌توان انجام داد:

گرادیان $\nabla h_{i}$ بر روی شبکه: $\nabla h_{i}=(i,\mu (i))$

یالی جهت‌دار از راس $i$ به راس $\mu (i)$ که $\mu (i)=S_{i}^{(1)}\cup {i}$ بوده و $h_{\mu }$ بیش‌ترین مقدار را در $\{h_{j}\mid j\in S_{i}^{(1)}\cup \{i\}\}$ دارد.

شبکه‌ی گرادیان: $\nabla G=\nabla G(V,F)$

که در آن $F$ مجموعه‌ای از یال‌های گرادیان در $G$ است.

به طور کلی میدان نرده‌ای $h$ به دلیل وجود جریان‌ها، منابع (sources) و حفره‌های (sinks) خارجی، وابسته به زمان بوده و شبکه‌ی گرادیان $\nabla G$ دارای دینامیک است.

انگیزه و تاریخچه

مفهوم شبکه‌ی گرادیان در ابتدا توسط Toroczkai و Bassler در سال ۲۰۰۴ به عنوان مدلی برای توجیه مشاهده‌ی گسترده‌ی شبکه‌های بی‌مقیاس در طبیعت، شبکه‌های ارتباطات و شبکه‌های ساخت بشر معرفی شد.

به طور کلی، شبکه‌های دنیای واقعی (مانند شبکه‌ی استنادات علمی، اینترنت، شبکه‌ی متابولیکی، شبکه‌ی فرودگاهی در سراسر جهان) که اغلب برای انتقال موجودیت‌هایی همانند اطلاعات، اتومبیل، توان، آب، نیرو و غیره رشد و تکامل می‌یابند، به صورت غیرموضعی و جهانی طراحی نشده اند؛ در عوض آن‌ها از طریق تغییرات محلی و موضعی رشد کرده و تکامل می‌یابند. به عنوان مثال اگر یک روتر در اینترنت به طور مداوم شلوغ باشد و در نتیجه‌ی آن بسته‌های شبکه گم شده و یا با تاخیر روبرو شوند، آن روتر با چندین روتر جدید که به یک‌دیگر متصل هستند، جایگزین می‌شود.

علاوه بر این، این جریان موجودیت‌ها اغلب توسط گرادیان‌های محلی یک کمیت نرده‌ای ایجاد می‌شوند و یا تحت تأثیر قرار می‌گیرند. برای نمونه می‌توان جریان الکتریکی را مثال زد که توسط گرادیان پتانسیل الکتریکی ایجاد و هدایت می‌شود. در شبکه‌های اطلاعاتی، مشخصات راس‌ها باعث ایجاد جهت‌گیری در نحوه انتقال اطلاعات از یک راس به رئوس مجاور آن می‌شود. این ایده، انگیزه‌‌ی مطالعه‌ی بازدهی جریان بر روی شبکه، با رویکرد استفاده از شبکه‌های گرادیان در حالتی که جریان توسط گرادیان‌های یک میدان نرده‌ای توزیع شده در شبکه هدایت شود است.

تحقیقات اخیر ارتباط میان توپولوژی شبکه و بازدهی جریان انتقالات را مورد بررسی قرار داده اند.

گرادیان در راس $i$ یک یال جهت‌دار به سمت بیش‌ترین افزایش پتانسیل نرده‌ای در مجاورت و همسایگی آن است.

توزیع درجات ورودی شبکه‌های گرادیان

در یک شبکه گرادیان، درجه‌ی ورودی راس $i$، $k_{i}^{\text{(in)}}$، تعداد یال‌های گرادیانی است که به راس $i$ اشاره می‌کنند و از این رو توزیع درجه‌ی ورودی نیز برابر با $R(l)=P\{k_{i}^{(in)}=l\}$ خواهد بود.

شبکه‌ی تصادفی

هنگامی که شبکه‌ی بستری $G$ یک گراف تصادفی که هر جفت راس آن با احتمال $p$ به یک‌دیگر متصل بوده (مدل اردوش-رینی برای گراف تصادفی) و مقادیر نرد‌ه‌ای $h_{i}$ نیز به صورت i.i.d (متغیر‌های تصادفی مستقل با توزیع یکسان) باشند، عبارت دقیق برای $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$، برای $0<l\leq z$ توزیع درجه ورودی توانی می‌شود:

توزیع درجه ورودی شبکه‌ی گرادیان و شبکه‌ی بستری آن (مدل G(N, p)).

$R(l)\simeq {\frac {1}{zl}}$

این نشان می‌دهد که در این حد، شبکه‌ی گرادیان شبکه‌ی تصادفی، بدون مقیاس است.

شبکه‌ی بی‌مقیاس

علاوه بر این، اگر شبکه بستری $G$ بدون مقیاس باشد، همانند مدل باراباسی-آلبرت، شبکه‌ی گرادیان نیز از توزیع توانی با توانی مشابه با $G$ پیروی می‌کند.

توزیع درجه ورودی شبکه‌ی گرادیان و شبکه‌ی بستری آن (مدل BA).

ازدحام در شبکه‌ها

این واقعیت که توپولوژی شبکه‌ی بستری بر سطح ازدحام شبکه تأثیر می گذارد را می‌توان با یک مثال ساده نشان داد: اگر شبکه ساختار ستاره‌ای داشته باشد، جریان در راس مرکزی بسیار پر ازدحام می‌شود، زیرا راس مرکزی باید تمام جریان‌های آمده از راس‌های دیگر را مدیریت کند. با این حال اگر شبکه ساختار حلقه مانند داشته باشد، از آنجایی که هر راس نقش یکسانی را ایفا می‌کند، ازدحامی ایجاد نمی‌شود.

نمایش تاثیر ساختار بر جریان‌ها

با فرض آن که جریان توسط گرادیان‌ میدان نرده‌ای در شبکه ایجاد می‌شود، بازدهی جریان در شبکه‌ها را می‌توان از طریق ضریب ازدحام مشخص کرد که به شرح زیر تعریف می‌شود:

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

که در آن $N_{\text{receive}}$ تعداد راس‌هایی است که جریان گرادیان را دریافت و $N_{\text{send}}$ تعداد راس‌هایی است که جریان گرادیان را ارسال می کنند. مقدار $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$ ها مقداری ثابت داشته و مستقل از اندازه‌ی شبکه است، به این معنی که شبکه‌های بدون مقیاس مستعد ازدحام حداکثری نیستند.

مقایسه‌ی ضریب ازدحام برای شبکه‌های تصادفی و شبکه‌های بدون مقیاس.

همچنین ببینید

• توپولوژی شبکه