رفتن به نوشته‌ها

برچسب: استیون استروگاتز

«بیست سال علم شبکه»

این نوشته ترجمه‌ای تقریبا وفادار از مقاله منتشر شده در Nature News and Views توسط Alessandro Vespignani به مناسبت تولد ۲۰ سالگی شبکه‌های جهان-کوچک است.
این نوشته اشاره‌ی مستقیمی دارد به مقاله منتشر شده در Nature News and Views توسط Alessandro Vespignani به مناسبت تولد ۲۰ سالگی شبکه‌های جهان-کوچک است.

«این ایده که هرکس در دنیا به هرکس دیگری تنها با ۶ درجه جدایی متصل است، ۲۰ سال پیش توسط مدل شبکه‌ «جهان کوچک» توضیح داده شد. چیزی که به نظر می‌رسید کاربرد خاصی داشته باشد تبدیل به یافته‌ای با نتایج فراوان شد.» الساندرو وسپینانی

ماجرا از این‌جا شروع شد که اواخر بهار سال ۱۹۹۸، واتس و استروگتز مقاله‌ای منتشر کردن به اسم «دینامیک جمعی شبکه‌های جهان-کوچک» که در اون مقاله مدلی معرفی شد که «خوشگی» و «فاصله کوتاه بین رئوس» شبکه‌هایی که در زندگی واقعی پیدا میشن رو توصیف می‌کرد. خب، اون اوایل این مدل یه جوری جالب به‌نظر می‌رسید. ولی صرفا به عنوان یک خروجی یا تعمیمی از شبکه‌های منظمی که فیزیک‌دونای آماری و ماده‌چگالی‌ها بهشون عادت داشتن. [در حقیقت تا ۲۰ سال پیش، منظور ما از شبکه توی فیزیک، گراف‌های منظم توری شکلی بودن که بهشون lattice می‌گفتیم و نه network.] اما با گذر زمان، هر چی که دانشمندان رشته‌های مختلفی از این مدل استفاده کردند، پیامد‌های عمیق این مدل بیشتر آشکار شد. به این معنی که درک ما از رفتارهای دینامیکی و گذار فازهایی که توی پدیده‌های روزمره‌ مشاهده می‌کردیم به طور جدی بهتر شد. از فرایندهای واگیری گرفته تا انتشار اطلاعات! به زودی مشخص شد که این مقاله دوران جدیدی از پژوهش رو ایجاد کرده که نهایتا منجر به شکل‌گیری «علم شبکه» به عنوان یک رشته «چندرشته‌ای» شد!

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

این رفتار لگاریتمی به معنی جهان‌-کوچک بودن هست. همون ایده‌ای که در دنیا هر نفر حداکثر با ۶ تا واسطه به هرکس دیگه‌ای می‌تونه برسه. یعنی آهنگ بزرگ شدن فاصله بین هر دو راس در یک شبکه تصادفی کمتر از آهنگ بزرگ شدن اندازه اون شبکه است. (این رابطه خطی نیست، با دو برابر کردن L ،N دو برابر نمیشه!).

پروفایل چگونگی تغییر متوسط طول کوتاه‌ترین مسیرین بین دو راس در شبکه‌هایی با تپولوژی متفاوت. نگاره از کتاب علم شبکه باراباشی

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

سازوکار ایجاد یک شبکه جهان کوچک در مدل واتس-استروگتز با اضافه کردن بی‌نظمی به یک شبکه منظم. نگاره برگرفته از مقاله اصلی ۱۹۹۸

می‌دونیم که شبکه‌های منظم، دارای ضریب خوشگی بالایی هستن و شبکه‌های تصادفی دارای خاصیت نزدیک بودن اعضا به هم! چیزی که یک شبکه جهان-کوچک واقعی نیاز داره هر دوی این ویژگی‌هاست! واتس و استروگتز برای این‌که این دوگانگی رو برطرف کنند پیشنهاد مدلی رو دادن که ابتدا یک شبکه منظم با ضریب خوشگی بالا رو ایجاد کنه و بعد از اون، با احتمال p، یال‌ها رو بین رئوس اصطلاحا بُر بزنه! یعنی برای این‌ کار، از یک شبکه منظم، هر یال رو با احتمال p انتخاب می‌کنید و دو سرش رو به رئوس متفاوتی وصل می‌کنید! به این کار اصطلاحا سیم‌بندی گفته می‌شه و اگر این سیم‌بندی به طور تصادفی انجام بشه، اصطلاحا گفته میشه که یال‌های شبکه رو بُر می‌زنیم! بنابراین با تغییر مقدار می‌تونیم شبکه رو از حالت منظم  (p → 0) به حالت تصادفی (p → 1) تبدیل کنیم.

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

