بالانس تئوری،مدل باراباشی-آلبرت، تولی و تبری!

در پست قبل در مورد بالانس تئوری یا نظریه توازن صحبت کردیم و نشون دادیم که به کمک یک مدل ساده و ابتدایی می‌تونیم به جوامع، متناسب با نوع رابطه‌ی اعضا با همدیگه، انرژی نسبت بدیم و مقدار این انرژی به ما میگه که جامعه مد نظر در چه وضعیتی از توازن قرار داره.

 یک شبکه نامتوازن بین آلیس، باب و کرول.دوستی با خط و دشمنی با خط‌چین مشخص شده است.

یک شبکه نامتوازن بین آلیس، باب و کرول.دوستی با خط و دشمنی با خط‌چین مشخص شده است.

بنابر بهنجارش، اگر انرژی جامعه‌ ۱- به‌دست بیاد، جامعه کاملا متوازن یا بالانس هست که این در صورتی رخ میده که همه اعضای جامعه دوست همدیگه باشند و یا اینکه جامعه دو قطبی بشه، یعنی جامعه به دو زیر مجموعه تقسیم بشه به نحوی که درون زیرمجوعه‌ها اعضا دوست باشند اما هر عضوی از این زیرمجوعه با اعضای زیرمجوعه‌ی مقابل دشمن باشه. همین‌طور اگر انرژی جامعه بیشتر از ۱- به‌دست بیاد یعنی جامعه نامتوازن‌ هست و هر چقدر که انرژی به ۱+ (کران بالای انرژی بنابر بهنجارش) نزدیک‌تر باشه جامعه نامتوازن‌تر هست که به معنی وجود امکان نزاع و درگیری در بین اعضاست.

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

همه‌ی ما گزاره‌های این شکلی رو زیاد شنیدم: «پول، پول میاره» یا «ثروتنمندان، ثروتمندتر میشند و فقرا فقیرتر».  بد نیست بدونید که جامعه‌شناسان به این پدیده می‌گند اثر متیو (Matthew Effect). ماجرا از اینجا شروع میشه که درون شبکه‌هایی مثل وب(www)، اینترنت، شبکه استناد (citation networks) و شبکه‌های اجتماعی  اعضایی وجود دارند که علی‌رغم تعداد کمشون، توجه زیادی از شبکه رو به خودشون معطوف می‌کنند.

 

توزیع قاون‌توانی، قسمت سبز رنگ ۸۰٪ از شبکه را شامل می‌شود و دم‌دراز زرد رنگ ۲۰٪ باقی‌مونده را.

توزیع قاون‌توانی، قسمت سبز رنگ ۸۰٪ از شبکه را شامل می‌شود و دم‌دراز زرد رنگ ۲۰٪ باقی‌مانده را.

به عنوان مثال در بین تمام سایت‌ها گوگل، ویکی‌پدیا و فیس‌بوک بیشترین بازدیدکننده‌ها و پیوندها رو دارند یا مثلا در جامعه‌ی ما، محمدرضا شجریان، حسین علیزاده و کیهان کلهر  جزو برجسته‌ترین هنرمندان موسیقی سنتی هستند، در مقایسه با جمعیت هنرمندان موسیقی، این افراد تعدادشون کمه. با این‌وجود شهرت و محبوبیشون از همه هنرمندان بیشتره. این شبکه‌ها، شبکه‌های بی‌مقیاس (scale-free) هستند به این معنی که توزیع درجه در این شبکه‌ها با تقریب خوبی از یک الگوی قانون‌توانی(power law) پیروی می‌کنه. این چندتا جمله‌ی سخت که گفتم یعنی اینکه وقتی ما این شبکه‌ها رو با یک گراف نمایش می‌دیم، درجه ‌رئوس متناسب با وارون فراوانی(تعداد) اون رئوس هست . یعنی هرچی راسی درجه‌ش بیشتر باشه (تعداد یال‌های بیشتری بهش متصل بشند) فراوانیش کمتره و هر چقدر درجه راسی کم‌تر باشه فراوانیش بیشتره! همون‌جوری که تعداد سایت‌هایی مثل گوگل تعدادشون خیلی کمه، چون درجه‌شون زیاده.

