بخش 9.1
مقدمه

بلژیک نمونه ای از جامعه دو فرهنگی است: 59% شهروداند آن اهل فنلاندرز هستند و هلندی صحبت می کنند و 40% شهروندانش اهل والون هستند و فرانسوی صحبت می کنند. از آنجایی که کشورهای چند قومیتی در سراسر دنیا تجزیه شده اند باید بپرسیم این سوال پیش می آید که چطور کشوری با دو قوم مختلف از سال 1830 در صلح در کنار یکدیگر زندگی می کنند؟ آیا بلژیک کشوری در هم تنیده است طوری که اهمیتی ندارد چه کسی فنلاندرزی و چه کسی والوونی است؟ یا اینکه دو ملیت در دو سوی یک مرز قرار دارند و یاد گرفته اند ارتباطاتشان را در کمترین سطح ممکن نگه دارند؟

وینسنت بلوندل و دانشجویش الگوریتمی برای تشخیص ساختار انجمن ها ارائه دادند و در سال 2007 به این پرسش ها جواب دادند. در ابتدا با شبکه تماس های تلفنی آغاز کردند و هرکسی را به افرادی که معمولا با تلفن همراهشان در ارتباط هستند متصل کردند [2]. این الگوریتم نشان داد که شبکه اجتماعی بلژیک یه دو خوشه بزرگ از انجمن ها تشکیل شده است به طوری که افراد هر یک از این خوشه ها به ندرت با افراد خوشه های دیگر تماس تلفنی برقرار می کنند(شکل 9.0). در واقع وقتی به هر گره در این شبکه، زبانی که با آن صحبت می کنند را نسبت دادند این جدایی کشف شد . دریافتند که یکی از خوشه ها اغلب افراد فرانسوی زبان هستند در حالی که خوشه دیگر، اغلب افراد هلندی زبان هستند.

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

• شبکه های اجتماعی:

  شبکه های اجتماعی پر از انجمن هایی هستند که به راحتی می توان آنها را تشخیص داد و دهه ها قبل، محققان به این موضوع توجه کرده اند[3,4,5,6,7]. به علاوه احتمال اینکه کارکنان یک شرکت با هم در ارتباط باشند بیشتر از ارتباط داشتن با کارکنان شرکت های دیگر است[3]. بنابراین به نظر می رسد که در شبکه های اجتماعی شرکت ها و محل کارها انجمن های چگالتری را تشکیل می دهند. انجمن ها همچنین می توانند حلقه دوستان، افرادی که سرگرمی های مشابه دارند یا کسانی که در همسایگی یکدیگر زندگی می کننند را نشان دهند.

  یکی از شبکه های اجتماعی که از جنبه تشخیص انجمن ها مورد توجه قرار گرفته است، کلوپ کاراته زاکاری (شکل 9.2) است[7] که ارتباط بین 34 عضو یک باشگاه کاراته را نشان می دهد. با توجه به تعداد اعضای کم این کلوپ، همه اعضا یکدیگر را می شناسند. برای پیدا کردن رابطه واقعی بین اعضای این کلوپ یک جامعه شناس به نام وین زیکاری78 جفت پیوند را بین اعضای کلوپ که بیرون از آنجا معمولا یکدیگر را ملاقات می کردند، ثبت کرد(شکل 9.2a).

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

  

• شبکه های بیولوژیکی
  

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

  انجمن ها همچنین نقش مهمی در تشخیص بیماری های انسان ها بازی می کنند. به علاوه، پروتئین های بیماری های مشابه معمولا با هم برهم کنش دارند [12,13]. این کشف، الهام بخش فرضیه ماژول بیماری هاست[14]. این فرضیه ادعا می کند که بیماری ها به همسایه های مشخصی در شبکه سلولی متصل هستند.

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

H1: فرضیه مبنا

ساختار انجمن های یک شبکه بصورت یکتا در دیاگرام ارتباطات آن کدگذاری شده است.

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

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

بخش 9.2
انجمن های پایه ای

منظور از انجمن چیست؟ چه تعداد انجمت در یک شبکه وجود دارند؟ به چند طریق می توان یک شبکه را به انجمن های مختلف تفکیک کنیم؟ در این بخش به این سوال های پر تکرار در زمینه تشخیص انجمن ها را پاسخ خواهیم داد

تعریف انجمن ها

درک ما از انجمن ها براساس فرضیه دوم است:(Image 9.4):

H2: فرضیه تراکم و همبندی

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

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

کیلیک بیشینه
یکی از اولین مقاله ها در زمینه ساختار انجمن ها در سال 1949 چاپ شد که در آن انجمن به گروهی از افراد گفته می شد که همه آنها یکدیگر را می شناختند[5]. در اصطلاحات نظریه گراف ها بدین معنی است که انجمن یک زیر گراف کامل یا یک کیلیک است. این تعریف کیلیک خود به خود همه شرط های H2 را دارد: زیر گراف همیند با تراکم پیوند بیشینه است. با این حال در نظر گرفتن انجمن ها به عنوان کیلیک نواقصی هم دارد از جمله:

• با اینکه مثلث ها در شبکه ها پرتکرار هستند ولی به ندرت کیلیک های بزرگتر ایجاد می شوند
• این که یک انجمن باید گراف کامل باشد شرط سخت گیرانه ای است و ممکن است بسیازی از موارد که حقیقتا انجمن هستند را ندید بگیرد. برای مثال هیچ کدام از انجمن های شکل 9.2 و 9.3 زیرگراف های کامل نیستند.

انجمن های قوی و ضعیف
برای آنکه سخت گیری های کیلیک را کاهش بدیم، زیرگرف همبند C با N_C گره در شبکه را در نظر بگیرید. درجه داخلی k_i^int گره i تعداد پیوندهایی را نشان می دهد که گره i را به سایر گره ها در C متصل می کند. درجه خارجی k_i^ext تعداد پیوند هایی است که گره i را به بقیه گره های شبکه متصل می کند. اگر k_i^ext=0 تمام همسایه های i داخل C قرار دارند، یعنی C انجمن خوبی است برای گره i است. اگر k_i^int=0 باید گره i در انجمن دیگری قرار بگیرد. با این تعریف می توانیم دو نوع انجمن را از هم تمیز دهیم(شکل 9.5).

• انجمن قوی
  C انجمن قوی است اگر هر کدام از گره های داخل C بیشتر به گره های داخل C متصل باشند تا سایر گره های گراف[15,16]. به طور خاص، زیرگرف C یک انجمن قوی تشکیل می دهد اگر به ازای هر گره i ∈ C، $k_i^{{\mathop{\rm int}} } (C) > k_i^{ext} (C) \hspace{20 mm} (9 . 1)$
• انجمن ضعیف
  C یک انجمن ضعیف است اگر مجموع درجات داخلی زیرگراف آن از مجموع درجات خارجی بیشتر شود [16]. به طور خاص زیر گراف C یک انجمن ضعیف را تشکیل می دهد اگر: $\sum\limits_{i \in C} {k_i^{{\mathop{\rm int}} } (C)} > \sum\limits_{i \in C} {k_i^{ext} (C)} \hspace{20 mm} (9 . 2)$

برآورده کردن شرط های انجمن ضعیف ساده تر از انجمن قوی است، زیرا اجازه می دهد بعضی از گره ها از (9.1) تبعیت نکنند. به عبارت دیگر نامساوی (9.2) به کل انجمن می شود نه تک تک اعضای آن.

توجه کنید که هر کلیک یک انجمن قوی است و هر انجمن قوی، انجمن ضعیف هم است. اما برعکس آن لزوما همیشه برقرار نیست(شکل 9.5).

تعریف ارائه شده از انجمن ها، درک ما از انجمن ها را پالایش می کند. درضمن به ما یادآوری می کنند که در تعریف انجمن ها آزادی هایی داریم.

تعداد انجمن ها

به چند طریق می توان گره های یک شبکه را به انجمن های مختلف دسته بندی کنیم؟ برای پاسخ دادن به این پرسش، ساده ترین مساله پیدا کردن انجمن بنام دوبخشی گراف را درنظر بگیرید: می خواهیم شبکه را به دو زیر گراف نا هم پوشان تقسیم کنیم، طوری که تعداد پیوند ها بین گره های این دو گروه یا همان اندازه برش، کمینه باشد(نکته 9.1)

افراز گراف
برای حل مساله دوبخشی گراف می توان تمام حالت های ممکن برای اینکه گراف به دو بخش تقسیم شود را بررسی کرده و حالتی که در آن برش کمینه شود را انتخاب کنیم. برای تعیین هزینه محاسباتی این رویکرد قوی باید تعداد راههای مختلفی که می توان شبکه ای با N گره را به دو گروه به N₁و N₂ گره تقسیم کرد را محاسبه کنیم.

با استفاده از فرمول استرلینگ

فرمول(9.3) را می توان بصورت زیر نوشت

برای ساده تر شدن مساله فرض کنید می خواهیم شبکه را به دو بخش برابر با سایز N₁ = N₂ = N/2تقسیم کنیم. در این حالت فرمول (9.4) بصورت زیر تبدیل می شود.

نشان می دهد که تعداد دو بخشی ها با زیاد شدن N بصورت نمایی زیاد می شود.

برای نشان دادن نتایج فرمول (9.5)، فرض کنید شبکه ای با 10 گره داریم که می خواهیم آن را به دو زیر گراف با سایز N₁ = N₂ = 5 تقسیم کنیم. طبق فرمول (9.3) لازم است 252 دو بخشی را چک کنیم با نمونه ای که کوچکترین اندازه برش را دارد پیدا کنیم. فرض کنید کامپیوتر ما این 252 حالت را در یک میلی ثانیه(10^-3ثانیه) پیدا کند. در ادامه اگر بخواهیم شبکه ای با 100 گره را به دو بخش به سایز های N₁ = N₂ = 50 تقسیم کنیم، طبق فرمول (9.3) باید به طور تقریبی 10²⁹حالت مختلف را بررسی کنیم و با کامپیوتر مشابه حالت قبلا 10¹⁶سال زمان لازم است. بنابراین این استراتژی قوی محکوم به شکست است، زیرا حتی نمی توان شبکه با سایز معمولی را دوبخش کرد.

تشخیص انجمن
در حالیکه در افراز گراف، تعداد و سایز انجمن ها از قبل تعریف می شوند، ولی در تشخیص انجمن هر دو ملفه نامشخص هستند. افراز در واقع تقسیم شبکه به تعداد دلخواهی گروه است بطوری که هر گره به یک و تنها یک گروه تعلق داشته باشد. تعداد افراز های ممکن بصورت زیر محاسبه می شود[19-22]:

همانطور که شکل 9.7 نشان می دهد با رشد N، B_Nسریعتر از نمایی رشد می کند.

معادله های (9.5) و (9.6) نشانه هایی از تغییرات بنیادین در تشخیص انجمن هستند: تعداد راههای که می توان شبکه ای را به انجمن ها تقسیم کنیم با سایز شبکه N، سریعتر از نمایی رشد می کند. بنابراین پیدا کردن تمام افراز های شبکه های بزرگ غیر ممکن است(نکته 9.2).

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

بخش9.3
خوشه بندی سلسله مراتبی

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

در این نوع خوشه بندی از ماتریس تشابه شروع می کنیم. در این ماتریس مولفه های x_ij نشان دهنده فاصله بین گره های i و j را نشان می دهند. شباهت ها در تشخیص انجمن با توجه به موقعیت نسبی گره های i و j در شبکه تعریف می شوند.