وجود میان‌برهای قرمز، به یک شبکه با ضریب‌خوشگی بالا، خاصیت جهان کوچکی می‌بخشد. نگاره از nature

مدل واتس و استروگتز ابتدا به عنوانی مدلی که «شش درجه جدایی» رو توصیف می‌کرد، در نظر گرفته می‌شد. اما در حقیقت مهم‌ترین تاثیرش هموار کردن مسیر مطالعه اثرات ساختار شبکه روی طیف وسیعی از پدیده‌های دینامیکی بود. یک سال پس از انتشار مقاله شبکه‌های جهان-کوچک، آلبرت باراباشی و رِکا آلبرت در مقاله‌ای با عنوان «برآمدگی اثر مقیاسی در شبکه‌های تصادفی» مدلی معروف به مدل شبکه «اتصال ترجیحی‌» رو منتشر کردن که نقش بسیار کلیدی در توسعه پژوهش در نظریه شبکه‌های پیچیده ایفا کرد. در نظریه گراف یا علم شبکه، به تعداد یال‌های متصل به هر راس، درجه اون راس گفته می‌شه و برای شبکه تصادفی، توزیع درجات رئوس، پواسونی هست. ایده مدل باراباشی-آلبرت این بود که توزیع درجات شبکه‌های واقعی، پواسونی نیست بلکه یک توزیع دم‌کلفت (توانی) هست. برای همین باراباشی و آلبرت سازوکاری رو معرفی کردن که به کمکش بشه شبکه‌هایی با توزیع درجات توانی داشت. این که درجات یک شبکه از توزیعی توانی میاد، به معنای وجود پدیده‌هایی نادر ولی مهمه! مثلا تعداد کسانی که توی اینستاگرام بالای ۱۰۰میلیون دنبال‌کننده دارن ۱۰ نفر هست ولی این‌ها افراد سرشناسی هستن! یا مثلا وقتی گفته میشه که در امریکا ۹۹٪ ثروت دست ۱٪ افراد جامعه است، درسته که این ۱٪ تعداد کمی از افراد جامعه امریکا رو تشکیل می‌دن ولی افراد بسیار تاثیرگذاری هستن! از اونجایی که در شبکه‌های جهان-کوچک و شبکه‌هایی که توزیع درجات ناهمگنی دارن طیف وسیعی از گذارفازها و رفتارهای برآمده رو میشه مشاهده کرد، رفته‌رفته دانشمندان زیادی از رشته‌های مختلف به این موضوع علاقمند شدن.

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

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

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

نکته‌ای که حتما باید بهش اشاره کنیم اینه که جمع‌آوری دانش و روش از رشته‌های کاملا مختلفی مثل علوم اجتماعی، ریاضیات کاربردی، فیزیک، زیست‌شناسی و علوم کامپیوتر واقعا کار آسونی نبوده! سال‌ها جنگ و جدل به خاطر توافق بر سر تعاریف و مفاهیم بوده و واقعا انرژی زیادی صرف شده تا رهیافت‌هایی که مردم در رشته‌های مختلف به کار بردن برای بقیه هم واضح بشه! ولی ما این کار رو انجام دادیم! طی ۲۰ سال گذشته، یک جامعه پرجوش و خروشی از علم شبکه ایجاد شده که برای خودش مجلات معتبر، موسسات تحقیقاتی و کنفرانس‌هایی با هزاران دانشمند داره!

در ۲۰امین سالگرد انتشار مقاله واتس و استروگتز، بیتشر از ۱۸۰۰۰ مقاله به این مدل که یکی از نمادهای تپولوژی شبکه‌ است ارجاع دادن. واتس و استروگتز مقاله‌شون رو با این جمله تموم می‌کنن که «امیدواریم که کار ما انگیزه‌بخش مطالعات بیشتر شبکه‌های جهان-کوچک بشه!» شاید در بستر تاریخ، هیچ گزاره‌ای اینقدر پیشگویانه نبوده باشه!

این ویدیو در مورد ظهور علم شبکه است:

بالانس تئوری چی میگه؟! (مقدمه)