رشد یک شبکه مطابق با مدل باراباشی-آلبرت که در هر مرحله راس جدید به ۲ راس قبلی وصل می‌شود.

کار آلبرت باراباشی و رکا آلبرت معرفی الگوریتمی بود که قادره چنین شبکه‌هایی رو مدل‌سازی کنه. این الگوریتم صرف‌نظر از تصادفی بودن باید گرافی رو تولید کنه که توزیع درجه‌ رئوسش قانون‌توانی باشه. برای همین اساس این مدل دو چیزه: ۱) رشد: در طی زمان رئوس جدیدی به شبکه اضافه می‌شند. ۲) اتصال ترجیحی: رئوس جدید ترجیح می‌دند به رئوسی وصل بشند که درجه‌ی بالاتری دارند (هر کسی دوست داره به کسی وصل بشه که قدرت بیشتری داره!). برای همین این الگوریتم ابتدا یک شبکه متصل (همبند) با m_0 راس ایجاد می‌کنه. بعد از اون، در هر مرحله، راسی اضافه می‌شه و به m \le m_0 راس قبلی وصل میشه. این راس بر اساس درجه‌شون انتخاب می‌شند: یعنی احتمال اینکه راس جدید به iامین راس موجود درگراف وصل بشه برابره با نسبت درجه راس iام به مجموع درجات کل رئوس. این سبب میشه که «هاب» در شبکه به‌وجود بیاد. هاب‌ها رئوسی هستند که درجه‌ شون از بقیه رئوس شبکه بیشتره. (شجریان یک هاب به حساب میاد در بین خواننده‌ها همون‌جوری که گوگل یک هابه در بین سایت‌ها!). يادتون باشه که در مدل باراباشی-آلبرت وزن هر یال ۱ است!

 

خیلی خب، الان وقتشه که بریم سراغ کاری که می‌خواستیم انجام بدیم. جامعه‌ای رو فرض کنید با جمعیت m_0 که اعضای اون با احتمال p دوست هم باشند. این جامعه مطابق با پست قبل توسط یک گراف کامل مدل میشه که انرژی شبکه برابر با تفاضل تعداد مثلث‌های متوزان با مثلث‌های نامتوازن تقسیم بر تعداد کل مثلثهاست. حالا فرد جدیدی وارد این جامعه میشه و این شخص ترجیح میده با کسایی دوست بشه که محبوبیت بیشتری در جامعه دارند (اتصال ترجیحی). به این معنی که کسایی که دوستای بیشتر و دشمنای کمتری دارند گزینه‌های بهتری هستند برای دوست شدن. برای همین ما به هر راس یک انرژی نسبت می‌دیم به این صورت که اگر راسی fتا دوست و eتا دشمن داشته باشه، انرژی اون راس برابر با  e – f هست.

نمایش جامعه‌ای ده نفری که در آن دوستی با خط و دشمنی با خط‌چین مشخص شده‌ است.

نمایش جامعه‌ای ده نفری که در آن دوستی با خط و دشمنی با خط‌چین مشخص شده‌ است.