وقتی همه x_ij ها را داشته باشیم به صورت بازگشتی می توانیم گروهی از گره ها را که شباهت زیادی به هم دارند را پیدا کنیم. از دو فرایند مختلف می توان برای این منظور استفاده کرد: الگوریتم تراکمی ، گره هایی که شباهت زیادی دارند را در یک انجمن ادغام می کند، الگوریتم تقسیم کننده ، پیوند بین گره هایی که شباهت کمی به یک انجمن دارند را حذف می کند و انجمن ها را از هم مجزا می کند. هر دو روش درهت سلسله مراتبی ایجاد می کند که دندوگرام یا نمودار درختی هم نامیده می شود و انجمن های محتمل را پیش بینی می کند. در ادامه استفاده از الگوریتم های تراکمی و تقسیم کننده را بررسی می کنیم.

رویه تراکمی: الگوریتم راواسز

استفاده از خوشه بندی سلسله مراتبی تراکمی را در تشخیص انجمن با الگوریتم راواسز توضیح می دهیم. از این الگوریتم به منظور تشخیص ماژول های عملگر در شبکه متابولیک استفاده کرده ایم [11]. الگوریتم شامل گام های زیر است:

گام اول: تعریف ماتریس شباهت
در الگوریتم تراکمی باید گره هایی که به یک انجمن تعلق دارند شباهت بالا و گره هایی که متعلق به انجمن های متفاوت هستند شباهت کمی داشته باشند. در شبکه ها، گره هایی که به هم متصل هستند و همسایه های مشترکی دارند احتمالا متعلق به یک انجمن هستند، بنابراین x_ij آنها زیاد خواهد شد. ماتریس همپوشانی تپولوژیکی (شکل 9.9) [11] $x_{ij}^o = \frac{{J(i,j)}}{{\min (k_i ,k_j ) + 1 - \Theta (A_{ij} )}} \hspace{20 mm} (9 . 7)$

که این انتظار را برآورده می کند. در اینجا Θ(x) تابع پله ای هویساید است که به ازای x≤0 صفر و برای x>0 یک است. J(i.j) تعداد همسایه های مشترک گره های iو j را نشان می دهد و اگر پیوند بین خود گره های iو jباشد، یک واحد به آن اضافه می کنیم. min⁡(k_i,k_j) هم کمترین درجه بین گره های i و j را نشان می دهد. در نتیجه:

• x_ij⁰=1 اگر گره های i و j به هم متصل باشند و همسایه های مشترک هم داشته باشند، مثل A و B در شکل 9.9a..
• x_ij⁰(i, j) =0 اگره گره های iو j همسایه مشترک نداشته باشند و همچنین بین آنها هم پیوندی نباشد، مثل A و E.
• اعضای همسایگی پرتراکم از نظر تپولوژیکی هم پوشانی بالایی دارند مثل H,I,J,K یا E,F,G.

گام دو: تصمیم گیری در مورد شباهت گروه ها
از آنجایی که گره ها با هم ادغام می شوند و انجمن ها را تشکیل می دهند، باید میزان شباهت انجمن ها را اندازه گیری کنیم. سه رویکرد تکی ، کامل و میانگین پرکاربردترین روش ها در محاسبه میزان شباهت انجمن ها با استفاده از ماتریس شباهت گرهx_ij هستند(شکل 9.10d). الگوریتم راواسز از تکنیک شباهت کلاستر ها بر اساس میانگین استفاده می کند. به این صورت که میزان شباهت براساس میانگین x_ij تمام گره هایی که در هر کدام از انجمن ها قرار دارند تعریف می شود(شکل 9.10d).

گام سه: پیاده کردن خوشه بندی سلسله مراتبی
الگوریت راواسز از فرایند زیر برای تشخیص انجمن ها استفاده می کند:

1. هر گره یک انجمن در نظر گرفته می شود و x_ij برای همه زوج گره ها محاسبه می شود.
2. زوج انجمن یا جفتی که بیشترین شباهت را دارند پیدا کنید و آنها را ادغام کنید تا یک انجمن تشکیل دهند.
3. شباهت بین انجمن جدید و بقیه انجمن ها را محاسبه کنید
4. گام های 2 و 3 را تکرار کنید تا جایی که همه گره ها در یک انجمن قرار بگیرند

گام چهار: نمودار درختی
در اثر ادغام های انجام شده در گام 3 نهایتا همه گره ها در یک انجمن قرار می گیرند. با استفاده از نمودار درختی می توانیم سازمان انجمن های شبکه را بدست آوریم.

نمودار درختی ترتیبی که گره ها به یک انجمن داده شده اند را نشان می دهند. برای مثال نمودار درختی Image 9.9b نشان می ددهد که طبق این الگوریتم اول گره های Aبا B ، K با J و E با F ادغام می شوند، زیرا برای هرکدام از اینها x_ij⁰=1. در ادامه گره C به (A,B)، I به (K,J ) و G به (E,F) اضافه شده است.

برای تشخیص انجمن ها باید نمودار درختی را برش بزنیم. خوشه بندی درختی در مورد جایی که باید برش انجام شود چیزی نمی گوید. برای مثال با استفاده از برشی که با خط چین در شکل 9.9b نشان داده شده است، سه انجمن تشخیص داده می شود(ABC,EFG,HIJK).

با اجرای الگوریتم راواسز روی شبکه متابولیک E.coli (شکل 9.3a) ساختار انجمنی مربوط به متابولیسم باکتریایی را تشخیص می دهد. برای پیدا کردن ارتباطات بیولوژیکی این انجمن ها، شاخه های نمودار درختی بر اساس کلاس بندی های بیوشیمی که تا کنون برای آنها شناخته شده است با رنگ ها کدگذاری شده اند. همانطور که در شکل 9.3b نشان داده شده است لایه هایی که نقش بیوشیمی مشابهی دارند در شاخه مشابهی از درخت قرار می گیرند. به عبارت دیگر کلاس بندی های بیوشیمی این متابولیسم ها ارتباطات بیوشیمی انجمن های بدست آمده از توپولوژی شبکه را تایید می کنند

پیچیدگی محاسباتی
تعداد محاسبات مورد نیاز برای اجرای الگوریتم راواسز چندتاست؟ الگوریتم چهار گام دارد، که هر کدام پیچیدگی محاسباتی مربوط به خود را دارد:

گام 1: برای محاسبه ماتریس شباهت x_ij⁰نیاز به N² مقایسه بین جفت گره است. بنابراین تعداد محاسبات N^2 خواهد بود. به عبارت دیگر پیچیدگی محاسباتی آن O(N^2) است.

گام 2: برای محاسبه شباهت بین گروه ها در هر گام باید فاصله بین خوشه جدید و بقیه خوشه ها را حساب کرد. اگر این عمل N بار انجام شود به 0(N²) محاسبه نیاز است.

گام 3و4: نمودار درختی در 0(NlogN) ساخته می شود

با ترکیب گام های 1-4 ، تعداد محاسبات مورد نیاز در مقیاس 0(N²) + 0(N²) + 0(NlogN) خواهد بود. از آنجایی که کندترین گام در مقیاس 0(N²) اجرا می شود، پس پیچیدگی محاسباتی این الگوریتم 0(N²) است. بنابراین خوشه بندی درختی بسیار سریعتر از راهکار ساده لوحانه اولیه با مرتبه اجرایی 0(e^N) است.

رویه های تقسیم کننده: الگوریتم گیروان-نیومن

اصولا رویه های تقسیم کننده پیوند بین گره هایی که به انجمن های مختلف تعلق دارند را حذف می کند و در نهایت شبکه را به انجمن های محزا از هم تقسیم می کند. کاربرد آنها را با معرفی الگوریتمی که که توسط مایکل گیروان و مارک نیومن ارائه شده است توضیح می دهیم [9,23]. این الگوریتم شامل گام های زیر است:

گام 1: تعریف مرکزیت
با اینکه در الکوریتم تراکمی x_ij گره هایی را انتخاب می کند که به یک انجمن تعلق دارند، در الگوریتم تقسیم کننده x_ij که مرکزیت هم نامیده می شود، جفت گره هایی را انتخاب می کند که به انجمن های مختلفی تعلق دارند. بنابراین در اینجا اگر گره های iوj به انجمن های مختلف تعلق داشته باشند، x_ij باید زیاد (یا کم) باشد و اگر به یک انجمن تعلق دارند x_ij کم باشد. سه معیاری که برای تعیین مرکزیت استفاده می شود و دارای شرایط لازم هستند در شکل 9.11 مورد بحث قرار گرفته اند. سریعترین این معیار ها بینابینی پیوند است. در این معیار x_ij تعداد کوتاهترین مسیر هایی است که از پیوند (I,j) عبور می کنند. انتظار می رود، پیوند هایی که انجمن های مختلف را به هم متصل می کنند x_ij بزرگتری داشته باشند در حالیکه پیوند های درون یک انجمن باید x_ij کوچکتری داشته باشند.

گام 2: خوشه بندی سلسله مراتبی
گام آخر در الگوریتم تقسیم بندی همان گام های استفاده شده در خوشه بندی تراکمی است(شکل 9.12):

1. مرکزیت x_ij را برای هرکدام از پیوند ها حساب کنید.
2. پیوندی که بیشترین مرکزیت را دارد حذف کنید. اگر مجموعه ای از این پیوند ها بودند یکی را به تصادف انتخاب کنید.
3. در شبکه جدید، مرکزیت هر پیوند را حساب کنید.
4. گام های 2 و 3 را تکرار کنید تا جایی که تمام پیوند ها حذف شوند.

گیروان و نیومن الگوریتم خود را روی شبکه کلوپ کاراته زاکاری اجرا کردند(شکل 9.2a) و نشان دادند که انجمن های پیدا شده تقریبا به خوبی با دو گروه تطابق پیدا می کنند. تنها گره 3 اشتباه دسته بندی شده بود.

پیچیدگی محاسباتی
گام محدود کننده نرخ در الگوریتم تقسیم کننده مربوط به محاسبه مرکزیت است. در نتیجه پیچیدگی محاسباتی الگوریتم به معیار مزکزیتی که استفاده می کنیم بستگی دارد. کاربردی ترین آن بینابینی پیوند با O(LN) است [24,25,26] (شکل 9.11a). گام سوم الگوریتم فاکتور جدیدL در زمان اجرا را معرفی می کند، بنابراین الگوریتم در مقیاس 0(L²N) یا برای شبکه های خلوت در مقیاس 0(N³) قرار می گیرد.

سلسله مراتبی در شبکه های واقعی

خوشه بندی سلسله مراتبی دو سوال اساسی ایجاد می کند:

انجمن های تودرتو
اولا،به نظر می آید که ماژول های کوچک در دل ماژول های بزرگ جای گرفته ان. این انجمن های تودرتو به خوبی به وسیله نمودار سلسله مراتبی نشان داده می شوند(شکل 9.9bو 9.12e). چطور این نکته را می دانیم، حتی اگر این سلسله مراتب برای شبکه وجود داشته باشد؟ ایا ممکن است این سلسله مراتب به وسیله الگوریتم تحمیل شده باشد، شبکه مربوطه ساختار انجمنی تودرتو داشته یا خیر؟ دوما، در ارتباط با انجمن ها و مشخصه مقیاس آزاد بودن، فرضه تراکم ادعا می کند که شبکه ها می توانند مجموعه ای از زیر گراف ها افراز شوند که پیوند ضعیف با سایر زیرگراف ها دارند. چطور می توانیم انجمن های مجزا در شبکه های مقیاس آزاد داشته باشیم، اگر اتصال هاب ها به چندین انجمن اجتناب ناپذیر باشد؟

مدل شبکه سلسله مراتبی، که ساختار آن در شکل 9.13 نشان داده شده است، تناقض بین انجمن ها و ویژگی مقیاس آزاد بودن را حل می کند و به ما درکی از ساختار درختی تودرتو انجمن ها می دهد. شبکه بدست آمده چندین ویژگی کلیدی دارد