این اولین پستیه که قراره در مورد چیزایی حرف بزنم که کسی در موردش زیاد نشنیده و نخونده. یک موضوع جدید و در حال توسعه که به نظرم به شدت جذابه. خب یک سری مشکلات هست توی این پست از جمله اینکه خیلی از عبارت‌ها رو «من» ترجمه کردم و هنوز ترجمه‌ی رسمی براشون ارائه نشده و یا اینکه لااقل هنوز عرف نشدند. ممکنه یک سری ایراد علمی هم وارد بشه که در آینده تصحیحشون می‌کنم. موضوع این پست Balance Theory هست، اما از اونجایی که اگر «نظریه تعادل» ترجمه بشه خیلی‌ها ممکنه در نگاه اول یاد تعادل نش یا نظریه تعادل عمومی بیفتند من به جای واژه‌ی «تعادل» از واژه‌ی «توازن» استفاده می‌کنم تا اطلاع ثانوی! درضمن مدلی که در ادامه مطرح میشه یک مدل ساده و ابتدایی هست، بنابراین احتمالا بعضی از سوال‌های شما رو در حوزه‌ی علوم اجتماعی و/یا علوم سیاسی بی‌جواب میذاره!

خیلی خب، سه‌ نفر رو فرض کنید که می‌تونند دوست یا دشمن همدیگه باشند. همین‌طور دوستی و دشمنی رو متقابل فرض کنید، یعنی اگر کسی رو دوست دارید، اونم شما رو دوست داره. حالا اگر این سه نفر دوست هم باشند، اون موقع همه چیز خوبه و تنشی پیش نمیاد؛ دوست دوست شما، دوست شماست! اصطلاحا میگیم این مجموعه‌ سه نفری در توازن قرار داره و یا اینکه متوازن -balanced- هست. اما اگر از بین این سه نفر دو نفر رابطه‌ی خوبی با همدیگه نداشته باشند اون‌موقع ممکنه تنش پیش بیاد. به عنوان مثال فرض کنید که شما، همسرتون و مادرتون رو دوست دارید با این وجود، متاسفانه، مادرتون و همسرتون رابطه‌ی خوبی با همدیگه ندارند.

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

اجازه بدید ،از این به بعد، به خاطر راحتی بیشتر از واژه‌های دقیق «دوست» و «دشمن» برای نوع روابط استفاده کنیم و دوستی رو کاملا ۱+ و یا ۱- فرض کنیم. بنابراین شما و همسرتون دوست، شما و مادرتون دوست ولی همسر شما و مادر شما دشمن همدیگه هستند. اینجا توازن از بین میره، به عنوان مثال کافیه شما هدیه‌ای برای مادرتون بخرید، در این صورت همسرتون شاکی میشه و مجبورید شب رو توی کوچه بخوابید! حالا فرض کنید که شما و آرش، هم‌زمان از یکی از همکار/هم‌کلاسی‌هاتون به اسم احسان متنفرید. خب طبق یه قاعده‌ی قدیمی، داشتن دشمن مشترک دوستی میاره و یا اینکه دشمن دشمن شما، دوست شماست. آرش دشمن احسان و احسان دشمن شماست پس طبق این قاعده شما و آرش دوست هستید. این مجموعه هم متوازنه. حالت دیگه که ممکنه پیش بیاد این هست که شما، میثم و سهیل هر سه دشمن همدیگه باشید، خب به وضوح مشخصه که این مجموعه نامتوازن هست؛ هر لحظه ممکنه کسی علیه کسی شورش کنه!

تا اینجا چارچوب بحث ما در مورد توازن مشخص شد. جذابیت این موضوع برای ما دانشمندان (!) زمانی شروع میشه که به فکر مدل‌سازی این چارچوب باشیم. ایده‌ی اصلی این کار توسط هایدر (۱۹۵۸) مطرح شد. مثلثی فرض کنید که هر راسش یکی از سه نفر بالا باشه و ضلعی که هر دو راس رو بهم متصل میکنه رو به عنوان رابطه اون دو راس(نفر) در نظر بگیرید. اگر دو نفر دوست هم باشند، به ضلعی که دو راس متناظر با اون دو نفر رو  متصل میکنه، ۱+ نسبت میدیم و اگر دو نفر دشمن هم باشند به ضلع متصل کننده  ۱-.

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

Screenshot from 2015-08-04 20:26:34
شبکه‌های متوازن و نامتوازن و نوع آرایش آن‌ها

