ساختار جامعه
در مطالعه شبکه های پیچیده،اگر گره های شبکه بتوانند به راحتی در مجموعه گره هایی (بالقوه همپوشانی) قرار گیرند، به گونه ای که هر مجموعه از گره ها به طور متراکم در داخل متصل شوند گفته می شود که شبکه دارای ساختار جامعه است . در مورد خاص یافته های "عدم تداخل" جامعه ، این بدان معنی است که شبکه به طور طبیعی به گروه هایی از گره ها با اتصالات متراکم داخلی و ارتباطات پراکنده بین گروه ها تقسیم می شود. اما جوامع "همپوشانی" نیز مجاز است. تعریف کلی تر بر این اصل استوار است که اگر جفت گره ها هر دو عضو یک جامعه (ها) باشند ، به احتمال زیاد به هم متصل می شوند و در صورت عدم اشتراک در اجتماعات ، احتمال اتصال آنها کمتر است. یک مسئله مرتبط اما متفاوت جستجوی جامعه است ، جایی که هدف یافتن جامعه ای است که یک راس خاص به آن تعلق دارد.
در بررسی شبکه ها ، از قبیل شبکه های رایانه ای و اطلاعاتی ، شبکه های اجتماعی و شبکه های بیولوژیکی، تعدادی از ویژگی‌های مختلف به طور کلی پیدا شده‌است، از جمله ویژگی جهان کوچک ، توزیع درجه های سنگین و خوشه بندی و غیره. یکی از ویژگی های مشترک دیگر ، ساختار جامعه است. در زمینه شبکه ها، ساختار جامعه به پدید آمدن گروهی از گره ها در شبکه اشاره دارد که از بقیه شبکه متراکم تر هستند، مانند تصویر سمت راست. این ناهمگنی در اتصالات نشاندهنده ی این است که شبکه در درون خود، دارای تقسیمات طبیعی خاصی است.
جوامع معمولا براساس افراز مجموعه رأس ها تعریف می شوند ، یعنی هر گره در یک و تنها یک جامعه قرار می گیرد، دقیقاً مانند شکل. این یک ساده سازی مفید است و بیشتر روشهای شناسایی جامعه این نوع ساختار جامعه را پیدا می کنند. با این حال در مواردی، نمایندگی بهتر می تواند آنی باشد که در آن رئوس در بیش از یک جامعه باشد. این قضیه میتواند در یک شبکه اجتماعی رخ دهد که هر راس نمایانگر یک شخص است و جوامع، نشان دهنده ی گروه های مختلف دوستان هستند: یک جامعه برای خانواده، جامعه دیگر برای همکاران، یک انجمن برای دوستان در یک باشگاه ورزشی و غیره. استفاده از كلیكها برای شناسایی جامعه كه در زیر آمده است، نمونه‌ای از این است که چگونه چنین ساختار اجتماعی با هم پوشانی را می‌توان یافت.
امکان دارد که برخی از شبکه ها ساختار جامعه ی معنی داری نداشته باشند. مثلا بسیاری از مدل های اساسی شبکه مانند نمودار تصادفی و مدل Barabási – Albert، ساختار جامعه را نشان نمی دهند.
ساختارهای جامعه در شبکه های واقعی بسیار رایج است. شبکه های اجتماعی شامل گروه های اجتماعی بر اساس مکان مشترک، علایق، شغل و غیره است.
پیدا کردن یک ساختار اجتماعی زیربنایی در یک شبکه، در صورت وجود، به چند دلیل دارای اهمیت است. جوامع برای ما امکان ایجاد یک نقشه در مقیاس بزرگ از شبکه را فراهم می سازد، زیرا جوامع منفرد مانند متا گره ها (meta-nodes) در شبکه عمل می کنند که مطالعه آن را آسان تر می کند.
جوامع فردی همچنین نشان دهنده ی عملکرد سیستم ارائه‌شده توسط شبکه هستند، چرا که جوامع اغلب با واحدهای عملکردی سیستم سروکار دارند. در شبکه های متابولیکی، این گروه های عملکردی مربوط به چرخه ها یا مسیرها هستند در حالی که در شبکه تعامل پروتئین-پروتئین ، جوامع مربوط به پروتئین ها، دارای عملکردی مشابه با داخل یک سلول بیولوژیکی هستند. به طور مشابه، شبکه‌های استنادی، جوامع را با موضوع تحقیق تشکیل می‌دهند. توانایی شناسایی این ساختارهای فرعی درون یک شبکه، می‌تواند دیدگاهب را نسبت به چگونگی عملکرد شبکه و توپولوژی ایجاد کند. چنین بینشی می تواند در بهبود برخی الگوریتم های نمودار مانند خوشه طیفی مفید باشد.
یکی از دلایل اهمیت جوامع این است که آنها معمولا دارای خصوصیات بسیار متفاوتی نسبت به خصوصیات متوسط شبکه ها هستند. بنابراین، فقط با تمرکز روی این ویژگی های متوسط، معمولاً بسیاری از ویژگی های مهم و جالب را در داخل شبکه از دست می دهیم. به عنوان مثال ، در یک شبکه اجتماعی معین، هر دو گروه اجتماعی و کم گو باید همزمان با یکدیگر وجود داشته باشند.
وجود جوامع همچنین روی فرآیندهای متعددی مثل شایعه پراکنی یا شیوع اپیدمی در شبکه تحت تأثیر میگذارد. از این رو برای درک صحیح چنین فرایندهایی، شناسایی جوامع و همچنین بررسی چگونگی تأثیر آنها بر فرآیندهای انتشار در تنظیمات مختلف ، از اهمیت برخوردار است.
در آخر، برنامه ای مهم که جامعه یابی در علم شبکه یافته است، پیش بینی لینک های از دست رفته و شناسایی پیوندهای کاذب در شبکه است. در طی فرآیند اندازه گیری، برخی از لینک ها ممکن است به چند دلیل مشاهده نشوند. به همین ترتیب، برخی از لینک ها به دلیل خطاهای اندازه گیری، می توانند به اشتباه وارد داده شوند. هر دو این موارد به خوبی توسط الگوریتم تشخیص جامعه اداره می شوند زیرا امکان تعیین احتمال وجود یک یال بین یک جفت گره‌ها وجود دارد.
پیدا کردن جوامع در یک شبکه دلخواه می تواند یک کار دشوار محاسباتی باشد. تعداد جوامع، در صورت وجود، در داخل شبکه معمولاً ناشناخته است و جوامع اغلب از اندازه و/یا تراکم نابرابر برخوردارند. با وجود این سختی ها، روش های مختلفی برای جامعه یابی ایجاد شده و با موفقیت های زیادی همراه بوده است.
یکی از قدیمی ترین الگوریتم های تقسیم بندی شبکه ها به چند قطعه، روش حداقل برش(minimum cut) (و انواع مختلفی مانند برش نسبت(ratio cut) و برش نرمال(normalized cut) ) است. این روش، به عنوان مثال ، در تعادل بار برای محاسبات موازی به منظور به حداقل رساندن ارتباط بین گره های پردازنده ، استفاده می کند.
در روش حداقل برش (minimum cut)، شبکه به تعدادی از پیش تعیین شده از قطعات تقسیم می شود، که معمولاً تقریبا به اندازه یک اندازه، طوری انتخاب می شوند که تعداد لبه های بین گروه ها حداقل شود. این روش در بسیاری از کاربردها خوب عمل می‌کند که در اصل در نظر گرفته‌شده اما کم‌تر از ایده‌آل برای یافتن ساختار اجتماعی در شبکه‌های عمومی است چرا که جوامع را بدون در نظر گرفتن اینکه آیا آن‌ها در ساختار ضمنی هستند یا نه, و تنها تعداد ثابتی از آن‌ها پیدا خواهد کرد.
روش دیگری برای پیدا کردن ساختارهای جوامع در شبکه ها دسته بندی سلسله مراتبی است. در این روش یک معیار شباهت برای کمی کردن برخی (معمولا توپولوژیکی) تشابه بین جفت‌های گره تعریف می‌شود. معیارهایی که معمولاً استفاده می شوند شامل شباهت کسینوس ()، شاخص ژاکارد و فاصله همینگ بین ردیف های ماتریس مجاورت است. سپس یک گروه با توجه به این معیار، گره‌ها مشابه را به جوامع تبدیل می‌کند. چندین طرح مشترک برای گروه بندی کردن وجود دارد، دوتا از ساده ترین آن ها دسته بندی تک پیوندی است که در آن دو گروه به عنوان اجتماع جداگانه در نظر گرفته شده و اگر و فقط اگر همه جفت گره های گروه های مختلف شباهت کمتری نسبت به یک مقدار مشخص داشته باشند، و خوشه بندی پیوند کامل، که در آن همه ی گره های هر گروه شباهت بیشتری نسبت به یک مقدار مشخص دارند. گام مهم این است که چگونه آستانه را برای توقف خوشه‌بندی تجمعی مشخص کنیم، که نشان‌دهنده ساختار جامعه نزدیک به بهینه است. یک استراتژی مشترک شامل ایجاد یک یا چند معیار برای پایش ویژگی‌های جهانی شبکه است، که در یک گام از خوشه‌بندی به اوج می‌رسد. یکی از رویکردهای جالب در این راستا استفاده کردن از معیارهای مختلف و متنوع برای تعیین شباهت یا عدم تشابه است که از طریق مبالغ محدب() ترکیب می شوند. تقریب دیگر محاسبه مقدار کنترل کننده چگالی لبه های خوشه ها با توجه به چگالی بین خوشه ها است ، مانند چگالی پارتیشن ، که در صورت تعریف متریک شباهت بین لبه ها (که تعریف تعریف جوامع همپوشانی را ارائه می دهد) پیشنهاد شده است ، و هنگامی که شباهت بین گره ها تعریف می شود ، گسترش می یابد ، که به شما امکان می دهد تعاریف دیگری از جوامع مانند اصناف (به عنوان مثال گروه های گره ای که تعداد پیوندهای مشابهی نسبت به همسایگان مشابه دارند اما لزوماً خود را به هم متصل نمی کنند) در نظر گرفته شود. این روش ها را می توان برای در نظر گرفتن شبکه های چند بعدی گسترش داد ، به عنوان مثال وقتی با شبکه هایی دارای گره با انواع مختلف پیوند سروکار داریم.
الگوریتم دیگری که معمولاً برای پیدا کردن جوامع استفاده می شود الگوریتم Girvan – Newman است. این الگوریتم فقط با پشت سر گذاشتن خود جوامع و با شناسایی لبه های شبکه ای که بین جوامع قرار دارد آنها را حذف می کند. این شناسایی با استفاده از اندازه گیری نظریه گراف بین مرکزیت انجام می شود که یک عدد به هر لبه اختصاص می دهد که اگر لبه "بین" بسیاری از جفت گره ها باشد، بزرگ است.
الگوریتم Girvan – Newman یک الگوریتم محبوب است به این دلیل که نتایج با کیفیتی را بدست آورده است. در تعدادی از بسته های نرم افزاری استاندارد پیاده سازی شده است. اما به آرامی اجرا شده و بر روی شبکه ای که از "n" راس و "m" لبه تشکیل شده باشد، زمان O ( "m" "n" ) به طول می انجامد و این کار را برای شبکه های بیش از چند هزار گره غیر قابل انجام می کند.
علیرغم اشکالات شناخته شده، حداکثر سازی مدولار یکی از روش های پرکاربرد برای شناسایی جامعه است. پیمانه ای بودن عملکرد مفیدی است که کیفیت یک تقسیم خاص از یک شبکه را به جوامع اندازه‌گیری می‌کند. این روش با جستجو در بخش های احتمالی یک شبکه برای یک یا چند مورد که دارای مادولاریسیون خاصی هستند جوامع را تشخیص می دهد. از آنجا که جستجوی جامع و کامل در تمام بخشهای ممکن معمولاً غیر ممکن میباشد، الگوریتم‌های تجربی مبتنی بر روش‌های بهینه‌سازی تقریبی مانند الگوریتم‌های حریصانه، تبرید شبیه‌سازی شده، یا بهینه‌سازی طیفی، با رویکردهای مختلفی که تعادل بین سرعت و دقت مختلف را ارایه می‌دهند.. یک رویکرد محبوب این روش، متد لوین است که با تکرار جوامع محلی را بهینه می‌کند تا زمانی که واحد پیمانه‌ای جهانی دیگر نمی‌تواند به طور همزمان با اختلالات موجود در وضعیت فعلی جامعه بهبود یابد. الگوریتمی که از طرح RenEEL استفاده می کند و نمونه ای از الگوی یادگیری گروه فوق العاده (EEL) است، در حال حاضر بهترین الگوریتم حداکثر سازی مدولار است.
فایده ی این روش سوال برانگیز است، زیرا نشان داده شده است که این روش اغلب بسته به اندازه شبکه، خوشه هایی را که کوچکتر از مقیاس هستند تشخیص نمی دهد ( حد تفکیک پذیری ). از طرفی، چشم انداز مقادیر مدولاریته با انحطاط عظیم پارتیشن ها با مدولاریته بالا، نزدیک به حداکثر مطلق مشخص می شود ، که ممکن است بسیار متفاوت از یکدیگر باشد.
روش های مبتنی بر استنتاج آماری سعی در تطبیق مدل تولیدی با داده های شبکه دارد که ساختار جامعه را رمزگذاری می کند. مزیت کلی این روش در مقایسه با گزینه های جایگزین این است که ماهیت اصولی تری دارد و به طور ذاتی توانایی رسیدگی به موضوعات مهم آماری را دارد. بیشتر روش ها در ادبیات بر اساس مدل بلوک تصادفی () و همچنین انواع مختلفی از جمله عضویت مختلط، اصلاح درجه، و ساختارهای سلسله مراتبی است. انتخاب مدل می تواند با استفاده از رویکردهای اصولی مثل حداقل طول توصیف (یا معادلا، انتخاب مدل بیزی ) و آزمون نسبت احتمال انجام شود. در حال حاضر الگوریتم های زیادی برای انجام استنباطی کارآمد از مدل های بلوک تصادفی وجود داشته و از جمله ی آنها میتوان به انتشار باور و مونت کارلو تجمعی اشاره کرد.
برخلاف رویکردهایی که تلاش در دسته بندی کردن یک شبکه با عملکردی عینی دارند، اینگونه روش ها بر اساس مدل های مولد ساخته شده اند که نه تنها به عنوان توصیف کننده ی ساختار شبکه در مقیاس بزرگ عمل می کنند بلکه می توانند برای "تعمیم" داده ها و پیش بینی وقوع پیوندهای گمشده یا جعلی در شبکه استفاده شوند.
کلیک ها زیرگراف هایی هستند که در آنها هر گره به تمام گره های دیگر در دسته متصل است. از آنجایی که گره ها نمی توانند اتصالی محکم تر از این داشته باشند،تعجبی ندارد که رویکردهای زیادی برای شناسایی جامعه در شبکه ها براساس شناسایی کلیک ها در گراف و تحلیل چگونگی این همپوشانی ها وجود دارد. توجه کنید که یک گره می تواند عضو بیش از یک کلیک باشد و در این روش ها یک گره می تواند عضو بیش از یک جامعه باشد که " "ساختار جامعه را با هم تداخل می دهد" ".
یکی از رویکردها، یافتن " "حداکثر دسته" " است. به این معنی که دسته هایی را پیدا کنید که زیر مجموعه هیچ دسته دیگری نیستند. یک الگوریتم کلاسیک برای یافتن این موارد الگوریتم Bron – Kerbosch است. هم پوشانی این ها را می‌توان برای تعریف جوامع به چندین روش مورد استفاده قرار داد. ساده ترین راه این است که حداکثر کلیک های بزرگتر از حداقل اندازه (تعداد گره ها) را در نظر بگیریم. اجتماع این دسته ها یک زیرگراف را تشکیل می دهد که اجزای آن (اجزای جدا شده) جوامع را مشخض می کنند. رویکردهایی از این قبیل معمولا در نرم افزار تجزیه و تحلیل شبکه های اجتماعی مانند UCInet پیاده سازی می شوند.
روش جایگزین استفاده از دسته هایی با اندازه ثابت است formula_1 . از همپوشانی این موارد می توان برای تعریف نوعی استفاده کرد formula_1 به طور منظم hypergraph یا یک ساختار که یک تعمیم از نمودار خط (مورد زمانی که formula_3 ) معروف به " "نمودار کلیك" ". نمودارهای کلیس دارای رئوس هستند که نمای کلی ها را در نمودار اصلی نشان می دهند در حالی که لبه های نمودار دسته همپوشانی کلیک را در نمودار اصلی ثبت می کنند. با استفاده از هر یک از روش های تشخیص جامعه قبلی (که هر گره را به یک انجمن اختصاص می دهد) به نمودار کلیک ، سپس هر کلیک را به یک انجمن اختصاص می دهد. سپس می توان برای تعیین عضویت در جامعه در گره های موجود در کلیک ها استفاده کرد. دوباره به عنوان گره ممکن است در چند کلیک باشد ، می تواند عضو چندین انجمن باشد. به عنوان مثال روش نفوذ کلیک جوامع را به عنوان خوشه های تراوش در تعریف می کند formula_1 -کلیک برای انجام این کار همه چیز را پیدا می کند formula_1 -کلیک های موجود در یک شبکه ، یعنی تمام زیر نمودارهای کامل formula_1 گره ها سپس دو تعریف می کند formula_1 در صورت اشتراك بودن ، كلیكها مجاور خواهند بود formula_8 گره ها ، این برای تعریف لبه ها در نمودار کلیک استفاده می شود. سپس یک جامعه به عنوان حداکثر اتحادیه تعریف می شود formula_1 - کلیساهایی که در آن می توانیم به هر مکانی برسیم formula_1 - از هر کس دیگری استفاده کنید formula_1 - از طریق مجموعه ای از formula_1 مجاورت کلیک یعنی جوامع فقط اجزای متصل شده در نمودار دسته هستند. از آنجا که یک گره می تواند به چندین مورد مختلف تعلق داشته باشد formula_1 خوشه های لایه برداری به طور همزمان ، جوامع می توانند با یکدیگر همپوشانی داشته باشند.
ارزیابی الگوریتم ها ، برای تشخیص که در تشخیص ساختار جامعه بهتر هستند ، هنوز یک سوال باز است. این باید بر اساس تجزیه و تحلیل شبکه های ساختار شناخته شده باشد. یک نمونه معمول ، آزمون "چهار گروه" است که در آن شبکه ای به چهار گروه با اندازه یکسان تقسیم می شود (معمولاً هر کدام از آنها 32 گره است) و احتمال اتصال در داخل و بین گروه ها متفاوت است تا ساختارهای کم و بیش چالش برانگیزی برای تشخیص الگوریتم این نمودارهای معیار مورد خاصی از مدل پارتیشن L Condon و Karp یا به طور کلی " مدل های بلوک تصادفی " است ، یک کلاس کلی از مدل های شبکه تصادفی حاوی ساختار جامعه. معیارهای انعطاف پذیر دیگری نیز ارائه شده است که امکان تغییر اندازه گروه و توزیع درجه غیرپیشرفته را فراهم می کند ، مانند معیار LFR که گسترش معیار چهار گروه است که شامل توزیع های ناهمگن درجه گره و اندازه جامعه است و باعث می شود یک آزمایش شدیدتر از روش های تشخیص جامعه.
معیارهای رایج تولید شده رایانه ای با شبکه ای از جوامع کاملاً مشخص شروع می شوند. سپس ، این ساختار با سیم کشی یا حذف پیوندها تخریب می شود و تشخیص پارتیشن اصلی برای الگوریتم ها دشوارتر می شود. در پایان ، شبکه به نقطه ای می رسد که اساساً تصادفی است. این نوع معیار را می توان "باز" نامید. عملکرد این معیارها با معیارهایی مانند اطلاعات متقابل عادی یا تغییر اطلاعات ارزیابی می شود . آنها راه حل بدست آمده توسط یک الگوریتم با ساختار اصلی جامعه مقایسه می کنند و شباهت هر دو پارتیشن را ارزیابی می کنند.
دز سال های اخیر، نتایج نسبتاً شگفت انگیزی توسط گروه های مختلف به دست آمده است که نشان دهنده ی وجود یک مرحله انتقال در مسئله شناسایی جامعه است، این نتایج نشان می دهند که هرچه تراکم اتصالات درون جوامع و بین جوامع بیشتر می شود یا هر دو کوچکتر می شوند (به طور یکسان، با ضعف بیش از حد ساختار جامعه یا شبکه بسیار پراکنده)، ناگهان جوامع غیرقابل شناسایی می شوند. یعنی جوامع هنوز وجود دارند، زیرا وجود و عدم وجود لبه ها همچنان با عضویت جامعه در نقاط انتهایی آنها ارتباط دارد. اما نام گذاری و برچسب زدن گره ها بهتر از شانس، یا حتی تشخیص نمودار از نمودار تولید شده توسط یک مدل پوچ مانند مدل Erdos – Renyi بدون ساختار جامعه ، از نظر تئوری غیرممکن است. این انتقال مستقل از نوع الگوریتمی است که برای شناسایی جوامع استفاده می شود ، و این بدان معناست که محدودیت اساسی در توانایی ما برای شناسایی جوامع در شبکه ها ، حتی با استنباط بهینه بیزی (یعنی بدون در نظر گرفتن منابع محاسباتی ما) وجود دارد.
یک مدل بلوک تصادفی را فرض کنید که formula_14 گره دارد، formula_15 گروه هایی با اندازه یکسان هستند، و formula_16 و formula_17 را برای احتمال اتصال در داخل و بین گروه ها دز نظر بگیرید. حال اگر formula_18 آنگاه شبکه دارای ساختار جامعه است زیرا تراکم پیوند در داخل گروه ها بیشتر از تراکم پیوند بین گروه ها خواهد بود. در حالت پراکنده، formula_16 و formula_17 مقیاس به عنوان formula_21 به طوری که میانگین درجه ثابت باشد:
سپس تشخیص جوامع غیرممکن می شود:
انعطاف پذیری شبکه های پیمانه ای به دلیل خرابی گره یا لینک معمولاً با استفاده از تئوری نفوذ (percolation theory) مطالعه می شود. ساختار شبکه هنگام حمله به گره های داخلی (به عنوان مثال گره هایی که جوامع را به یکدیگر متصل می کنند) مورد مطالعه قرار گرفته است. همچنین، اخیرا مطالعه ای به مطالعه ی چگونگی تقویت ارتباطات بین جامعه برای مقاومت در برابر جوامع پرداخته است.
مطالعه مدل های اپیدمی در شبکه های پیمانه ای توسط والدز و همکاران انجام شده است. این نویسندگان همچنین معیار اعلام بیماری همه‌گیر را مورد مطالعه قرار دادند.
مدلی برای شبکه های مدولار فضایی توسط Gross و همکاران ایجاد شده است. این مدل به عنوان مثال ، زیرساخت ها را در کشوری توصیف می کند که در آن جوامع (ماژول ها) شهرهای دارای اتصالات زیادی را در فضای دو بعدی نشان می دهند. پیوندهای بین جوامع (شهرها) کمتر و معمولاً با نزدیکترین همسایگان است (شکل 2 را ببینید). شیوع اپیدمی در چنین شبکه هایی در گروس و هاولین بررسی شده است.