ویژگی مقیاس آزاد
مدل سلسله مراتبی شبکه مقیاس آزاد با درجه نمایی ایجاد می کند (شکل 9.14a ، مباحث پیشرفته 9.A)

ضریب خوشه بندی مستقل از سایز
هرچند در مدل اردوش-رینی و آلبرت-باراباشی، ضریب خوشه بندی با N کاهش می یابد(بخش 5.9) در شبکه های سلسله مراتبی داری C=0.743 که مستقل از سایز شبکه است(شکل 9.14c). این ضریب خوشه بندی مستقل از N در شبکه متابولیک مشاهده شده است [11].

ماژولاریته سلسله مراتبی
این مدل از تعدا بسیار زیادی انجمن های کوچک تشکیل شده که انجمن های بزرگتر را تشکیل می دهند که این شبکه های بزرگتر هم با هم ترکیب شده و انجمن های بزرگتر را تشکیل می دهند. نشانه کمی ماژولاریته سلسله مراتبی تودرتو، وابستگی ضریب خوشه بندی گره ها به درجه گره است[11,27,28].

به عبارت دیگر، هرچه درجه گره ای بیشتر باشد، ضریب خوشه بندی آن کمتر می شود.

فرمول (9.8)روشی که در یک شبکه انجمن ها سازماندهی شده اند را نشان می دهد. به علاوه، در گره های با درجه پایین، C زیاد است زیرا در انجمن های متراگم حاضر هستند. گره های با درجه بالاC کمی دارند زیرا به انجمن های مختلف متصل هستند. برای مثال، در شکل 9.13c، برای گره هایی که در مرکز ماژول 5-گره ای قرار دارند k=4 وضریب خوشه بندی C=4 است. گره هایی که در مرکز ماژول 25گره ای قرار دارند دارای k=20 و C=3/19 هستند. گره هایی که در مرکز ماژول 125 گره ای قراردارند هم دارای k=48 و C=3/83 هستند. بنابراین هرچه درجه گره ای بیشتر باشد C آن کمتر می شود.

مدل شبکه سلسله مراتبی بیان می کند که با بررسی C(K) می توان در مورد سلسله مراتبی بودن شبکه ای تصمیم گرفت. در مدل اردوش-رینی و آلبرت-باراباشی، C(K) مستقل از k بنابراین ماژولاریته سلسله مراتبی ندارند. برای بررسی اینکه آیا در دنیای واقعی، سیستم ها ماژولاریته سلسله مراتبی دارند یا خیر، C(k) برای 10 شبکه مرجع حساب شده است و نشان می دهند ( شکل 9.36):

• تنها شبکه برق، ماژولاریته سلسله مراتبی ندارد، زیرا C(k) آن مستقل از k است (شکل 9.36a)
• در 9 شبکه باقیمانده C(k) با k افزایش می یابد. بنابراین در این شبکه های گره های کوچک بخشی از شبکه های پرتراکم کوچک هستند در حالی که هاب ها انجمن های مجزا را یکدیگر متصل می کنند.
• در شبکه همکاری های علمی، متابولیک و ارجاعات علمی در بخش هایی با k بالا، C(k) از فرمول (9.8) پیروی می کند. مدل C(K) برای تلفن همراه، پست الکترونیکی، برهم کنش پروتئینی و وب همانند شبکه هایی که C(k) آنها از فرمول (9.8) پیروی نمی کند، باید تک به تک بدست آید. مدل های شبکه دیگر با جزئیات بیشتر C(k)~k^-β را پیش بینی می کنند که در آن β بین 0 و 2 است [27,28].

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

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

بخش 9.4
ماژولاریته

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

H3 فرضیه تصادفی

شبکه هایی که پیوند های آنها تصادفی برقرار شده اند، ذاتا فاقد ساختار انجمنی هستند

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

ماژولاریته

شبکه ای با N گره، L پیوند و n_c انجمن را درنظر بگیرید. در هر کدام از انجمن ها N_c گره با L_c پیوند که در آن c=1,...,n_c به یکدیگر متصل می شوند. براساس فرضیه تراکم H2 اگر L_c بزرگتر از تعداد پیوند های مورد انتظار برای گره های N_c که از دنباله درجه شبکه بدست می آید باشد، در نتیجه زیر گراف C_c هم جزئی از انجمن درستی خواهد بود(شکل 9.2). بنابراین تفاوت بین نمودار اتصالات شبکه A_ij و تعداد پیوند های مورد انتظار بین i و j درصورتی که پیوند های شبکه به طور تصادفی ایجاد شودند را بررسی خواهیم کردp_ij.

برای بدست آوردن p_ij می توان درجه گره های را ثابت نگه داشت و شبکه اصلی را تصادفی کرد. با استفاده از مدل (7.1) که نماش درجه تهی هم دارد، خواهیم داشت:

اگر M_c مثبت باشد، بصورت شانسی C_c تعداد پیوند هایش بیشتر از مقدار مورد انتظار خواهد بود، بنابراین یک انجمن بالقوه را نشان می دهد. اگر M_c صفر باشد آنگاه ارتباط بین گره های N_c تصادفی خواهد بود و با توزیع درجه قابل توصیف است. در نهایت اگر M_c منفی باشد، گره های C_c انجمنی تشکیل نمی دهند.

با استفاده از (9.10) شکل ساده تری برای ماژولاریته (9.9) بدست می آید(مباحث پیشرفته 9.B)

که در آن L_c تعداد پیوند های موجود داخل انجمن C_c و k_c درجه کل گره های این انجمن است.

برای تعمیم این ایده ها به کل شبکه باید تمام افراز هایی که شبکه را به n_c انجمن افراز می کنند را درنظر گرفت. برای پیدا کردن این مساله که تراکم پیوند های محلی در انجمن های ایجاد شده با این افراز، با تراکم در شبکه ای که پیوند ها بطور تصادفی ایجاد شده اند، ماژولاریته افراز را بصورت جمع (9.11) روی همه n_c انجمن تعریف می کنیم[23].

ماژولاریته چندین ویژگی کلیدی دارد:

• ماژولاریته بیشتر، افراز بهتری ایجاد می کند
  هر چه M بیشتر باشد، ساختار انجمن مربوطه هم بهتر خواهد بود. همچنین در شکل 9.16A افرازی که بیشترین ماژولاریته (M=0.41)را دارد، دو انجمن مشخص را به درستی تشخیص می دهد. افرازی که ماژولاریته کمتری دارد، در تشحیص این دو انجمن منحرف می شود (شکل 9.16b). در نظر داشته باشید که ماژولاریته یک افراز نمی تواند بیشتر از یک باشد[31,32].
• ماژولاریته صفر و منفی
  اگر کل شبکه را به عنوان یک انجمن در نظر بگیریم، M=0 بدست می آید زیرا در این حالت دوتا از عبارات در پرانتز های (9.12) با هم برابر می شوند(شکل 9.16c). اگر هر کدام از گره ها به انجمن های متفاوتی تعلق داشته باشند، L_c=0 می شود و جمع (9.12)، n_c تا عبارت منفی خواهد داشت، بنابراین M منفی است(شکل 9.16d).

با استفاده از ماژولاریته می توان تشخیص داد کدام یک از افراز های پیش بینی شده توسط روش سلسله مراتبی، بهترین ساختار انجمنی را نشان می دهد. برای این کار می توان افرازی را انتخاب کرد که برای آن M بیشینه است. این مساله در شکل 9.12f M قابل مشاهده است. در این شکل مقدار M برش های مختلف نمودار درختی نشان داده شده است و وقتی شبکه را به سه انجمن افراز کنیم M بیشینه می شود.

الگوریتم حریصانه

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

H4 : فرضیه ماژولاریته بیشینه

برای هر شبکه داده شده، افرازی که بالاترین ماژولاریته را دارد، ساختار انجمنی بهینه را نشان می دهد.

بررسی شبکه های کوچک این فرضیه را تایید می کنند. در این شبکه ها M بیشینه با انجمن های مورد انتظار مطابقت دارد(شکل 9.12 و 9.16).

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

الگوریتم حریصانه
اولین الگوریتم بیشینه سازی ماژولاریته تئسط نیومن معرفی شد[33]. با تکرار هر بار بین دو انجمن پیوندی ایجاد می شود، اگر حذف این پیوند تعداد انجمن ها را زیاد کند، این دو انجمن با هم تلفیق می شوند. گام های الگوریتم در زیر آمده است:

1. هر کدام از گره ها را یک انجمن در نظر می گیریم و با N انجمن که از گره های تکی تشکیل شده اند شروع می کنیم.
2. هر دو انجمنی که حداقل با یک پیوند به هم مرتبط شده اند را پیدا می کنیم و ∆M را برای دو حالتی که دو انجمن با هم تلفیق شوند و حالی که از هم مجزا باشند را حساب می کنیم. در بین تمام جفت انجمن های در نظر گرفته شده، جفت انجمنی که ∆M بیشتری دارد را انتخاب کرده و باهم تلفیق می کنیم. در نظر داشته باشید که همیشه ماژولاریته روی کل شبکه محاسبه می شود.
3. گام 2 را تکرار کنید تا زمانی که تمام گره های یک انجمن را تشکیل دهند، و در گام مقدار M را ثبت کنید.
4. افرازی را انتخاب کنید که بیشترین M را دارد.

برای روشن شدن قدرت پیش بینی الگوریتم حریصانه، شبکه همکاری علمی بین فیزیکدانان را در نظر بگیرید، که شامل N=56276 دانشمند فیزیک است که در تمام رشته های فیزیک مقاله هایی در arxiv.org منتشر کرده اند(شکل 9.17). الگوریتم حریصانه 600 انجمن با بیشینه M=0.713 پیدا می کند. چهار تا از این انجمن ها بشیار بزرگ هستند بطوری که 77% تمام گره های شبکه را شامل می شوند(شکل 9.17a). 93% نویسنده ها در بزرگترین انجمن در حوزه فیزیک مواد متراکم کار کرده اند در حالی که در دومین بزرگترین انجمن در زمینه فیزیک انرژی زیاد کار کرده اند، و این آمار نشان می دهد که هر انجمن فیزیکدانانی با علایق حرفه ای مشابه را شامل می شود. دقت الگوریتم حریصانه درشکل 9.2a نشان داده شده است. این شکل ساختار انجمنی کلوب کاراته زاکاری با بیشترین M را نشان می دهد و زیرانجمن های کلوب را به درستی تشخیص می دهد.

پیچیدگی محاسباتی
از آنجایی که محاسبه ∆M در زمان ثابت انجام می شود، گام دوم الگوریتم حریصانه به O(L) محاسبه نیاز دارد. بعد از تصمیم گیری درمورد انجمن هایی که باید با هم تلفیق شوند به روز رسانی ماتریس در بدترین حالت از مرتبه O(N) می شود. از آنجایی که در این الگوریتم باید N-1 تلفیق انجمن اتفاق بیوفتد، پیچیدگی محاسباتی O[(L+N)N] و در ماتریس های خلوت O(N²) می شود. پیاده سازی هایی که الگوریتم را بهینه کرده اند، پیچیدگی زمانی را به O(Nlog²N) کاهش داده اند (منبع آنلاین 9.1)

محدودیت های ماژولاریته

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

محدودیت تفکیک پذیری
برای بیشینه کردن ماژولاریته، باعث می شود انجمن های کوچک باهم تلفیق شده و انجمن های بزرگ را تشکیل دهند. زیرا وقتی انجمن A و B با هم ادغام می شوند، ماژولاریته شبکه با توجه به فرمول زیر تغییر می کند(مباحث پیشرفته 9B)

