پیش‌نویس:مدل شبکه سلسله مراتبی

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

مفهوم

مدل شبکه سلسله مراتبی بخشی از خانواده مدل بدون مقیاس است که در ویژگی اصلی این مدل یعنی به اشتراک گذاشتن هاب های بیشتر در بین گره ها نسبت به تولید تصادفی مشترک است. با این حال، به طور قابل توجهی با سایر مدل های مشابه ( باراباسی-آلبرت ، واتس- استروگاتز ) در توزیع ضرایب خوشگی گره ها متفاوت است: همانطور که مدل‌های دیگر یک ضریب خوشگی ثابت را به عنوان تابعی از درجه گره پیش‌بینی می‌کنند، در مدل‌های سلسله مراتبی انتظار می‌رود که گره‌هایی با یال های بیشتر ضریب خوشگی پایین‌تری داشته باشند. علاوه بر این، در حالی که مدل Barabási-Albert کاهش میانگین ضریب خوشگی را با افزایش تعداد گره‌ها پیش‌بینی می‌کند، در مورد مدل‌های سلسله مراتبی هیچ رابطه‌ای بین اندازه شبکه و میانگین ضریب خوشگی آن وجود ندارد.

توسعه مدل‌های شبکه سلسله مراتبی عمدتاً ناشی از شکست سایر مدل‌های بدون مقیاس در ترکیب ساختار بدون مقیاس و خوشه‌بندی بالا در یک مدل واحد بود. از آنجایی که چندین شبکه واقعی ( شبکه‌های متابولیک ، شبکه تعامل پروتئین ، شبکه جهانی وب یا برخی شبکه‌های اجتماعی ) چنین ویژگی‌هایی را نشان می‌دهند، توپولوژی‌های سلسله مراتبی مختلفی به منظور توضیح این ویژگی‌های مختلف معرفی شدند.

الگوریتم

مدل‌های شبکه سلسله مراتبی معمولاً به روش تکرار شونده و با تکرار خوشه اولیه شبکه بر اساس یک قانون خاص بدست می آیند. به عنوان مثال، یک شبکه اولیه از پنج گره کاملاً به هم پیوسته را در نظر بگیرید (N=5). در مرحله بعد، چهار ماکت از این خوشه ایجاد کنید و گره های محیطی هر ماکت را به گره مرکزی خوشه اصلی متصل کنید (N=25). این مرحله می تواند به طور نامحدود تکرار شود، بنابراین برای هر k مرحله، تعداد گره های سیستم را می توان با N=5 ^k+1 به دست آورد.

البته چندین روش مختلف برای ایجاد سیستم های سلسله مراتبی پیشنهاد شده است. این سیستم ها به طور کلی در ساختار خوشه اولیه و همچنین در درجه گسترش که اغلب به عنوان ضریب تکرار مدل از آن یاد می شود، متفاوت هستند.

نمونه ای از ساختار شبکه سلسله مراتبی.

ویژگی‌ها

توزیع درجه

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

$P\left(k\right)\sim ck^{-\gamma }\,$

که در آن c یک عدد ثابت است و γ درجه توانی می باشد. در بیشتر شبکه‌های دنیای واقعی که ویژگی‌های بدون مقیاس را نشان می‌دهند γ در بازه [2،3] قرار دارد.

برای مدل های سلسله مراتبی نشان داده شده است که توان درجه تابع توزیع را می توان به صورت زیر بدست آورد.

$\gamma =1+{\frac {\ln M}{\ln(M-1)}}$

که M در آن نشان دهنده ضریب تکرار مدل است.

ضریب خوشگی

برخلاف سایر مدل‌های بدون مقیاس ( Erdős–Rényi ، Barabási–Albert، Watts–Strogatz) که در آن ضریب خوشگی مستقل از درجه یک گره خاص است، در شبکه‌های سلسله مراتبی ضریب خوشگی را می‌توان به عنوان تابعی از درجه به صورت زیر نوشت:

$C\left(k\right)\sim k^{-\beta }\,$

نشان داده شده است که در شبکه های بدون مقیاس تعینی، توان β مقدار 1 را می گیرد

مثال ها

شبکه بازیگر

بر اساس داده های بازیگران موجود در سایت imdb شبکه توسط بازیگران هالیوودی تعریف می‌شود که اگر هر دو در یک فیلم ظاهر شوند به یکدیگر متصل هستند و در نتیجه مجموعه داده‌ای از 392340 گره و 15347957 یال ایجاد می‌شود. همانطور که مطالعات قبلی نشان داده است، این شبکه حداقل برای مقادیر بالای k ویژگی های بدون مقیاس را نشان می دهد. علاوه بر این، به نظر می رسد ضرایب خوشگی از قانون مقیاس بندی مورد نیاز با پارامتر -1 پیروی می کنند که شواهدی برای توپولوژی سلسله مراتبی شبکه ارائه می دهد. به طور شهودی، بازیگران تک‌بازی بنا به تعریف ضریب خوشگی یک دارند در حالی که بازیگرانی که در چندین فیلم بازی می‌کنند بسیار بعید است که با یک گروه کار کنند که به طور کلی با افزایش تعداد بازیگران همکار، ضریب خوشگی کاهش می‌یابد.

شبکه زبان

اگر معیارهای پیوند بین کلمات را مشخص کنیم حتی کلمات را هم می‌توان به عنوان شبکه در نظر گرفت.

تعریف پیوندها به عنوان ظاهر شدن به عنوان هم معنی در فرهنگ لغت مریام وبستر، یک شبکه از 182853 گره با 317658 یال می‌سازد. همانطور که مشخص شد، شبکه کلمات به‌دست‌آمده از قانون توان در توزیع درجه پیروی می‌کند این در حالی است که توزیع ضریب خوشگی نشان می‌دهد که شبکه بنیادین از ساختار سلسله مراتبی با γ =3.25 و β =1 پیروی می‌کند.

شبکه صفحات وب

با نگاشت دامنه www.nd.edu، شبکه ای از 325729 گره و 1497135 یال به دست آمد که توزیع درجه آن از قانون توانی با Yout = 2.45 و Yin = 2.1 برای درجه های خارج و داخل پیروی می کند. شواهد برای توزیع قانون مقیاس بندی ضرایب خوشه بندی به طور قابل توجهی ضعیف تر از موارد قبلی است، اگرچه یک الگوی کاهشی به وضوح در توزیع ضریب خوشگی قابل مشاهده است که نشان می‌دهد هر چه یک دامنه پیوند های بیشتری داشته باشد آن پیوندها کمتر به هم لینک داده می شوند.

شبکه دامنه

شبکه دامنه ، یعنی اینترنت در سطح سیستم خودگردان (AS) که دامنه های ادمین در صورتی به هم متصل در نظر گرفته می‌شوند که یک روتر آن‌ها را به هم متصل کند. شامل 65520 گره و 24412 یال بین آنها است و ویژگی های یک شبکه بدون مقیاس را نشان می دهد.

نمونه ضرایب خوشگی توسط تابع C(k)~k^−0.75 برازش شد که توان آن (به صورت مطلق) تا حدودی کوچکتر از پارامتر نظری برای شبکه‌های بدون مقیاس تعینی است.