بنابراین مدلی که به عنوان یک «شبکه‌ اجتماعی» برای توصیف روابط بین انسان‌ها و متوازن بودنشون مطرح می‌کنیم این جوری ساخته میشه:

    1. با توجه به افراد،‌سازمان‌ها، کشورها و هرچیزی که روابط دوستی یا دشمنی دارند ما یک گراف کامل از مرتبه تعداد اعضا مشخص می‌کنیم. گراف کامل هست چون که فرض بر اینه که همه‌ی اعضا همدیگه رو می‌شناسند و رابطه دارند. به عنوان مثال به کشورهای عضو سازمان ملل فکر کنید که یا از هم خوششون میاد یا از هم بدشون میاد!
    2. هر یال یا مثبته و یا منفی. هیچ حالت بینابینی وجود نداره.
    3. یک مثلث متوازن (balanced) است اگر و تنها اگر حاصل‌ضرب علامت یال‌های آن مثبت باشه. (اگر تعداد یال‌های منفی فرد باشه: (-,-,- یا -,+,+) اون‌موقع گراف ما و یا شبکه ما نامتوازن خواهد شد.)
      شیوه‌ی قطبیده شدن جهان به دو بلوک شرق و غرب قبل از جنگ‌جهانی اول
      شیوه‌ی قطبیده شدن جهان به دو بلوک شرق و غرب قبل از جنگ‌جهانی اول

خب حالا فرض کنید که ما یک شبکه‌ی مشخص از اعضا و روابطشون داریم:

    • آیا می‌تونیم بگیم که اوضاع این شبکه چقدر متوزانه؟
    • آیا می‌تونیم با در نظر گرفتن شبکه‌ی کشورهای دنیا و روابطشون بگیم آیا ممکنه بین دو کشور صلح برقرار بشه؟ یا اگه بین دو کشور صلح برقرار شد، اون موقع این صلح موضعی (منطقه‌ای) چه اثراتی روی صلح جهانی داره؟ به عبارت دیگه اگه علامت یالی رو در یک شبکه عوض کنیم (رابطه‌ی دو نفر رو از دوستی به دشمنی و یا عکس تبدیل کنیم) اون موقع میشه فهمید برای کل شبکه چه اتفاقی می‌افته؟
  • آیا می‌تونیم پیش‌بینی کنیم در چه شرایطی ممکنه بین هوادارهای دو تیم ورزشی توی ورزشگاه آزادی درگیری و نزاع پیش میاد؟

بله، با تقریب خوبی می‌تونیم همه این‌کارها رو به لطف نظریه‌ی توازن و یا بالانس تئوری انجام بدیم.

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

خب پس وقتی ما یک شبکه داریم که در یکی از این دو حالت نیست یعنی متوازن یا بالانس نیست. سوال مهم اینه که خب اگر بخواهیم که شبکه رو بالانس یا متوازن کنیم چه کار باید انجام بدیم؟ یک راه پیشنهادی این هست که یک یال رو به صورت تصادفی انتخاب کنیم و علامتش رو عوض کنیم و بعدش ببینیم برای سیستم چه اتفاقی می‌افته. به عبارت دیگه اگر بعد از عوض کردن اون یال، تعداد مثلث‌های متوازن در کل شبکه زیاد بشه یعنی اینکه ما تونستیم شبکه رو به یک حالت متوازن‌تر هدایت کنیم، ولی اگر با عوض کردن علامت یالی تعداد مثلث‌های متوازن شبکه کم بشه یعنی عدم‌توازن رو توی شبکه بالا بردیم.

از اون‌جایی که ما فیزیک‌پیشه هستیم، اجازه بدید با رویکرد انرژی به قضیه نگاه کنیم؛ با توجه‌ به پیش‌فرض‌های ما، انرژی شبکه باید متناسب باشه با تعداد مثلث‌های نامتوازن منهای تعداد مثلث‌های متوازن موجود درشبکه:

CodeCogsEqn_001
معادله انرژی برای یک شبکه اجتماعی

 

CodeCogsEqn
اگر دو راس دوست باشند به یال بین آن دو ۱+ نسبت می‌دهیم و اگر دشمن باشند ۱-

 

نمودار انرژی برای شبکه‌هایی با (A) سه راس و (B) چهار راس
نمودار انرژی برای شبکه‌هایی با (A) سه راس و (B) چهار راس