که در آن l_AB تعداد پیوندهایی از انجمن A با درجه کلی k_A که به گره هایی از انجمن B با درجه کلی k_B وصل می شوند. اگر A و B انجمن های محزا هستند وقتی Mبیشینه می شود باید از هم مجزا باشند. همانطور که در ادامه نشان داده می شود، همیشه این نکته صادق نیست.

شرایطی را در نظر بگیرید که k_Ak_B|2L < 1┤، یعنی شرایطی که فرمول (9.13) پیش بینی می کند اگر حداقل یک پیوند بین دو انجمن باشد یعنی (l_AB≥ 1 ) آنگاه ΔM_AB > 0. بنابراین برای بالارفتن ماژولاریته باید A و B را با هم ادغام کنیم. برای ساده تر شدن فرض کنید k_A ~ k_B= k، برای درجه کلی انجمن ها فرمول (9.14) برقرار است

پس با ادغام A و B ماژولاریته افزایش می یابد، حتی اگر A و B انجمن های مجزا باشند. این مساله ماژولاریته بیشین ساختگی است: اگر k_A و k_B زیر آستانه (9.14) باشند، تعداد پیوند های مورد انتظار بین آنها کمتر از 1 است. بنابراین وقتی M را بیشینه می کنیم حتی یک پیوند بین دو انجمن، آنها را مجبور می کند تبدیل به یک انجمن شوند. این محدودیت در تفکیک پذیری چندین پیامد دارد:

• بیشینه سازی ماژولاریته نمی تواند انجمن هایی که کوچکتر از محدوده تفکیک چذیری است را تشخیص دهد(9.14). برای مثال در وب با L=1497134 (جدول 2.1) بیشینه سازی ماژولاریته در تشخیص انجمنهایی با درجه کلی k_C ≲ 1,730 به مشکل بر می خورد.
• شبکه های واقعی از چندین انجمن کوچک تشکیل شده اند[36-38]. با وجود محدودیت های تفکیک پذیری (9.14) بطور سیستمی، این انجمن های کوچک بالاجبار به انجمن های بزرگتر جذب می شوند که ساختار انجمنی شبکه را به اشتباه توصیف می کنند.

برای پیشگیری از محدودیت های تفکیک پذیری می توانیم انجمن های بزرگی که با استفاده از ماژولاریته بهینه شده بدست آمده اند را به بخش های بیش تری تقسیم کنیم [33,34,39]. برای مثال با درنظر گرفتن کوچکترین گروه از دو گروه مواد متراکم در شکل 9.17a به عنوان شبکه مجزا و اعمال الکوریتم حریصانه روی آن، حدود 100 انجمن کوچکتر بدست می آید و ماژولاریته به M=0.807 افزایش می یابد (شکل 9.17b) [33].

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

شبکه ای متشکل از n_c زیر گراف با چگالی پیوند قابل ملاحظه k_C ≈ 2L/n_cرا در نظر بگیرید. بهترین افراز زمانی اتفاق می افتد که هر خوشه به انجمن متمایزی تعلق داشته باشد (شکل 9.18a) یعنی حالتی که M=0.867. با این حال خوشه های مجاور را در یک انجمن ادغام کنیم ماژولاریته بیش تری بدست می آید M=0.87 (شکل 9.18b). به طور کلی در (9.13) و (9.14) پیش بینی می شود که اگر دو خوشه با هم ادغام شوند ماژولاریته به اندازه زیر تغییر می کند

به عبارت دیگر، کاهش در ماژولاریته کمتر از ΔM = −2/n_c² خواهد بود. در شبکه ای با n_c = 20 این تغییرات حداکثر ∆M=-05 می شود که در مقایسه با ماژولاریته بیشینه M ≃ 0.87 (شکل 9.18b) بسیار کوچک است. هرچه تعداد گروه ها بیشتر شود ΔM_ij به سمت صفر میل می کند، و با همین روند تمایز بین افراز بهینه و افراز های نیمه بهینه بسیار که اختلاف چندانی با M_maxندارند دشوار تر می شود. به عبارت دیگر تابع ماژولاریته در اطراف افراز بهینه دارای قله نیست، بلکه سطح هموار مرتفعی دارد(شکل 9.18d).

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

همچنین، ماژولاریته چندین محدودیت مهم دارد: اول، انجمن های کوچکی که ارتباطات ضعیفی بین آنها است را با هم ادغام می کند. دوم، شبکه ها ماژولاریته بیشینه مشخصی ندارند که باعث ایجاد سطح مسطحی می شود که تشخیص ماژولاریته دشوار خواهد بود. این سطح هموار نشان می دهد چرا تعداد کثیری از الگوریتم های بیشینه سازی ماژولاریته به سرعت افراز M بیشینه را پیدا می کنند: آنها یکی از چندین افرازی که نزدیک به افراز بهینه M است را پیدا می کنند. در نهایت محاسبات تحلیلی و شبیه سازی های عددی نشان می دهند که برخلاف فرضیه H₃ که مفهوم ماژولاریته را بیان کرد، حتی شبکه های تصادفی هم افراز با ماژولاریته بیشینه دارند[41-43].

بهینه سازی ماژولاریته نمونه خاصی از مساله بزرگتری است: پیدا کردن انجمن ها با بهینه سازی تابع کیفیت Q. الکوریتم حریصانه و الکوریتم لووین که در مباحث پیشرفته 9.C توضیخ داده شده است، برای پیدا کردن ماژولاریته بیشینه فرض بر این است که Q=M. در مباحث پیشرفته 9.C همچنین الگوریتم اینفومپ توضیح داده شده است. این الگوریتم برای پیدا کردن انجمن ها از کمینه کردن معادله نگاشت M که معیاری مبتنی بر بی نظمی در کیفیت افراز است استفاده می کند[44-46].

بخش 9.5
انجمن های هم پوشان

معمولا به ندرت پیش می آید که گره ای تنها به یک انجمن تعلق داشته باشد. برای مثال دانشمندی را در نظر بگیرید که در جامعه ای از دانشمندان، علایق تحقیقاتی خود را به اشتراک می گذارند. همین فرد در انجمنی از خانواده و خویشاوندان هم عضو است، احتمالا در انجمن دیگری هم عضو است که سرگرمی هایش را به اشتراک می گذارد (شکل 9.19). در هر کدام از این انجمن ها افرادی وجود دارند که در چندین انجمن دیگر هم عضو هستند، درنتیجه شبکه پیچیده ای از انجمن های تو در تو و هم پوشان ایجاد می شود[36]. انجمن های هم پوشان تنها منحصر به سیستم های احتماعی نیست: معمولا ژن های مشابه در بیماری های بسیاری درگیر هستند، که نشان می دهد عوامل بیماری اختلالات مختلف با هم همپوشانی دارند[14].

در حالی که از مدت ها پیش ساختار انجمن های تودرتو مورد توجه جامعه شناسان جامعه مهندسان علاقه مند به افراز گراف ها بوده است، در تمام الگوریتم هایی که تا کنون مورد بحث بوده اند، هر گره تنها به یک انجمن تعلق دارند. تاماس وینسک و همکارانش [36,48] الگوریتمی برای تشخیص انجمن های هم پوشان ارائه دادند و کار آنها نقطه عطفی بود برای جلب توجه جامعه دانشمندان حوزه علم شبکه به این مساله. در این بخش دو الگوریتم مورد استفاده برای تشخیص الگوریتم های هم پوشان به نام تاثیرگذاری خوشه و خوشه بندی لینک.

تاثیرگذاری کیلیک

الگوریتم تاثیرگذاری که گاهی Cfinder هم نامیده می شود، هر انجمن را به صورت اجتماعی از کیلیک های هم پوشان در نظر می گیرد[36]:

• دو K-کیلیک با هم مجاور هستند اگر K-1 گره مشترک داشته باشند(شکل 9.20b).
• انجمن K-کیلیکی، بزرگترین زیرگراف همبند است که از اجتماع تمام K-کیلیک های مجاور بدست آمده است(شکل 9.20c).
• K-کیلیکی که از K-کیلیک مشخصی قابل دسترسی نیست به انجمن K-کیلیک دیگری تعلق دارد(شکل 9.20c,d).

الگوریتم CFinder تمام کیلیک ها را تشخیص می دهد و ماتریسO همپوشانی کیلیک-کیلیک N_clique x N_clique را تشکیل می دهد، N_clique تعداد کیلیک ها و O_ij تعداد گره های مشترک بین کیلیک های i و j است(شکل 9.39). خروجی الگوریتم CFinder که ساختار انجمنی کلمه روشنایی را نشان می دهد در شکل 9.21 نشان داده شده است. در شبکه بین دو کلمه پیوند برقرار می شود اگر آنها معانی مرتبط به هم داشته باشند. به راحتی می توان فهمید که انجمن های هم پوشانی که بوسیله الگوریتم تشخیص داده شده اند، مفهوم خاصی دارند: کلمه روشنایی هم زمان به انجمن کلمه های مرتبط با نورمثل درخشان یا تاریک، انجمن کلمه های تعیین کننده رنگ(زرد، قهوره ای)، انجمن عبارات مرتبط با نجوم(خورشید، اشعه) و انجمن کلمه های مرتبط با هوش (با استعداد، خوش ذوق) تعلق دارد. این مثال مشکلات الگوریتم های ابتدایی در تشخیص انجمن های این شبکه را نشان می دهد: الگوریتم های ابتدایی، بالاجبار کلمه روشنایی را در یکی از چهار انجمن قرار می دهند و سه تای دیگر را حذف می کنند.

آیا الگوریتم هایی که با CFinder تشحیص داده می شوند، ممکن است به طور تصادفی ایجاد شوند؟ برای تشخیص انجمن های k-کیلیکی واقعی از انجمن هایی که تنها حاصل تراکم بالای پیوند ها هستند، ویژگی های تاثیرگذاری k-کیلیک ها در شبکه های تصادفی را جستجو می کنیم[48]. همانطور که در فصل 3 بیان شد، اگر شبکه ای تصادفی به اندازه کافی چگال باشد، چندین کیلیک از مرتبه های مختلف خواهد داشت. انجمن k- کیلیکی بزرگ تنها زمانی در شبکه های تصادفی ایجاد می شود که احتمال پیوند P از حد آستانه ای بیشتر شود. (مباحث پیش رفته 9.D)

با توجه به p_c (k) تنها تعداد کمی k-کیلیکی مجزا مورد انتظار است(شکل 9.22a). به محض اینکه p از p_c(k) بیشتر شود چندین کیلیک ظاهر می شوند که انجمن های k-کیلیکی را تشکیل می دهند(Image 9.22b). به عبارت دیگر هر انجمن k-کیلیکی آستانه خودش را دارد:

• در k=2، k-کیلیک ها در واقع همان پیوند ها هستند و فرمول (9.16 ) به p_c(k)~1/Nکاهش می یابد که همان شرط مولفه های همبند غول آسا در شبکه اردوش-رینی است.
• در k=3، کیلیک ها مثلث هستند(شکل 9.22a,b) و(9.16) برای این حالت پیش بینی می کنند p_c(k)~1/√2N

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

پیچیدگی محاسباتی
برای پیدا کردن کیلیک های در شبکه ها نیاز به الگوریتم هایی است که زمان اجرای آنها با N بصورت نمایی رشد می کند. ولی تعریف انجمن در CFinder براساس کیلیک هاست نه کیلیک بیشینه، که این مساله هم در زنان چند جمله ای قابل تشخیص است[49]. اگر در شبکه ای کیلیک های بزرگ وجود دارد، بهتر است تمام کیلیک ها را با استفاده از الگوریتم با پیچیدگی O(e^N) تشحیص دهیم [36]. به رغم پیچیدگی محاسباتی بالا، این الگوریتم نسبتا سریع است طوری که شبکه تلفن های همراه شامل 4میلیون کاربر را در کمتر از یک روز پردازش می کند( شکل 9.28را هم ببینید) [50].