پس رئوسی که -طبق تعریف- انرژی کم‌تری دارند گزینه‌های بهتری هستند برای دوستی. فرد جدید به صورت تصادفی با محبوب‌ترین فرد، یعنی راسی که کمترین انرژی رو داره دوست میشه. همون جوری که توی پست قبلی دیدید، دوستی بین دو نفر وقتی محکم‌تر میشه که با دوستای هم دوست و با دشمنای هم دشمن بشند(اصل تولی و تبری!). بنابراین شخص تازه‌وارد بعد از دوست شدن با محبوب‌ترین فرد جامعه، به صورت تصادفی سعی می‌کنه با حداکثر j تا از دوستای با کمترین انرژی فرد محبوب دوست و حداکثر با k تا از دشمنای با بیشترین انرژی اون دشمن بشه. بنابراین افراد تازه‌وارد در شبکه، نوع رابطه‌شون رو بر اساس انرژی، که مبین محبوبیت در جامعه هست تنظیم میکنند. در نتیجه افراد قبل از برقراری ارتباط چک می‌کنند تا با افرادی که انرژی کمتری دارند دوست و با کسانی که انرژی بیشتری دارند دشمن بشند. ما می‌خوایم ببینیم که بعد اضافه شدن m تا راس به این شبکه انرژی شبکه چه جوری تغییر می‌کنه. از اونجایی که بعد از اضافه شدن رئوس دیگه گراف ما کامل نیست (بعضی‌ها دیگه با هم هیچ نوع رابطه‌ای ندارند) ممکنه این پرسش به ذهنتون برسه که خب انرژی رو چه جوری حساب کنیم؟! درسته که بعضی از رئوس تشکیل مثلث نمی‌دند، با این وجود، مجددا، طبق تعریف، انرژی شبکه برابر با تفاضل تعداد مثلث‌های متوزان با مثلث‌های نامتوازن تقسیم بر تعداد کل مثلثهاست.

کاری که ما به کمک چندخط (نزدیک به ۲۰۰خط) برنامه‌نویسی يا پایتون انجام دادیم اینه که یک جامعه ۱۰ نفری رو به ۱۰۰ نفر رسوندیم و با توجه به توضیحاتی که دادم، در نهایت انرژی شبکه، توزیع درجه رئوس و چیزایی که نیاز داشتیم رو حساب کردیم.

نمایش جامعه‌ای ۱۰۰ نفری پس از رشد و اتصال ترجیحی - دوستی با خط و دشمنی با خط‌چین مشخص شده‌ است. شمال شرقی شبکه متراکم‌تر است!

نمایش جامعه‌ای ۱۰۰ نفری پس از رشد و اتصال ترجیحی – دوستی با خط و دشمنی با خط‌چین مشخص شده‌ است. شمال شرقی شبکه متراکم‌تر است!

ما ۱۰۰ حالت ممکن رو به عنوان شرایط اولیه تست کردیم، به این صورت که۱۰۰ جامعه ۱۰ نفری درست کردیم که هر جامعه احتمال اینکه اعضاش در ابتدا با همدیگه دوست (و متعاقبا دشمن) باشند متفاوت بوده. احتمالی که به جامعه‌ iام نسبت دادیم، برابر با (۱۰۰- i)٪ ، بوده. بنابراین ما مسئله رو برای ۱۰۰ حالت از شرایط اولیه مختلف حل کردیم. از شرایط مرزی مسئله اینه که هر مرتبه که راسی اضافه میشه، بعد از دوست شدن با محبوب‌ترین فرد، با چندتا از دوستای اون دوست و با چند تا از دشمنای اون دشمن میشه یا به عبارتی مقدار j و k چنده؟ (نگاه کنید به توضیحات بالا). به خاطر توان محاسباتی کامپویترهامون، ما تونسیتم این شرایط رو آزمایش کنیم:

$$\left ( j,k \right )= \left \{ (3,3),(3,4),(4,3),(4,2),(2,4),(4,0),(0,4),(8,0),(0,8) \right \}$$