n تعداد کل رئوس است و به خاطر بهنجارش (Normalization) تفاضل انرژی‌ها رو بر تعداد کل مثلث‌های شبکه تقسیم کردیم تا انرژی هنجار به واحد بشه! بنابراین بیشترین مقدار انرژی ۱ و کم‌ترین مقدار ۱- خواهد شد. وجود منفی هم به این خاطر هست که هرچی انرژی کم‌تر باشه (منفی‌تر) سیستم متوازن‌تره. خب بیاید با استفاده از این رابطه نمودار انرژی رو برای دو تا شبکه‌ی کوچیک، یکی با ۳ راس و دیگری با ۴ راس بکشیم:

نمودار A انرژی یک شبکه یا ۳ راس رو نشون میده که ساده‌ترین شبکه برای بررسی هست. بنابراین انرژی شبکه یا ۱ (نامتوزان) و یا ۱- (متوازن) هست. عددی که بالای هر مثلث نوشته شده فراوانی هر کدوم هست (مثلا اینکه یک یال خط‌چین باشه سه حالت داره، بدیهیه!)

نمودار B انرژی یک شبکه‌ی با ۴ راس رو نشون میده. خب توی این شبکه علاوه بر حالات قبل، انرژی صفر هم مشاهده میشه. طبیعیه که ما توی این شبکه می‌تونیم از بالا به پایین بیایم و شبکه رو متوازن کنیم. برای این کار کافیه علامت یکی از یال‌ها رو عوض کنیم و به وضعیت پایدارتر برسیم. خب این سوال مطرح میشه که:

  • آیا توی هر شبکه‌ای ممکنه با عوض کردن علامت یک یال، به یک شبکه‌ی متوازن‌تر رسید؟
Screenshot from 2015-08-04 22:06:50
وجود حالت‌های مسدود (jammed state)

متاسفانه در مورد شبکه‌های بزرگ(تعداد راس بیشتر) حالت‌هایی در سیستم وجود داره که به Jammed States و یا به قول استیون استروگاتز Strict Jammed States معروف هستند. این حالت‌ها چیزی نیستند جزو کمینه‌های نسبی انرژی. به این معنی که انرژی این‌حالت‌ها از تمام حالت‌های ممکن که با تغییر علامت یک یال در دسترس هستند، کمتر هست. بنابراین در حالت‌های jammed یا مسدود، امکان این‌که تنها با تعویض علامت یک یال به یک حالت متوازن‌تر رفت، وجود نداره. به عبارت دیگه انرژی حالت‌های مسدود کوچکتر یا مساوی انرژی حالت‌های مجاور هست.

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

یک گراف Paley با ۱۳ راس،‌ به شیوه‌ی اتصال رئوس دقت کنید.
یک گراف Paley با ۱۳ راس،‌ به شیوه‌ی اتصال رئوس دقت کنید.

ویژگی جالبی در مورد حالت‌های مسدود با انرژی صفر وجود داره؛ یال‌های مثبت در این حالت‌ها عضو یال‌های گراف Paley هستند. گراف Paley گرافی هست که تعداد رئوسش (q) یک عدد اول به شکل q=4k+1 هست. هر دو راس در این گراف درصورتی وصل هستند که تفاضل شماره اون دو راس یک عدد مربع کامل باشه به پیمانه‌ی q. این گراف‌ها خیلی خوشگل‌ هستند و قیافه‌ی متقارنی دارند. می‌تونید تعدادی از این گراف‌ها رو این‌جا ببینید.

 اگر دوست دارید به یک حالت مسدود با انرژی U=0 برسید:

    1. به یال‌هایی از شبکه که عضو گراف Paley هستند «+» نسبت دهید.به سایر یال‌ها (یال‌هایی که عضو شبکه (گراف کامل) هستند ولی عضو گراف Paley نیستند) «-» نسبت دهید.
    2. یک راس جدید به شبکه اضافه کنید (وسط شبکه!). هم اکنون شبکه شما q+1 راس دارد.
    3. راس جدید را به q راس قبلی وصل کنید و به یال‌های بین این راس و سایر رئوس «-» نسبت دهید.

با این روش شما می‌تونید یک حالت مسدود با انرژی صفر بسازید که q+1 راس داره.

فکر کنم برای مقدمه کافی باشه!

  1. The Energy Landscape of Social Balance
  2. Dynamics of Social Balance on Networks
  3. STRUCTURAL BALANCE: A GENERALIZATION OF HEIDER’S THEORY’
  4. Social Balance on Networks: The Dynamics of Friendship and Enmity
  5. Statistical physics of balance theory
سخنرانی استیون استروگتز در مورد نظریه توازن