خوشه بندی پیوند

هرچند گره ها معمولا به چند انجمن تعلق دارند، پیوند ها معمولا منحصر به یک انجمن هستند و ارتباطات دقیقی را نشان می دهد که عضویت گره ها در انجمن ها را تعریف می کند. برای مثال، پیوندی بین دو فرد ممکن است نشان دهد آنها با هم خویشاوند هستند یا به هم کار می کنند و یا سرگرمی مشترکی دارند ، طرحی که ندرتا هم پوشانی دارد. به طور مشابه در زیست شناسی، هر برهم کنش بین پروتئین ها عامل کارکردهای مختلفی هستند، که تعریف انحصاری از نقش پروتئین در سلول ارائه می دهد. انحصاری بودن پیوند ها، الهام بخش الگوریتم های تشخیص انجمن هاست که بجای خوشه بندی گره ها، پیوند ها را خوشه بندی کنند[51,52].

الگوریتم خوشه بندی پیوند که توسط آن ، باگروو و لمان ارائه شده، شامل گام های زیر است:

گام اول: تعریف شباهت پیوند ها
شباهت دو پیوند، براساس گره های مجاوری که توسط آنها به هم متصل شده اند تعریف می شود. برای مثال پیوند های (I,k) و (j,k) را که هر دو به گره مشابه kمتصل شده اند را درنظر بگیرید. شباهت آنها به صورت زیر تعریف می شود(شکل 9.23a-c)

در این فرمول n₊(i) لیست گره های همسایه گره i و خود i است. بنابراین S تعداد نسبی همسایه های مشترک i و j را محاسبه می کند. در نتیجه S=1 اگر iو j همسایه های مشابه داشته باشند(شکل 9.23c). هرچه هم پوشانی همسایه های دو پیوند کمتر باشد، S کوچکتر می شود(شکل 9.23b).

گام دوم: اعمال خوشه بندی درختی
ماتریس شباهت S امکان استفاده از خوشه بندی سلسله مراتبی را به منظور تشخیص انجمن های پیوندی فراهم می کند(بخش 9.3). از فرایند تک پیوندی استفاده می کنیم، بصورت تکراری انجمن هایی که دو پیوند با بیشترین شباهت دارند را باهم ادغام می کنیم(شکل 9.10).

در نهایت برای شبکه شکل 9.23e ماتریس شباهت نشان داده شده در (d) بدست می آید. خوشه بندی سلسله مراتبی تک پیوندی، نمودار درختی که در (d) نشان داده شده را ایجاد می کند که برش های آن انجمن های پیوندی شکل (e) و انجمن های گره ای همپوشان در (f) را نشان می دهد.

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

پیچیدگی محاسباتی
الگوریتم خوشه بندی پیوندی داری دو گام است که محدودیت زمانی ایجاد می کنند: محاسبه شباهت و خوشه بندی سلسله مراتبی. برای محاسبه شباهت یک جفت پیوند از درجه k_i و k_j براساس فرمول (9.17) به max(k_i,k_j) گام نیاز است. در شبکه مقیاس آزاد با درجه توان γ پیچیدگی محاسباتی شباهت از مرتبه O(N^2/(γ-1)) است که با سایز بزرگترین گره،k_max،تعیین می شود. خوشه بندی سلسله مراتبی به O(l2) گام زمانی نیاز دارد. بنابراین پیچیدگی محاسباتی کلی الگوریتم O(N^2/(γ-1))+ O(L²) است. در گراف های خلوت، عبارت دوم قابل چشم پوشی خواهد بود و پیچیدگی محاسباتی بصورت O(N²) در می آید.

نیاز به تشخیص انجمن های هم پوشان الهام بخش الگوریتم های بسیاری بوده است [53]. برای مثال الگوریتم CFinder برای تحلیل گراف های وزن دار [54]، جهت دار و دو بخشی [55,56]توسعه یافته است. بطور مشابه می توان همانند تابع ماژولاریته که در در بخش 9.4 بحث شد [52]، تابع کیفیت هم تعریف کرد.

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

بخش 9.6
انجمن های آزمایشی

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

دقت

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

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

معیار گیروان-نیومن(GN)
معیار گیروان-نیومن شامل N=128 گره است که به n_c=4 انجمن با سایز N_c=32 گره تقسیم شده است[9,57]. هر گره با احتمال p^int بهN_c – 1 گره از انجمن خودش و با احتمال p^ext به3N_c گره از انجمن های دیگر متصل شده است. برای کنترل پارامتر ها

تفاوت تراکم را داخل انجمن ها و بین انجمن ها نشان می دهد. انتظار می رود به ازای μ کوچک وقتی احتمال اتصال گره های داخل انجمن ها از احتمال اتصال گره های انجمن های مختلف بیشتر شود، الگوریتم های تشخیص انجمن ها کارایی خوبی داشته باشند(شکل 9.25aa). کارایی همه الگوریتم ها باید برای μ بزرگ(شکل 9.25b) یعنی وقتی که تراکم داخل انجمن ها نسبت به تراکم بین انجمن ها چشم گیر است، کاهش پیدا کند.

معیار لانچیچینتی ، فورتوناتو ،رادیکچی (LFR)
معیار GN گراف تصادفی ایجاد می کند که در آن همه گره ها درجه های نزدیک به هم دارند و سایز آنها با هم برابر است. اما همچنان توزیع درجه در شبکه های واقعی و توزیع اندازه انجمن، توزیع دنباله بزرگ است (شکل 9.29). بنابراین الگوریتمی که روی معیار GN کارایی خوبی دارد لزوما در شبکه های واقعی دارای کارایی بالا نیست. برای پرهیز از این محدودیت ها، معیار LFR (شکل 9.26) شبکه هایی را ایجاد می کند که هم درجه گره ها و هم انجمن های مستقر شده از قانون توان پیروی می کنند[58].

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

اندازه گیری دقت
برای مقایسه انجمن های پیش بینی شده و آنهایی که در معیار مستقر شده اند، تعداد دلخواهی افراز را در انجمن های غیر هم پوشان در نظر بگیرید. در هر گام، گره ای انتخاب می شود و انجمنی که به آن تعلق دارد برچسب زده می شود. حاصل این کار رشته ای تصادفی از برچسب انجمن هاست که از توزیع P(C) پیروی می کنند. P(C) احتمال اینکه گره ای که بطور تصادفی انتخاب شده به انجمن C تعلق داشته باشد را نشان می دهد.

دو افراز از یک شبکه را درنظر بگیرید، یکی افراز معیار و دیگری افراز پیش بینی شده توسط الگوریتم تشخیص انجمن. هر کدام از افراز ها توزیع p(C₁) و p(C₂) خود را دارند. توزیع اشتراکp(C₁, C₂) ، احتمال اینکه گره ای که بطور تصادفی انتخاب شده به انجمنC₁ در افراز اول و به انجمن C₂ در دومی تعلق داشته باشد را نشان می دهد. شباهت دو افراز با نرمال سازی اطلاعات متقابل تعیین می شود[38]

صورت کسر (9.19) همان اطلاعات متقابل I است. که اطلاعاتی که بین دو انحمن به اشتراک گذاشته می شود را انداره گیری می کند: I=0 اگر C₁و C₂مستقل از یکدیگر باشند؛ اگر دو افراز مشابه هم باشند و نظریه شانون هم برقرار باشد، I برابر مقدار بیشینه H({p(C₁)}) = H({p(C₂)}) می شود.

اگر همه گره ها به یک انجمن تعلق داشته باشند، به طور قطع برچسب بعدی مشخص است و H=0، زیرا هیچ اطلاعات جدیدی با بررسی انجمنی که گره بعدی به آن تعلق دارد بدست نمی آوریم. اگر p(C) توزیع یکنواخت باشد، H بیشینه خواهد بود، زیرا در این حالت مشخص نیست کدام انجمن بعدی خواهد بود و هر کدام از گره ها H بیت اطلاعات جدید ایجاد میکنند

بطور خلاصه، اگر معیار و انجمن های تشخیص داده شده مشابه باشند، I_n=1، اگر از هم مستقل باشند، I_n=0. مزیت I_n در شکل 9.25b نشان داده شده است. در این شکل دقت الگوریتم راواسز برای معیار گیروان-نیومن نشان داده شده است. در شکل 9.27 از I_n استفاده شده است تا کارایی هر کدام از الگوریتم ها در مقابل معیار های GN و LFR نشان داده شود. از این نتایج می توان چندین نتیجه گرفت:

• اگر به ازایμ<0.5 داشته باشیم I_n≃1، در نتیجه وقتی تراکم پیوند ها داخل انجمن ها در مقابل اطرافیانش بیشتر باشد، بیشتر الگوریتم ها انجمن های مستقر شده را به درستی تشخیص می دهند. بیشتر از μ=0.5 دقت هر کدام از الگوریتم ها کاهش می یابد.
• دقت وابسته به معیار است. برای بیشتر معیار های LFR واقعی، روش اووین و راواسز بهترین کارایی و ماژولاریته حریصانه ضعیف عمل می کند.

سرعت

همانطور که در بخش 9.2 بحث شد، تعداد افراز های ممکن بصورت نمایی نسبت به N افزایش می یابد که برای شبکه های واقعی مقدار نجومی خواهد داشد. با اینکه الگوریتم های تشخیص انجمن تمام افراز ها را چک نمی کنند، همچنان هزینه محاسباتی آنها تنوع گسترده ای دارد و سرعت و سایز شبکه ای که می تواند روی آن کاربرد داشته باشد را مشخص می کند. جدول 9.1 پیچیدگی محاسباتی الگوریتم هایی که در این فصل بحث شدند را بطور خلاصه نشان می دهد. طبق این جدول، الگوریتم لووین و اینفو مپ بهتر از بقیه هستند و هر دو از مرتبه O(NlogN) هستند. بدترین الگوریتم هم CFinder است که از مرتبه 0(e^N) است.

هرچند، این قانون مقیاس بندی کردن زمان اجرای واقعی را نشان نمی دهد. تنها نشان می دهند زمان اجرا با چه نسبتی از N تغییر می کند. در زمان تشخیص انجمن ها در شبکه های خیلی بزرگ، این مقیاس بندی اهمیت پیدا می کند. برای اینکه درک درستی از سرعت واقعی این الگوریتم ها بدست آید، زمان اجرای آنها روی شبکه برهم کنش پروتئینی (N=2.18)، شبکه برق (N=4941) و شبکه همکاری های علمی (N=23133) با استفاده از کامپیوتر های مشابه اندازه گیری شده است. نتایج در شکل 9.28 آمده است و نشان می دهد که:

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

In summary, benchmarks allow us to compare the accuracy and the speed of the available algorithms. Given that the development of the fastest and the most accurate community detection tool remains an active arms race, those interested in the subject should consult the literature that compares algorithms across multiple dimensions [31,58,60,61].

بخش 9.7
توصیف شبکه ها

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

توزیع اندازه انجمن ها

طبق فرضیه اصلی (H1) تعداد و سایز انجمن ها در شبکه به وسیله نمودار ارتباطات شبکه منحصرا مشخص می شود. این سوال پیش می آید که: توزیع اندازه این انجمن ها چیست؟