منظور از (j , k) شرایطیه که فرد تازه وارد به طور تصادفی، حداکثر با j نفر از دوستان با انرژی کم‌تر فرد محبوب که برای دوستی انتخاب شده، دوست و حداکثر با k نفر از دشمنان با انرژی بالا فرد محبوب دشمن بشه. مجموعه بالا هم حالت‌هایی هست که ما زورمون رسید و انجام دادیم. از اونجایی که آزمایش ما پر از فرایند‌های تصادفی هست، هر آزمایش رو ۱۰ مرتبه تکرار کردیم. ما دنبال این بودیم که ببینم چه بلایی بر سر توازن جامعه بعد از رشد و اتصال ترجیحی میاد. برای همین چیزی که گزارش شده، نسبت‌ جواب‌هایی هست که انرژی شبکه‌ کاهش پیدا کرده به کل جواب‌ها در هر آزمایش پس از رشد و اتصال ترجیحیه! به عبارت دیگه، ما ۱۰۰ جامعه رو با شرایط مرزی متفاوت، هر کدوم رو ۱۰ مرتبه، در بوته‌ی آزمایش قرار دادیم و با توجه به اینکه بعد از این آزمایش‌ها چقدر جوامع ما به سمت بالانس شدند  پیش‌رفتند، نمودارهای زیر رو رسم  کردیم:

۱) تعداد دوست بیشتر از دشمن(j> k) :

تعداد دوست بیشتر از تعداد دشمن

تعداد دوست بیشتر از تعداد دشمن (j> k)

چیزی که مشاهده میشه اینه که هر چی j بزرگ‌تر از k باشه، به عبارتی j-k هر چقدر بزرگ‌تر باشه شبکه شانس بیشتری برای کاهش انرژی داره!

۲) تعداد دوست برابر با دشمن(j = k) :

3f 3e

تعداد دوست برابر با دشمن(j = k)

با توجه به نمودار قبل و این نمودار، جوامعی که در ابتدا دوستی و دشمنی با احتمال تقریبا برابری توزیع شده، شانس بیشتری برای رفتن به سمت توازن دارند.

۲) تعداد دوست کم‌تر از دشمن(j  < k) :

 

تعداد دوست کم‌تر از دشمن (j<k)

تعداد دوست کم‌تر از دشمن (j<k)

مجددا نتیجه‌ی قسمت اول، j-k هر چقدر کوچک‌تر باشه شبکه شانس کم‌تری برای رسیدن به انرژی کم‌تر داره! در دو نمودار بالا که j=0  می‌بینیم هیچ کدوم از جوامع شانس متوازن شدن رو ندارند! همین طور در شبکه‌ پایین-چپ که j=2 و k=4 با اینکه جوامع شانس بیشتری نسبت به j=0 برای کاهش انرژی دارند با این وجود، هیچ کدوم از جوامع ۱۰۰٪ این شانس رو ندارند. در نهایت در شبکه‌ پایین-راست  j=3 و k=4  امیدی برای شبکه‌ها وجود داره که کاملا به انرژی کم‌تری برسند!

از اونجایی که مدل ما هم شامل رشد و  اتصال ترجیحی است باید خاصیب بی‌مقیاسی از خودش نشون بده، به عبارت دیگه توزیع درجه رئوس در گراف جامعه ما باید قانون‌توانی باشه. در پایان نمودار درجه راس برحسب فراوانی برای جامعه‌ای که ابتدا ۱۰ نفر داشته و در نهایت به ۵۰۰ نفر رسیده با شرط مرزی j=k=3 رو مشاهده ‌می‌کنید:

۴۰٪ جمعیت اولیه دوست یکدیگرند

۴۰٪ جمعیت اولیه دوست یکدیگرند

۶۰٪ جمعیت اولیه دوست یکدیگرند

۶۰٪ جمعیت اولیه دوست یکدیگرند

5 comments

  1. سلام خدمت آقای کریمی
    من بهمن هستم دانشجو برق قدرت میخواستم با شما همکاری کنم

  2. سلام دوست عزیز،
    از طریق سری مقالات فراکتال ها با این بلاگ آشنا شدم. واقعا از مطالبش لذت بردم. دست مریزاد
    کار خوبتون رو ادامه بدید 😉

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

This site uses Akismet to reduce spam. Learn how your comment data is processed.