بسیاری از مطالعات، توزیع دنباله کشیده را برای سایز انجمن ها گزارش داده اند و اذعان دارند که چندین انجمن کوچک به همراه تعداد کمی انجمن خیلی بزرگ با هم وجود دارند[16,33,35,36,60]. برای بررسی میزان گستردگی این مساله در شکل 9.29 p_Nc پیش بینی شده توسط الگوریتم های تشخیص انجمن متفاوت برای سه شبکه نشان داده شده است. این نمودار ها چندین الگو را نشان می دهند:

• در شبکه تعاملات پروتئینی و همکاری علمی، همه الگوریتم ها تقریبا دنباله کشیده ای از p_Nc را نشان می دهند. بنابراین در این انجمن ها چندین انجمن کوچک با تعداد کمی انجمن بزرگ وجود دارد.
• در مورد شبکه برق، الگوریتم های مختلف خروجی های متفاوتی داشتند. الگوریتم های مبتنی بر ماژولاریته انجمن هایی در حدود N_c ≃ 10²را پیش بینی کردند. در مقابل الگوریتم راواسظ و اینفومپ چندین انجمن با سایز N_c ≃ 10 و تعداد کمی انجمن بزرگتر تشخیص می دهند. در نهایت الگوریتم های تاثیر کیلیک و خوشه بندی پیوندی تقریبا توزیع اندازه دنباله کشیده را پیش بینی می کنند.

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

انجمن ها و وزن پیوند ها

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

شبکه های اجتماعی
هرچه زمانی که دو فرد با هم سپری می کنند بیشتر باشد، احتمال اینکه دوستان مشترکی داشته باشند بیشتر می شود و همین مساله شانس اینکه هر دو به یک انجمن تعلق داشته باشند هم بیشتر می شود. بنابراین، جوامع در شبکه های اجتماعی تمایل به ایجاد روابط قوی دارند. اما در مقابل پیوند هایی که انجمن های مختلفی را به یکدیگر پیوند می دهند ضعیف تر هستند. این الگو، نظریه رابط ضعیف نامیده می شود [62] و در شکل 9.30a برای شبکه تلفن های همرا نشان داده شده است [63]. واضح است که رابط های قوی غالبا داخل چندین انجمن کوچک هستند و پیوند هایی که انجمن ها را به هم متصل می کنند آشکارا ضعیف تر هستند.

سیستم های انتقال
هدف بسیاری از شبکه های تکنولوژی یا زیستی انتقال مواد با اطلاعات است. در این حالت انتظار می رود وزن پیوندها با مرکزیت بینابینی که نماینده ای از حجم بار انتقال یافته در شبکه بصورت محلی است، ارتباط داشته باشد [64,65,66]. از آنجایی که پیوندهایی که انجمن های مختلف را به هم متصل می کنند باید بار قابل توجهی را انتقال دهند، در شبکه های انتقال رابط های قوی بین انجمن ها قرار دارند. در مقابل، پیوند های داخل انجمن ها ضعیف تر هستند(Image 9.30b).

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

تکامل انجمن

تغییر در نمودار ارتباطات شبکه، پیامدهای بسیاری برای انجمن ها خواهد داشت: می توانند باعث ایجاد انجمن های جدید، رشد یا کوچک شدن انجمن های موجود، ادغام انجمن ها یا تفکیک آنها و از بین رفتن انجمن ها شوند(شکل 9.31) [50]. مطالعات انجام شده روی شبکه های اجتماعی و ارتباطی دید وسیعی از تجربیات حاصل از تغییر انجمن ها می دهند [50,67-73]:

رشد
احتمال اینکه یک گره به انجمنی بپیوندد با تعداد پیوند هایی که آن گره با انجمن دارد افزایش می یابد [73].

کوچک شدن
گره هایی که پیوند های کمی با اعضای انجمن خود دارند با احتمال بیشتری از انجمن جدا می شوند تا گره هایی که پیوند های زیادی با اعضای انجممن خود دارد [73]. در شبکه های وزن دار، احتمال اینکه گره ای از انجمن جدا شود با جمع وزن پیوند ها به سایر انجمن ها افزایش می یابد.

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

سن
ارتباط مستقیمی بین سن و سایز انجمن وجود دارد. یعنی انجمن های قدیمی تر احتمالا بزرگتر هم هستند.

پایداری انجمن
اعضای انجمن های بزرگتر سریعتر از اعضای انجمن های کوچکتر تغییر می کنند. همچنین در شبکه های اجتماعی، انجمن های بزرگ معمولا به موسسات، شرکت ها و سازمان ها تعلق دارند که آنها هم با پذیرش اعضای جدید، استخدام کارمندان یا ثبت نام دانش آموزان جدید، نو می شوند. در انجمن های کوچک برای داشتن پایداری باید اعضای آنهاهم ثابت باشند [50].

این نتایح براساس محتوای سیستم های اجتماعی بدست آمده اند. درک ما از الگو ها و دربرگیری تکامل شبکه ها در سیستم های تکلنولوژی یا زیستی همچنان محدود است.

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

بخش 9.8
خلاصه

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

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

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

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

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

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

آیا انجمن ها اهمیت دارند؟
از یک مثال برای پاسخ به این پرسش استفاده می کنیم. شکل 9.32a همسایه های محلی شبکه تماس های تلفن همراه را نشان می دهد. در این شکل چهار انجمنی که با استفاده از الگوریتم خوشه بندی پیوند شناسایی شده اند، نشان داده شده است(شکل 9.5). همچنین این شکل تکرر تماس ها در طهر (b)، شب (c) را نشان می دهد تا عادت های تماس تلفنی در ساعات مختلف روز را ثبت کند. می توان فهمید که اعضای انجمن بالا سمت راست که با گره های قهوه ای رنگ در (a) نشان داده شده اند، در نیمه شب(b) فعال هستند، اما تماس با یکدیگر را در ظهر قطع می کنند(c). در مقابل انجمن های آبی روشن و تیره در ظهر فعال هستند و در نیمه شب می خوابند. این مثال نشان می دهد انجمن هایی که تنها براساس نمودار اتصالات شبکه تشخیص داده می شوند، الگوی فعالیت منسجمی دارند که مختص همین انجمن است

شکل 9.32 بیان می کند که به محض اینکه در شبکه ای انحمن تشکیل شود، تاثیر چشم گیری روی رفتار شبکه خواهد داشت. معیار های زیادی این نتیجه گیری را تایید می کنند: اطلاعات داخل انجمن ها سریع حرکت می کنند ولی انتقال آنها بین انجمن ها دشوار است [63]. انجمن ها روی وزن پیوند ها تاثیر گذار هستند[62]؛ وجود انجمن ها می تواند همبستگی درجه ای ایجاد کند[74].

اهمیت انجمن ها از نظر کارایی برابر است. برای مثال، تقویت پیوند های شبکه وب بین مشتریانی که به یک انجمن تعلق دارند می تواند بازدهی خدمات مبتنی بر وب را افزایش دهد[75]. در بازاریابی، تشخیص انجمن ها می تواند در تشخیص مشتریان با علایق مشابه یا عادات خرید مشابه کمک کند که با استفاده از آن می توان سیستم های توصیه گر محصولات با کارایی بالا را طراحی کرد[76]. انجمن ها برای ایجاد ساختار داده ای که در پس بسیاری از شبکه های اجتماعی در حال اجرا هستند، استفاده می شوند، شبکه هایی مثل فیس بوک، توییت یا لینکدین. انجمن ها به این سرویس ها کمک می کنند دوست های احتمالی، مطالب مورد علاقه و اهداف تبلیغاتی را شناسایی کنند.

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

بخش 9.9
تمرین ها

1. شبکه های سلسله مراتبی

   توان درحه شبکه سلسله مراتبی نشان داده شده در شکل 9.33 را محاسبه کنید. .

   

2. انجمن ها و حلقه ها

   طوری منظم یک بعدی با N گره را در نظر بگیرید که یک دایره تشکیل می دهد، یعنی هر گره به همسایه اش متصل می شود. این خط را به n_c خوشه متوالی با سایز N_c=N/n_c افراز کنید.

   1. ماژولاریته افراز بدست آمده را محاسبه کنید
   2. طبق فرضیه ماژولاریته بیشینه(بخش 9.4)، بیشترین به بهترین M_c افراز تعلق دارد. سایز انجمن n_c که مربوط به بهترین افراز است را محاسبه کنید.
   3. محدودیت های تفکیک پذیری ماژولاریته
   
   

3. شبکه ای شامل حلقه ای با n_c کیلیک را را درنظر بگیرید که هر کیلیک N_c گره و m(m-1)/2 پیوند دارد. کیلیک های مجاور با تنها یک پیوند به هم متصل می شوند(شکل 9.34). شبکه ساختار انجمنی واضحی دارد، هر انجمن یک کیلیک را نشان می دهد.

   1. M_single مربوط به افراز طبیعی و M_pairs که در آن هر جفت از کیلیک های مجاور با هم ادغام شده و یک شبکه را تشکیل می دهند و در شکل 9.34هم با خط چین نشان داده شده اند، را حساب کنید.
   2. نشان دهید که تنها برای n_c < 2L ماژولاریته بیشنیه می تواند افراز انجمنی که بصورت چشمی درست است را پیش بینی کند یعنی $L = n_c m(m - 1)/2 + n_c$
   3. درمورد نتایج عدم رعایت فرمول بالا بحث کنید
   
   
4. ماژولاریته بیشینه

   نشان دهید ماژولاریته بیشینه که در (9.12) تعریف شده است نمی تواند بیشتر از یک شود.

بخش 9.10
مباحث پیشرفته 9.A
شمارش افراز ها

در این بخش به بحث در مورد ویژگی مقیاس پذیری مدل سلسله مراتبی که در شکل 9.13 معرفی شد می پردازیم. با استفاده از فرمول (9.8) توزیع درجه و ضریب خوشه بندی وابسته به درجه را حساب می کنیم. در نهایت وجود سلسله مراتب را در 10 شبکه واقعی بررسی می کنیم.

توزیع درجه
برای محاسبه توریه درجه مدل، باید تعداد گره ها با درجه های مختلف را شمارش کرد. با شروع از پنج گره مدلی که در شکل 9.13a نشان داده شده، گره وسط را به عنوان هاب درنظر می گیریم و چهار گره باقی مانده را به عنوان گره های جنبی در نظر می گیریم. تمام کپی های این هاب همچنان هاب و کپی گره های جنبی هم، همان جنبی نامیده می شوند(شکل 9.35). (شکل 9.35).

طی n تکرار، بزرگترین هاب n⁴ پیوند برقرار می کند. این هاب را H_n و چهار کپی این هاب را H_(n-1) نام گذاری می کنیم (شمل 9.35). 4() ̇5 مرکزماژول باقیمانده که اندازه آنها برابر با اندازه شبکه در تکرار n-1 است را H_(n-2) می نامیم.

در تکرار nام درجه هاب H_i بصورت زیر است

که از فرمول زیر استفاده می شود

یا

به ازای i < n تعداد ماژول های H_i به این صورت است

برای مثال چهار ماژول به ازای i = n – 1، 4⋅5 ماژول به ازای i = n – 2، ...، و4 · 5 ^n–2 ماژول به ازای i=n وجود دارد. از آنجایی که ^n–i–1 ماژول از هاب نوع H_i با درجه k_n (H_i ) وجود دارد با استفادع از (4.35) و (4.38) می توان نوشت: $\ln N_n (H_i ) = C_n - i \cdot \ln 5 \hspace{20 mm} (9 . 39)$ $\ln k_n (H_i ) \simeq i \cdot \ln 4 + \ln (4/3) \hspace{20 mm} (9 . 40)$

که در آن

توجه کنید که در فرمول (9.40) از تقریب ⁱ–1≃4ⁱ استفاده شده است.

به ازای تمام k>n+2 می توان (9.40) و (9.41) را ترکیب کرد و فرمول زیر بدست می آید

or

برای محاسبه توزیع درجه باید با محاسبه نرخ زیر، N_n(H_i) را نرمال کنیم.

با استفاده از

به فرمول زیر می رسیم

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

ضریب خوشه بندی
گاهی محاسبه ضریب خوشه بندی هاب های H_i ساده است. Σⁱ_l=14^l پیوند آنها از گره هایی می آیند که بصورت دایره ای به هم متصل هستند، بنابراین تعداد ارتباطات بین آنها برابر با تعداد خودشان است. بنابراین تعداد پیوند ها بین همسایه های H_i برابر است با:

که فرمول زیر نتیجه می شود

به عبارت دیگر

که نشان می دهد C(k) با مقیاس k^–1 متناسب با فرمول (9.8) تعیین می شود.

نتایج تجربی
شکل 9.36 تابع C(k) ده شبکه مرجع را نشان می دهد. همچنین C(k) این شبکه ها بعد از اعمال تصادفی سازی حفط درجه (نماد های سبز رنک) نشان داده شده است، که با استفاده از آنها می توان مطالب زیادی را دریافت کرد:

• همه شبکه ها مرتبه ای از بزرگ نمایی بالاتر از C(k) نسبت به معادل تصادفی خود دارند. بنابراین گره های با درجه پایین تر نسبت به انتخاب تصادفی، در همسایگی پرتراکم تری قرار دارند.
• در شکبه همکاری های علمی، متابولیک و ارجاع دهی های با تقریب نسبتا خوبی C(k)~k^–1 ، در حالی که مدل تصادفی هموار است. بنابراین، این شبکه ها ماژولاریته سلسله مراتبیاز نوع مدل شکل 9.13 دارند.
• در شبکه های اینترنت، تماس های تلفن همراه، بازیرگران، پست الکترونیکی، برهم کنش پروتئینی و وب، C(k) با k کاهش پیدا می کند در حالی که در نمونه تصادفی آنها C(k) از k مستقل است. بنابراین، درحالیکه این شبکه ها ماژولاریته سلسله مراتبی را نشان می دهند، C(k) بدست آمده با مدل سلسله مراتبی ساده ما قابل مشاهده نیست. برای اینکه C(k) این سیستم ها را برازش کنیم نیاز به مدل هایی است که دقیقا اعتبار آنها را مشخص کنند. این مدل های پیش بینی می کنند C(k)~k^–βکه β می تواند با یک متفاوت باشد [27].
• تنها در شبکه برق، C(k) هموارو مستقل از k مشاهده می شود. و همین نکته نشان دهنده عدم وجود ماژولاریته سلسله مراتبی است.

در نهایت، شکل 9.36 نشان می دهد که بیشتر شبکه های واقعی، ماژولاریته سلسله مراتبی کلی را نشان می دهند.

بخش 9.11
مباحث پیشرفته 9.C
ماژولاریته

در این بخش از تعریف های (9.12) و (9.13) استفاده کرده تا مشخصات تابع ماژولاریته و تغییراتش را مشخص کنیم.

ماژولاریه به عنوان مجموع انجمن ها
با استفاده از فرمول های (9.9) و (9.10) می توانیم ماژولاریته کل شبکه را بصورت زیر بنویسیم:

که C_i برچسب انجمنی است که گره i به آن تعلق دارد. از انجایی که تنها جفت گره هایی که متعلق به یک انجمن باشند در جمع فرمول (9.37) شرکت می کنند، می توانیم اولین عبارت را بصورت جمع تمام انجمن ها در نظر بگیریم.

که L_c تعداد پیوند ها در انجمن C_c را نشان می دهد. از آنجایی که هر پیوند در A_ij دو بار شمارش می شود، فاکتور 2 حذف می شود.

با روش مشابه عبارت دوم (9.37) بصورت زیر در می آید

که k_c جمع تمام گره ها در انجمن C_c است. همچنین در مدل پیکر بندی احتمال اینکه یک عضو کوچکی که درجه کمی دارد که به طور تصادفی انتخاب شده است به عضو کوچک دیگری متصل شود 1/2L است، زیرا به طور کلی 2L عضو کوچک می تواند در شبکه وجود داشته باشد. بنابراین احتمال اینکه عضو کوجک مورد نظر به عضو کوچک دیگری در داخل همین انجمن متصل شود k_c/2L است. با تکرار این روند برای تمام k_c عضو کوچک موجود در انجمن C_c و ضرب کردن در 2/1 برای جلوگیری از شمارش دوباره، عبارت آخر فرمول (9.39) بدست می آید.

با ترکیب (9.38) و (9.39) فرمول (9.12) بدست می آید.

ادغام دو انجمن
انجمن های A و B را درنظر بگیرید. k_A و k_B درجه کلی در این انجمن ها را نشان دهد(معادل که در بالا آمده است). می خواهیم با ادغام این دو انجمن، تغییر در ماژولاریته را حساب کنیم. با استفاده از فرمول (9.12)، این تغغیر بصورت زیر نوشته می شود

که در آن

l_AB تعداد پیوند های مستقیم بین گره های انجمن A و انجمن B را نشان می دهد و

با درج (9.41) و (9.42) در فرمول (9.40)، فرمول زیر بدست می آید

که همان فرمول (9.13) است.

بخش 9.12
مباحث پیشرفته 9.C
الگوریتم های سریع برای تشخیص انجمن

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

شباهت های بسیاری بین دو الگوریتم وجود دارد:

• هر دو در تلاش هستن تابع کیفیت Q را بهینه کنند. در الگوریتم لووین، Q ماژولاریته M است و در الگوریتم اینفو مپ معیار مبتنی بر بینظمی که معادلع نقشه یا L نامیده می شود، نقش را بازی می کند. .
• هر دو الگوریتم از رویه مشابهی برای بهینه سازی استفاده می کنند.

بعد از بیان مشابهت ها، در مورد دو الگوریتم بحث می کنیم.

الگوریتم لووین

پیچیدگی محاسباتی O(N²) د رالگوریتم حریصانه برای شبکه های خیلی بزرگ می تواند یک عامل بازدارنده باشد. الگوریتمی با بهینه سازی ماژولاریته و مقیاس پذیری بهتر توسط بلوندل و همکارانش ارائه شد[2]. الگوریتم لووین شامل 2 گام است که بصورت تکراری اجرا می شوند(شکل 9.37):

گام اول
با شبکه وزن داری با N گره شورع می شود. در ابتدا هر کدام از گره ها در اجمن ها متفاوتی قرار می گیرند. به ازای هر گره i تغییر در ماژولاریته را در صورتی که گره i را در انجمن یکی از همسایه هایش j قرار گیرد، را محاسبه می کنیم. سپس گره I به انجمنی منتقل می شود که بیشترین تغییر را دارد، البته اگر این تغییر مثبت باشد. اگر هیچ تغییر مثبتی وجود نداشته باشد، i در همان انجمن خودش باقی می ماند. این فراید تکرار می شود تا جایی که هیچ بهبود دیگری ممکن نباشد

تغییر در ماژولاریته ∆M که با انتقال یک گره تنها به انجمن C بدست می آید، بصورت زیر قابل محاسبه است

که Σ_in مجموع وزن پیوند های داخل C (همان L_C در شبکه های بدون ورن)، Σ_tot مجموع وزن پیوند ها به همه گره های داخل C، k_i مجموع وزن پیونهای متصل به گره I، k_i,in مجموع وزن پیوند ها از گره i به گره های داخل C و در نهایت، W مجموع وزن تمام پیوند های شبکه است.

در نظر داشته باشید که ∆M خالت خاصی از (9.13) است که تغییر ماژولاریته بعد از ادغام انجمن های A و B را محاسبه می کند. در این حالت B گره مجزایی است. وقتی i از انجمن مربوطه حذف شود برای تشخیص تغییرات در ماژولاریته می توان از ∆M استفاده کرد. در این حالت باید ∆M وقتی i با انجمن C ادغام، بعد از آنکه i را از آن خارج کردیم، حساب کنیم. بعد از حذف i تغییرات برابر -∆M است.

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

بعد از اتمام گام 2، گام 1و2 را مجددا تکرار می کنیم و به هر تکرار آنها یک گذر می گوییم(شکل 9.37). در هر گذر، تعداد انجمن ها کاهش پیدا می کند. تکرار تا جایی ادامه پیدا می کند که تغییر جدیدی حاصل نشود که در این حالت ماژولاریته بیشینه بدست آمده است.

پیچیدگی محاسباتی
بیشترین محدودیت الگوریتم لووین مربوط به حافظه مورد نیاز است تا زمان محاسبات. در گذر اول که زمانگیر تر است، مقیاس تعداد محاسبات بصورت خطی با L تغییر می کند. در گذر های بعدی با کاهش تعداد گره ها و پیوند ها، پیچیدگی الگوریتم حداکثر O(L) است. بنابراین می توان در شبکه ای از میلیون ها گره، انجمن ها را تشخیص داد.

اینفومپ

اینفومپ توسط مارتین رزول و کارل تی برگسترون معرفی شد و از فشردگی داده ها برای تشخیص انجمن ها استفاده می کند (شکل 9.38) [44-46]. برای این کار از بهینه سازی تابع کیفیت در تشخیص انجمن شبکه های جهت دار و وزن دار استفاده می کند که معادله نقشه نامیده می شود.

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

برای بدست آوردن این کد مسیر قرار داد های زیر را در نظر می گیریم:

• به هر انجمن یک کد داده می شود (دفترچه کد نمایه گذاری). برای مثال به انجمن بنفش رنگ در شکل 9.38c کد 111 داده می شود.
• به هر گره داخل انجمن یک کدواژه داده می شود. برای مثال، به گره بالا سمت چپ در ( C ) کد واژه 001 داده می شود. توجه کند کدواژه مشابه می تواند در انجمن دیگری استفاده شود
• کد هایی که قدم زن در یک انجمن علامت گذاری می کند، هنگام خروجش از انجمن، حذف کنید. مثل 0001 در انجمن بنفش رنگ در (C)

بنابراین هدف ساختن کدی است که مسیر قدم زن تصادفی را هرچه کوتاهتر توصیف کند. با بدست آمدن این کد، با خواندن دفترچه نمایه هایی که بصورت یکتا به هر انجمن اختصاص داده شده اند، می توان ساختار انجمن ها را بدست آورد (شکل 9.38c)

کد بهینه با معادله نقشه کمینه بدست می آید.

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

عبارت دوم هم میانگین بیت های لازم برای نشان دادن جابجایی داخل انجمن ها است. در اینجا H(P_c)بی نظمی حرکت های داخل انجمنی شامل کد خروج است تا خروج از انجمن i را نشان دهد.

عبارت های خاص معادله نقشه و محاسبات آنها در بدست آوردن احتمالات جابجایی های قدم زن تصادفی در اینجا مد نظر است و با جزئیات در مرجع های [44-46] مفصل توضیح داده شده است. منبع آنلاین 9.3 ابزاری تعاملی را نشان می دهد که برای نشان دادن مکانیزمی که در پس معادله (9.59) است و کاربردهای آن استفاده می شود.

در نهایت L در نقش تابع کیفیت عمل می کند و به هر افراز شبکه به انجمن ها مقداری را اختصاص می دهد. برای بدست آوردن بهترین افراز باید L به ازای تمام افراز های ممکن کمینه شود. رایج ترین شیوه برای بهینه سازی، همان گام های یک و دو الگوریتم لویین هستند: هر گره به یک انجمن مجزا اختصاص داده می شود، و هر دو گره مجاور در صورتی که ادغام آنها باعث کاهش L شود، با عم ادغام می شوند. با هر حرکت L طبق فرمول (9.59) به روز می شود. انجمن های بدست آمده باهم ادغام شده و ابر انجمن ها را تشکیل می دهند و یک گذر تمام می شد. پس از آن الگوریتم مجددا روی شبکه کاهش یافته جدید اجرا می شود.

پیچیدگی محاسباتی
در پیچیدگی محاسباتی اینفومپ فرآیند استفاده شده برای کمینه کردن معادله نقشه L تعیین کننده است. اگر از الگوریتم لووین استفاده شود، پیچیدگی محاسباتی مشابه پیچیدگی محاسباتی الگوریتم لووین خواهد بود، یعنی حداکثر O(LlogL) یا در گراف های خلوت O(Nlog N) است.

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

بخش 9.13
مباحث پیشرفته 9.D
حد آستانه تاثیر کیلیک

در این بخش آستانه تاثیر (9.20) را برای تاثیر کیلیک در شبکه های تصادفی بدست می آوریم و در مورد گام های اصلی الگوریتم CFinder (شکل 9.39) بحث می کنیم.

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

مقدار مورد انتظاری که بالا درموردش صحبت شد از طریق زیر بدست می آید

که عبارت (k-1) تعداد گره های نمونه ای که می تواند در تغییر مکان بعدی استفاده کرد را مشخص می کند. عبارت N-k–1)^k–1 تعداد نقاط نهایی که نمونه بعد از جابجایی می تواند روی آنها قرار گیرد را نشان می دهد و در خارج از این نقاط تنها کسر p^k–1 قابل قبول است، زیرا هر یک از k-1 یال جدید (مرتبط با جابجایی) باید برای ایجاد k-کیلیک جدید وجود داشته باشند. برای N بزرگ فرمول (9.63) بصورت زیر ساده می شود

که در نهایت به فرمول (9.16) می رسد.

بخش 9.14
منابع

[1] B. Droitcour. Young Incorporated Artists. Art in America, 92-97, April 2014.

[2] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech., 2008.

[3] G.C. Homans. The Human Groups. Harcourt, Brace & Co, New York, 1950.

[4] S.A. Rice. The identification of blocs in small political bodies. Am. Polit. Sci. Rev., 21:619–627, 1927.

[5] R.D. Luce and A.D. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949.

[6] R.S. Weiss and E. Jacobson. A method for the analysis of the structure of complex organizations. Am. Sociol. Rev., 20:661–668, 1955.

[7] W.W. Zachary. An information flow model for conflict and fission in small groups. J. Anthropol. Res., 33:452–473, 1977.

[8] L. Donetti and M.A. Muñoz. Detecting network communities: a new systematic and efficient algorithm. J. Stat. Mech., P10012, 2004.

[9] M. Girvan and M.E.J. Newman. Community structure in social and biological networks. PNAS, 99:7821–7826, 2002.

[10] L.H. Hartwell, J.J. Hopfield, and A.W. Murray. From molecular to modular cell biology. Nature, 402:C47–C52, 1999.

[11] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabási. Hierarchical organization of modularity in metabolic networks. Science, 297:1551-1555, 2002.

[12] K.-I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal, and A.-L. Barabási. The human disease network. PNAS, 104:8685-8690, 2007.

[13] J. Menche, A.Sharma, M. Kitsak, S. Ghiassian, M. Vidal, J. Loscalzo, A.-L. Barabási. Oncovering disease-disease relationships through the human interactome. 2014.

[14] A.-L. Barabási, N. Gulbahce, and J. Loscalzo. Network medicine: a network-based approach to human disease. Nature Review Genetics, 12:56-68, 2011.

[15] G. W. Flake, S. Lawrence, and C.L. Giles. Efficient identification of web communities. Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 150-160, 2000.

[16] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. PNAS, 101:2658–2663, 2004.

[17] A.B. Kahng, J. Lienig, I.L. Markov, and J. Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, 2011.

[18] B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 49:291–307, 1970.

[19] G.E. Andrews. The Theory of Partitions. Addison-Wesley, Boston, USA, 1976.

[20] L. Lovász. Combinatorial Problems and Exercises. North-Holland, Amsterdam, The Netherlands, 1993.

[21] G. Pólya and G. Szegő. Problems and Theorems in Analysis I. Springer- Verlag, Berlin, Germany, 1998.

[22] V. H. Moll. Numbers and Functions: From a classical-experimental mathematician’s point of view. American Mathematical Society, 2012.

[23] M.E.J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.

[24] M.E.J. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27:39–54, 2005.

[25] U. Brandes. A faster algorithm for betweenness centrality. J. Math. Sociol., 25:163–177, 2001.

[26] T. Zhou, J.-G. Liu, and B.-H. Wang. Notes on the calculation of node betweenness. Chinese Physics Letters, 23:2327–2329, 2006.

[27] E. Ravasz and A.-L. Barabasi. Hierarchical organization in complex networks. Physical Review E, 67:026112, 2003.

[28] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. Pseudofractal scale-free web. Physical Review E, 65:066122, 2002.

[29] E. Mones, L. Vicsek, and T. Vicsek. Hierarchy Measure for Complex Networks. PLoS ONE, 7:e33799, 2012.

[30] A. Clauset, C. Moore, and M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453:98-101, 2008.

[31] L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics, P09008, 2005.

[32] S. Fortunato and M. Barthélemy. Resolution limit in community detection. PNAS, 104:36–41, 2007.

[33] M.E.J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, 69:066133, 2004.

[34] S. Fortunato and M. Barthélemy. Resolution limit in community detection. PNAS, 104:36–41, 2007.

[35] A. Clauset, M.E.J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.

[36] G. Palla, I. Derényi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814, 2005.

[37] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas. Self-similar community structure in a network of human interactions. Physical Review E, 68:065103, 2003.

[38] L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. J. Stat. Mech., P09008, 2005.

[39] J. Ruan and W. Zhang. Identifying network communities with a high resolution. Physical Review E 77: 016104, 2008.

[40] B. H. Good, Y.-A. de Montjoye, and A. Clauset. The performance of modularity maximization in practical contexts. Physical Review E, 81:046106, 2010.

[41] R. Guimerá, M. Sales-Pardo, and L.A.N. Amaral. Modularity from fluctuations in random graphs and complex networks. Physical Review E, 70:025101, 2004.

[42] J. Reichardt and S. Bornholdt. Partitioning and modularity of graphs with arbitrary degree distribution. Physical Review E, 76:015102, 2007.

[43] J. Reichardt and S. Bornholdt. When are networks truly modular? Physica D, 224:20–26, 2006.

[44] M. Rosvall and C.T. Bergstrom. Maps of random walks on complex networks reveal community structure. PNAS, 105:1118, 2008.

[45] M. Rosvall, D. Axelsson, and C.T. Bergstrom. The map equation. Eur. Phys. J. Special Topics, 178:13, 2009.

[46] M. Rosvall and C.T. Bergstrom. Mapping change in large networks. PLoS ONE, 5:e8694, 2010.

[47] A. Perey. Oksapmin Society and World View. Dissertation for Degree of Doctor of Philosophy. Columbia University, 1973.

[48] I. Derényi, G. Palla, and T. Vicsek. Clique percolation in random networks. Physical Review Letters, 94:160202, 2005.

[49] J.M. Kumpula, M. Kivelä, K. Kaski, and J. Saramäki. A sequential algorithm for fast clique percolation. Physical Review E, 78:026109, 2008.

[50] G. Palla, A.-L. Barabási, and T. Vicsek. Quantifying social group evolution. Nature, 446:664-667, 2007.

[51] Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466:761-764, 2010.

[52] T.S. Evans and R. Lambiotte. Line graphs, link partitions, and overlapping communities. Physical Review E, 80:016105, 2009.

[53] M. Chen, K. Kuzmin, and B.K. Szymanski. Community Detection via Maximization of Modularity and Its Variants. IEEE Trans. Computational Social Systems, 1:46-65, 2014.

[54] I. Farkas, D. Ábel, G. Palla, and T. Vicsek. Weighted network modules. New J. Phys., 9:180, 2007.

[55] S. Lehmann, M. Schwartz, and L.K. Hansen. Biclique communities. Physical Review E, 78:016108, 2008.

[56] N. Du, B. Wang, B. Wu, and Y. Wang. Overlapping community detection in bipartite networks. IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, IEEE Computer Society, Los Alamitos, CA, USA: 176–179, 2008.

[57] A. Condon and R.M. Karp. Algorithms for graph partitioning on the planted partition model. Random Struct. Algor., 18:116–140, 2001.

[58] A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs for testing community detection algorithms. Physical Review E, 78:046110, 2008.

[59] A. Lancichinetti, S. Fortunato, and J. Kertész. Detecting the overlapping and hierarchical community structure of complex networks. New Journal of Physics, 11:033015, 2009.

[60] S. Fortunato. Community detection in graphs. Physics Reports, 486:75–174, 2010.

[61] D. Hric, R.K. Darst, and S. Fortunato. Community detection in networks: structural clusters versus ground truth. Physical Review E, 90:062805, 2014.

[62] M. S. Granovetter. The Strength of Weak Ties. The American Journal of Sociology, 78:1360–1380, 1973.

[63] J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L. Barabási. Structure and tie strengths in mobile communication networks. PNAS, 104:7332, 2007.

[64] K.-I. Goh, B. Kahng, and D. Kim. Universal Behavior of Load Distribution in Scale-Free Networks. Physical Review Letters, 87:278701, 2001.

[65] A. Maritan, F. Colaiori, A. Flammini, M. Cieplak, and J.R. Banavar. Universality Classes of Optimal Channel Networks. Science, 272:984 –986, 1996.

[66] L.C. Freeman. A set of measures of centrality based upon betweenness. Sociometry, 40:35–41, 1977.

[67] J. Hopcroft, O. Khan, B. Kulis, and B. Selman. Tracking evolving communities in large linked networks. PNAS, 101:5249–5253, 2004.

[68] S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionary behavior of interaction graphs. KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, pp. 913–921, 2007.

[69] D.J. Fenn, M.A. Porter, M. McDonald, S. Williams, N.F. Johnson, and N.S. Jones. Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007–2008 credit crisis. Chaos, 19:033119, 2009.

[70] D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering, in: KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, pp. 554–560, 2006.

[71] Y. Chi, X. Song, D. Zhou, K. Hino, and B.L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, pp. 153–162, 2007.

[72] Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B.L. Tseng. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. in: WWW ’08: Proceedings of the 17th International Conference on the World Wide Web, ACM, New York, NY, USA, pp. 685–694, 2008.

[73] L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, pp. 44–54, 2006.

[74] M. E. J. Newman and J. Park. Why social networks are different from other types of networks. Physical Review E, 03G122, 2003.

[75] B. Krishnamurthy and J. Wang. On network-aware clustering of web clients. SIGCOMM Comput. Commun. Rev., 30:97–110, 2000.

[76] K.P. Reddy, M. Kitsuregawa, P. Sreekanth, and S.S. Rao. A graph based approach to extract a neighborhood customer community for collaborative filtering. DNIS ’02: Proceedings of the Second International Workshop on Databases in Networked Information Systems, Springer-Verlag, London, UK, pp. 188–200, 2002.

[77] R. Agrawal and H.V. Jagadish. Algorithms for searching massive graphs. Knowl. Data Eng., 6:225–238, 1994.

[78] A.Y. Wu, M. Garland, and J. Han. Mining scale-free networks using geodesic clustering. KDD ’04: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, NY, USA, 2004, pp. 719–724, 2004.