ساختار جامعه

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

خواص

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

در بررسی شبکه ها ، از قبیل شبکه های رایانه ای و اطلاعاتی ، شبکه های اجتماعی و شبکه های بیولوژیکی، تعدادی از ویژگی‌های مختلف به طور کلی پیدا شده‌است، از جمله ویژگی جهان کوچک ، توزیع درجه های سنگین و خوشه بندی و غیره. یکی از ویژگی های مشترک دیگر ، ساختار جامعه است. ^{[۱] [۲] [۳] [۴] [۵]} در زمینه شبکه ها، ساختار جامعه به پدید آمدن گروهی از گره ها در شبکه اشاره دارد که از بقیه شبکه متراکم تر هستند، مانند تصویر سمت راست. این ناهمگنی در اتصالات نشاندهنده ی این است که شبکه در درون خود، دارای تقسیمات طبیعی خاصی است.

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

امکان دارد که برخی از شبکه ها ساختار جامعه ی معنی داری نداشته باشند. مثلا بسیاری از مدل های اساسی شبکه مانند نمودار تصادفی و مدل Barabási – Albert، ساختار جامعه را نشان نمی دهند.

اهمیت

ساختارهای جامعه در شبکه های واقعی بسیار رایج است. شبکه های اجتماعی شامل گروه های اجتماعی بر اساس مکان مشترک، علایق، شغل و غیره است. ^{[۵] [۶]}

پیدا کردن یک ساختار اجتماعی زیربنایی در یک شبکه، در صورت وجود، به چند دلیل دارای اهمیت است. جوامع برای ما امکان ایجاد یک نقشه در مقیاس بزرگ از شبکه را فراهم می سازد، زیرا جوامع منفرد مانند متا گره ها (meta-nodes) در شبکه عمل می کنند که مطالعه آن را آسان تر می کند. ^[۷]

جوامع فردی همچنین نشان دهنده ی عملکرد سیستم ارائه‌شده توسط شبکه هستند، چرا که جوامع اغلب با واحدهای عملکردی سیستم سروکار دارند. در شبکه های متابولیکی، این گروه های عملکردی مربوط به چرخه ها یا مسیرها هستند در حالی که در شبکه تعامل پروتئین-پروتئین ، جوامع مربوط به پروتئین ها، دارای عملکردی مشابه با داخل یک سلول بیولوژیکی هستند. به طور مشابه، شبکه‌های استنادی، جوامع را با موضوع تحقیق تشکیل می‌دهند.^[۱] توانایی شناسایی این ساختارهای فرعی درون یک شبکه، می‌تواند دیدگاهب را نسبت به چگونگی عملکرد شبکه و توپولوژی ایجاد کند. چنین بینشی می تواند در بهبود برخی الگوریتم های نمودار مانند خوشه طیفی مفید باشد. ^[۸]

یکی از دلایل اهمیت جوامع این است که آنها معمولا دارای خصوصیات بسیار متفاوتی نسبت به خصوصیات متوسط شبکه ها هستند. بنابراین، فقط با تمرکز روی این ویژگی های متوسط، معمولاً بسیاری از ویژگی های مهم و جالب را در داخل شبکه از دست می دهیم. به عنوان مثال ، در یک شبکه اجتماعی معین، هر دو گروه اجتماعی و کم گو باید همزمان با یکدیگر وجود داشته باشند. ^[۷]

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

در آخر، برنامه ای مهم که جامعه یابی در علم شبکه یافته است، پیش بینی لینک های از دست رفته و شناسایی پیوندهای کاذب در شبکه است. در طی فرآیند اندازه گیری، برخی از لینک ها ممکن است به چند دلیل مشاهده نشوند. به همین ترتیب، برخی از لینک ها به دلیل خطاهای اندازه گیری، می توانند به اشتباه وارد داده شوند. هر دو این موارد به خوبی توسط الگوریتم تشخیص جامعه اداره می شوند زیرا امکان تعیین احتمال وجود یک یال بین یک جفت گره‌ها وجود دارد. ^[۹]

الگوریتم هایی برای یافتن جوامع

پیدا کردن جوامع در یک شبکه دلخواه می تواند یک کار دشوار محاسباتی باشد. تعداد جوامع، در صورت وجود، در داخل شبکه معمولاً ناشناخته است و جوامع اغلب از اندازه و/یا تراکم نابرابر برخوردارند. با وجود این سختی ها، روش های مختلفی برای جامعه یابی ایجاد شده و با موفقیت های زیادی همراه بوده است. ^[۴]

روش حداقل برش

یکی از قدیمی ترین الگوریتم های تقسیم بندی شبکه ها به چند قطعه، روش حداقل برش(minimum cut) (و انواع مختلفی مانند برش نسبت(ratio cut) و برش نرمال(normalized cut) ) است. این روش، به عنوان مثال ، در تعادل بار برای محاسبات موازی به منظور به حداقل رساندن ارتباط بین گره های پردازنده ، استفاده می کند.

در روش حداقل برش (minimum cut)، شبکه به تعدادی از پیش تعیین شده از قطعات تقسیم می شود، که معمولاً تقریبا به اندازه یک اندازه، طوری انتخاب می شوند که تعداد لبه های بین گروه ها حداقل شود. این روش در بسیاری از کاربردها خوب عمل می‌کند که در اصل در نظر گرفته‌شده اما کم‌تر از ایده‌آل برای یافتن ساختار اجتماعی در شبکه‌های عمومی است چرا که جوامع را بدون در نظر گرفتن اینکه آیا آن‌ها در ساختار ضمنی هستند یا نه, و تنها تعداد ثابتی از آن‌ها پیدا خواهد کرد. ^[۱۰]

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

روش دیگری برای پیدا کردن ساختارهای جوامع در شبکه ها دسته بندی سلسله مراتبی است. در این روش یک معیار شباهت برای کمی کردن برخی (معمولا توپولوژیکی) تشابه بین جفت‌های گره تعریف می‌شود. معیارهایی که معمولاً استفاده می شوند شامل شباهت کسینوس (cosine similarity)، شاخص ژاکارد و فاصله همینگ بین ردیف های ماتریس مجاورت است. سپس یک گروه با توجه به این معیار، گره‌ها مشابه را به جوامع تبدیل می‌کند. چندین طرح مشترک برای گروه بندی کردن وجود دارد، دوتا از ساده ترین آن ها دسته بندی تک پیوندی است که در آن دو گروه به عنوان اجتماع جداگانه در نظر گرفته شده و اگر و فقط اگر همه جفت گره های گروه های مختلف شباهت کمتری نسبت به یک مقدار مشخص داشته باشند، و خوشه بندی پیوند کامل، که در آن همه ی گره های هر گروه شباهت بیشتری نسبت به یک مقدار مشخص دارند. گام مهم این است که چگونه آستانه را برای توقف خوشه‌بندی تجمعی مشخص کنیم، که نشان‌دهنده ساختار جامعه نزدیک به بهینه است. یک استراتژی مشترک شامل ایجاد یک یا چند معیار برای پایش ویژگی‌های جهانی شبکه است، که در یک گام از خوشه‌بندی به اوج می‌رسد. یکی از رویکردهای جالب در این راستا استفاده کردن از معیارهای مختلف و متنوع برای تعیین شباهت یا عدم تشابه است که از طریق مبالغ محدب(convex sums) ترکیب می شوند. ^[۱۱] تقریب دیگر محاسبه مقدار کنترل کننده چگالی لبه های خوشه ها با توجه به چگالی بین خوشه ها است ، مانند چگالی پارتیشن ، که در صورت تعریف متریک شباهت بین لبه ها (که تعریف تعریف جوامع همپوشانی را ارائه می دهد) پیشنهاد شده است ، ^[۱۲] و هنگامی که شباهت بین گره ها تعریف می شود ، گسترش می یابد ، که به شما امکان می دهد تعاریف دیگری از جوامع مانند اصناف (به عنوان مثال گروه های گره ای که تعداد پیوندهای مشابهی نسبت به همسایگان مشابه دارند اما لزوماً خود را به هم متصل نمی کنند) در نظر گرفته شود. ^[۱۳] این روش ها را می توان برای در نظر گرفتن شبکه های چند بعدی گسترش داد ، به عنوان مثال وقتی با شبکه هایی دارای گره با انواع مختلف پیوند سروکار داریم. ^[۱۳]

الگوریتم Girvan – Newman

الگوریتم دیگری که معمولاً برای پیدا کردن جوامع استفاده می شود الگوریتم Girvan – Newman است. ^[۱] این الگوریتم فقط با پشت سر گذاشتن خود جوامع و با شناسایی لبه های شبکه ای که بین جوامع قرار دارد آنها را حذف می کند. این شناسایی با استفاده از اندازه گیری نظریه گراف بین مرکزیت انجام می شود که یک عدد به هر لبه اختصاص می دهد که اگر لبه "بین" بسیاری از جفت گره ها باشد، بزرگ است.

الگوریتم Girvan – Newman یک الگوریتم محبوب است به این دلیل که نتایج با کیفیتی را بدست آورده است. در تعدادی از بسته های نرم افزاری استاندارد پیاده سازی شده است. اما به آرامی اجرا شده و بر روی شبکه ای که از n راس و m لبه تشکیل شده باشد، زمان O ( m ² n ) به طول می انجامد و این کار را برای شبکه های بیش از چند هزار گره غیر قابل انجام می کند. ^[۱۴]

به حداکثر رساندن پیمانه ای بودن

علیرغم اشکالات شناخته شده، حداکثر سازی مدولار یکی از روش های پرکاربرد برای شناسایی جامعه است. ^[۱۴] پیمانه ای بودن عملکرد مفیدی است که کیفیت یک تقسیم خاص از یک شبکه را به جوامع اندازه‌گیری می‌کند. این روش با جستجو در بخش های احتمالی یک شبکه برای یک یا چند مورد که دارای مادولاریسیون خاصی هستند جوامع را تشخیص می دهد. از آنجا که جستجوی جامع و کامل در تمام بخشهای ممکن معمولاً غیر ممکن میباشد، الگوریتم‌های تجربی مبتنی بر روش‌های بهینه‌سازی تقریبی مانند الگوریتم‌های حریصانه، تبرید شبیه‌سازی شده، یا بهینه‌سازی طیفی، با رویکردهای مختلفی که تعادل بین سرعت و دقت مختلف را ارایه می‌دهند.. ^{[۱۵] [۱۶]} یک رویکرد محبوب این روش، متد لوین است که با تکرار جوامع محلی را بهینه می‌کند تا زمانی که واحد پیمانه‌ای جهانی دیگر نمی‌تواند به طور همزمان با اختلالات موجود در وضعیت فعلی جامعه بهبود یابد. ^{[۱۷] [۱۸]} الگوریتمی که از طرح RenEEL استفاده می کند و نمونه ای از الگوی یادگیری گروه فوق العاده (EEL) است، در حال حاضر بهترین الگوریتم حداکثر سازی مدولار است. ^{[۱۹] [۲۰]}

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

استنباط آماری

روش های مبتنی بر استنتاج آماری سعی در تطبیق مدل تولیدی با داده های شبکه دارد که ساختار جامعه را رمزگذاری می کند. مزیت کلی این روش در مقایسه با گزینه های جایگزین این است که ماهیت اصولی تری دارد و به طور ذاتی توانایی رسیدگی به موضوعات مهم آماری را دارد. بیشتر روش ها در ادبیات بر اساس مدل بلوک تصادفی (stochastic block model) ^[۲۳] و همچنین انواع مختلفی از جمله عضویت مختلط، ^{[۲۴] [۲۵]} اصلاح درجه، ^[۲۶] و ساختارهای سلسله مراتبی است. ^[۲۷] انتخاب مدل می تواند با استفاده از رویکردهای اصولی مثل حداقل طول توصیف ^{[۲۸] [۲۹]} (یا معادلا، انتخاب مدل بیزی ) و آزمون نسبت احتمال انجام شود. ^[۳۰] در حال حاضر الگوریتم های زیادی برای انجام استنباطی کارآمد از مدل های بلوک تصادفی وجود داشته و از جمله ی آنها میتوان به انتشار باور ^{[۳۱] [۳۲]} و مونت کارلو تجمعی اشاره کرد. ^[۳۳]

برخلاف رویکردهایی که تلاش در دسته بندی کردن یک شبکه با عملکردی عینی دارند، اینگونه روش ها بر اساس مدل های مولد ساخته شده اند که نه تنها به عنوان توصیف کننده ی ساختار شبکه در مقیاس بزرگ عمل می کنند بلکه می توانند برای تعمیم داده ها و پیش بینی وقوع پیوندهای گمشده یا جعلی در شبکه استفاده شوند. ^{[۳۴] [۳۵]}

روش های مبتنی بر کلیک

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

یکی از رویکردها، یافتن " حداکثر دسته " است. به این معنی که دسته هایی را پیدا کنید که زیر مجموعه هیچ دسته دیگری نیستند. یک الگوریتم کلاسیک برای یافتن این موارد الگوریتم Bron – Kerbosch است. هم پوشانی این ها را می‌توان برای تعریف جوامع به چندین روش مورد استفاده قرار داد. ساده ترین راه این است که حداکثر کلیک های بزرگتر از حداقل اندازه (تعداد گره ها) را در نظر بگیریم. اجتماع این دسته ها یک زیرگراف را تشکیل می دهد که اجزای آن (اجزای جدا شده) جوامع را مشخض می کنند. ^[۳۶] رویکردهایی از این قبیل معمولا در نرم افزار تجزیه و تحلیل شبکه های اجتماعی مانند UCInet پیاده سازی می شوند.

روش جایگزین استفاده از دسته هایی با اندازه ثابت است ${\displaystyle k}$ . از همپوشانی این موارد می توان برای تعریف نوعی استفاده کرد ${\displaystyle k}$ به طور منظم hypergraph یا یک ساختار که یک تعمیم از نمودار خط (مورد زمانی که ${\displaystyle k=2}$ ) معروف به " نمودار کلیك ". ^[۳۷] نمودارهای کلیس دارای رئوس هستند که نمای کلی ها را در نمودار اصلی نشان می دهند در حالی که لبه های نمودار دسته همپوشانی کلیک را در نمودار اصلی ثبت می کنند. با استفاده از هر یک از روش های تشخیص جامعه قبلی (که هر گره را به یک انجمن اختصاص می دهد) به نمودار کلیک ، سپس هر کلیک را به یک انجمن اختصاص می دهد. سپس می توان برای تعیین عضویت در جامعه در گره های موجود در کلیک ها استفاده کرد. دوباره به عنوان گره ممکن است در چند کلیک باشد ، می تواند عضو چندین انجمن باشد. به عنوان مثال روش نفوذ کلیک ^[۳۸] جوامع را به عنوان خوشه های تراوش در تعریف می کند ${\displaystyle k}$ -کلیک برای انجام این کار همه چیز را پیدا می کند ${\displaystyle k}$ -کلیک های موجود در یک شبکه ، یعنی تمام زیر نمودارهای کامل ${\displaystyle k}$ گره ها سپس دو تعریف می کند ${\displaystyle k}$ در صورت اشتراك بودن ، كلیكها مجاور خواهند بود ${\displaystyle k-1}$ گره ها ، این برای تعریف لبه ها در نمودار کلیک استفاده می شود. سپس یک جامعه به عنوان حداکثر اتحادیه تعریف می شود ${\displaystyle k}$ - کلیساهایی که در آن می توانیم به هر مکانی برسیم ${\displaystyle k}$ - از هر کس دیگری استفاده کنید ${\displaystyle k}$ - از طریق مجموعه ای از ${\displaystyle k}$ مجاورت کلیک یعنی جوامع فقط اجزای متصل شده در نمودار دسته هستند. از آنجا که یک گره می تواند به چندین مورد مختلف تعلق داشته باشد ${\displaystyle k}$ خوشه های لایه برداری به طور همزمان ، جوامع می توانند با یکدیگر همپوشانی داشته باشند.

روش های آزمایش الگوریتم های جوامع

ارزیابی الگوریتم ها ، برای تشخیص که در تشخیص ساختار جامعه بهتر هستند ، هنوز یک سوال باز است. این باید بر اساس تجزیه و تحلیل شبکه های ساختار شناخته شده باشد. یک نمونه معمول ، آزمون "چهار گروه" است که در آن شبکه ای به چهار گروه با اندازه یکسان تقسیم می شود (معمولاً هر کدام از آنها 32 گره است) و احتمال اتصال در داخل و بین گروه ها متفاوت است تا ساختارهای کم و بیش چالش برانگیزی برای تشخیص الگوریتم این نمودارهای معیار مورد خاصی از مدل پارتیشن L ^[۳۹] Condon و Karp یا به طور کلی " مدل های بلوک تصادفی " است ، یک کلاس کلی از مدل های شبکه تصادفی حاوی ساختار جامعه. معیارهای انعطاف پذیر دیگری نیز ارائه شده است که امکان تغییر اندازه گروه و توزیع درجه غیرپیشرفته را فراهم می کند ، مانند معیار LFR ^{[۴۰] [۴۱]} که گسترش معیار چهار گروه است که شامل توزیع های ناهمگن درجه گره و اندازه جامعه است و باعث می شود یک آزمایش شدیدتر از روش های تشخیص جامعه. ^{[۴۲] [۴۳]}

معیارهای رایج تولید شده رایانه ای با شبکه ای از جوامع کاملاً مشخص شروع می شوند. سپس ، این ساختار با سیم کشی یا حذف پیوندها تخریب می شود و تشخیص پارتیشن اصلی برای الگوریتم ها دشوارتر می شود. در پایان ، شبکه به نقطه ای می رسد که اساساً تصادفی است. این نوع معیار را می توان "باز" نامید. عملکرد این معیارها با معیارهایی مانند اطلاعات متقابل عادی یا تغییر اطلاعات ارزیابی می شود . آنها راه حل بدست آمده توسط یک الگوریتم ^[۴۱] با ساختار اصلی جامعه مقایسه می کنند و شباهت هر دو پارتیشن را ارزیابی می کنند.

قابل تشخیص بودن

دز سال های اخیر، نتایج نسبتاً شگفت انگیزی توسط گروه های مختلف به دست آمده است که نشان دهنده ی وجود یک مرحله انتقال در مسئله شناسایی جامعه است، این نتایج نشان می دهند که هرچه تراکم اتصالات درون جوامع و بین جوامع بیشتر می شود یا هر دو کوچکتر می شوند (به طور یکسان، با ضعف بیش از حد ساختار جامعه یا شبکه بسیار پراکنده)، ناگهان جوامع غیرقابل شناسایی می شوند. یعنی جوامع هنوز وجود دارند، زیرا وجود و عدم وجود لبه ها همچنان با عضویت جامعه در نقاط انتهایی آنها ارتباط دارد. اما نام گذاری و برچسب زدن گره ها بهتر از شانس، یا حتی تشخیص نمودار از نمودار تولید شده توسط یک مدل پوچ مانند مدل Erdos – Renyi بدون ساختار جامعه ، از نظر تئوری غیرممکن است. این انتقال مستقل از نوع الگوریتمی است که برای شناسایی جوامع استفاده می شود ، و این بدان معناست که محدودیت اساسی در توانایی ما برای شناسایی جوامع در شبکه ها ، حتی با استنباط بهینه بیزی (یعنی بدون در نظر گرفتن منابع محاسباتی ما) وجود دارد. ^{[۴۴] [۴۵] [۴۶]}

یک مدل بلوک تصادفی را فرض کنید که ${\displaystyle n}$ گره دارد، ${\displaystyle q=2}$ گروه هایی با اندازه یکسان هستند، و ${\displaystyle p_{\text{in}}}$ و ${\displaystyle p_{\text{out}}}$ را برای احتمال اتصال در داخل و بین گروه ها دز نظر بگیرید. حال اگر ${\displaystyle p_{\text{in}}>p_{\text{out}}}$ آنگاه شبکه دارای ساختار جامعه است زیرا تراکم پیوند در داخل گروه ها بیشتر از تراکم پیوند بین گروه ها خواهد بود. در حالت پراکنده، ${\displaystyle p_{\text{in}}}$ و ${\displaystyle p_{\text{out}}}$ مقیاس به عنوان ${\displaystyle O(1/n)}$ به طوری که میانگین درجه ثابت باشد:

${\displaystyle p_{\text{in}}=c_{\text{in}}/n}$ و ${\displaystyle p_{\text{out}}=c_{\text{out}}/n}$

سپس تشخیص جوامع غیرممکن می شود: ^[۴۵]

${\displaystyle c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}}$

انعطاف پذیری شبکه های مدولار

انعطاف پذیری شبکه های پیمانه ای به دلیل خرابی گره یا لینک معمولاً با استفاده از تئوری نفوذ (percolation theory) مطالعه می شود. ساختار شبکه هنگام حمله به گره های داخلی (به عنوان مثال گره هایی که جوامع را به یکدیگر متصل می کنند) مورد مطالعه قرار گرفته است. ^[۴۷] همچنین، اخیرا مطالعه ای به مطالعه ی چگونگی تقویت ارتباطات بین جامعه برای مقاومت در برابر جوامع پرداخته است. ^[۴۸]

اپیدمی ها در شبکه های مدولار

مطالعه مدل های اپیدمی در شبکه های پیمانه ای توسط والدز و همکاران انجام شده است. ^[۴۹] این نویسندگان همچنین معیار اعلام بیماری همه‌گیر را مورد مطالعه قرار دادند.

شبکه های مدولار فضایی

تصویرگری از مدل. مدل مدولار فضایی نشان دهنده ساختاری از شبکه کانالهای آلودگی در داخل شهرها (ماژول ها) و بین شهرها است. در داخل یک شهر ، کانالهای آلودگی متراکم هستند و بصورت تصادفی بین مناطق مختلف شهر پخش می شوند (پیوندهای سبز) مانند شبکه Erdős – Rénii که دارای ساختاری کاملاً تصادفی است در حالیکه کانالهای آلودگی از یک شهر به شهر دیگر معمولاً بین شهرهای همسایه امکان پذیر است (قرمز پیوندها) دارای ساختار مکانی مانند

مدلی برای شبکه های مدولار فضایی توسط Gross و همکاران ایجاد شده است. ^[۵۰] این مدل به عنوان مثال ، زیرساخت ها را در کشوری توصیف می کند که در آن جوامع (ماژول ها) شهرهای دارای اتصالات زیادی را در فضای دو بعدی نشان می دهند. پیوندهای بین جوامع (شهرها) کمتر و معمولاً با نزدیکترین همسایگان است (شکل 2 را ببینید). شیوع اپیدمی در چنین شبکه هایی در گروس و هاولین بررسی شده است. ^[۵۱]

همچنین ببینید

• شبکه پیچیده
• سلسله مراتب
• نظریه شبکه
• نظریه تراوش 

• شناسایی جامعه در نمودارها - مقدمه
• آیا پیاده سازی الگوریتم هایی برای تشخیص جامعه در نمودارها وجود دارد؟ - پشته سرریز
• تفاوت های الگوریتم های تشخیص جامعه در igraph چیست؟ - پشته سرریز

1. M. Girvan; M. E. J. Newman (2002). "Community structure in social and biological networks". Proc. Natl. Acad. Sci. USA. 99 (12): 7821–7826. arXiv:cond-mat/0112110. Bibcode:2002PNAS...99.7821G. doi:10.1073/pnas.122653799. PMC 122977. PMID 12060727. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «ComSocBio» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
2. S. Fortunato (2010). "Community detection in graphs". Phys. Rep. 486 (3–5): 75–174. arXiv:0906.0612. Bibcode:2010PhR...486...75F. doi:10.1016/j.physrep.2009.11.002.
3. F. D. Malliaros; M. Vazirgiannis (2013). "Clustering and community detection in directed networks: A survey". Phys. Rep. 533 (4): 95–142. arXiv:1308.0971. Bibcode:2013PhR...533...95M. doi:10.1016/j.physrep.2013.08.002.
4. M. A. Porter; J.-P. Onnela; P. J. Mucha (2009). "Communities in Networks" (PDF). Notices of the American Mathematical Society. 56: 1082–1097, 1164–1166. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Notices» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
5. Fani, Hossein (2017). "Community detection in social networks". Encyclopedia with Semantic Computing and Robotic Intelligence. Vol. 1. pp. 1630001 [8]. doi:10.1142/S2425038416300019. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «escri_FaniE17» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
6. Hamdaqa, Mohammad; Tahvildari, Ladan; LaChapelle, Neil; Campbell, Brian (2014). "Cultural Scene Detection Using Reverse Louvain Optimization". Science of Computer Programming. 95: 44–72. doi:10.1016/j.scico.2014.01.006.
7. M.E.J.Neman (2006). "Finding community structure in networks using the eigenvectors of matrices". Phys. Rev. E. 74 (3): 1–19. arXiv:physics/0605087. Bibcode:2006PhRvE..74c6104N. doi:10.1103/PhysRevE.74.036104. PMID 17025705.
8. Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). "Data reduction for spectral clustering to analyze high throughput flow cytometry data". BMC Bioinformatics. 11 (1): 403. doi:10.1186/1471-2105-11-403. PMC 2923634. PMID 20667133.
9. Aaron Clauset; Cristopher Moore; M.E.J. Newman (2008). "Hierarchical structure and the prediction of missing links in networks". Nature. 453 (7191): 98–101. arXiv:0811.0484. Bibcode:2008Natur.453...98C. doi:10.1038/nature06830. PMID 18451861.
10. M. E. J. Newman (2004). "Detecting community structure in networks". Eur. Phys. J. B. 38 (2): 321–330. Bibcode:2004EPJB...38..321N. doi:10.1140/epjb/e2004-00124-y. {{cite journal}}: |hdl-access= requires |hdl= (help)
11. Alvarez, Alejandro J.; Sanz-Rodríguez, Carlos E.; Cabrera, Juan Luis (2015-12-13). "Weighting dissimilarities to detect communities in networks". Phil. Trans. R. Soc. A. 373 (2056): 20150108. Bibcode:2015RSPTA.37350108A. doi:10.1098/rsta.2015.0108. ISSN 1364-503X. PMID 26527808.
12. Ahn, Y.-Y.; Bagrow, J.P.; Lehmann, S. (2010). "Link communities reveal multi-scale complexity in networks". Nature. 466 (7307): 761–764. arXiv:0903.3178. doi:10.1038/nature09182.
13. Pascual-García, Alberto; Bell, Thomas (2020). "functionInk: An efficient method to detect functional groups in multidimensional networks reveals the hidden structure of ecological communities". Methods Ecol Evol. 11 (7): 804–817. doi:10.1111/2041-210X.13377. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «functionink_2020» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
14. M. E. J. Newman (2004). "Fast algorithm for detecting community structure in networks". Phys. Rev. E. 69 (6): 066133. arXiv:cond-mat/0309508. Bibcode:2004PhRvE..69f6133N. doi:10.1103/PhysRevE.69.066133. PMID 15244693. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «fast» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
15. L. Danon; J. Duch; A. Díaz-Guilera; A. Arenas (2005). "Comparing community structure identification". J. Stat. Mech. 2005 (9): P09008. arXiv:cond-mat/0505245. Bibcode:2005JSMTE..09..008D. doi:10.1088/1742-5468/2005/09/P09008.
16. R. Guimera; L. A. N. Amaral (2005). "Functional cartography of complex metabolic networks". Nature. 433 (7028): 895–900. arXiv:q-bio/0502035. Bibcode:2005Natur.433..895G. doi:10.1038/nature03288. PMC 2175124. PMID 15729348.
17. V.D. Blondel; J.-L. Guillaume; R. Lambiotte; E. Lefebvre (2008). "Fast unfolding of community hierarchies in large networks". J. Stat. Mech. 2008 (10): P10008. arXiv:0803.0476. Bibcode:2008JSMTE..10..008B. doi:10.1088/1742-5468/2008/10/P10008.
18. "Lightning-fast Community Detection in Social Media: A Scalable Implementation of the Louvain Algorithm". 2013.
19. J. Guo; P. Singh; K.E. Bassler (2019). "Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks". Scientific Reports. 9 (14234): 14234. arXiv:1909.10491. Bibcode:2019NatSR...914234G. doi:10.1038/s41598-019-50739-3. PMC 6775136. PMID 31578406.
20. "RenEEL-Modularity". 31 October 2019.
21. S. Fortunato; M. Barthelemy (2007). "Resolution limit in community detection". Proceedings of the National Academy of Sciences of the United States of America. 104 (1): 36–41. arXiv:physics/0607100. Bibcode:2007PNAS..104...36F. doi:10.1073/pnas.0605965104. PMC 1765466. PMID 17190818.
22. B. H. Good; Y.-A. de Montjoye; A. Clauset (2010). "The performance of modularity maximization in practical contexts". Phys. Rev. E. 81 (4): 046106. arXiv:0910.0165. Bibcode:2010PhRvE..81d6106G. doi:10.1103/PhysRevE.81.046106. PMID 20481785.
23. Holland, Paul W.; Kathryn Blackmond Laskey; Samuel Leinhardt (June 1983). "Stochastic blockmodels: First steps". Social Networks. 5 (2): 109–137. doi:10.1016/0378-8733(83)90021-7. ISSN 0378-8733.
24. Airoldi, Edoardo M.; David M. Blei; Stephen E. Fienberg; Eric P. Xing (June 2008). "Mixed Membership Stochastic Blockmodels". J. Mach. Learn. Res. 9: 1981–2014. ISSN 1532-4435. PMC 3119541. PMID 21701698. Retrieved 2013-10-09.
25. Ball, Brian; Brian Karrer; M. E. J. Newman (2011). "Efficient and principled method for detecting communities in networks". Physical Review E. 84 (3): 036103. arXiv:1104.3590. Bibcode:2011PhRvE..84c6103B. doi:10.1103/PhysRevE.84.036103. PMID 22060452.
26. Karrer, Brian; M. E. J. Newman (2011-01-21). "Stochastic blockmodels and community structure in networks". Physical Review E. 83 (1): 016107. arXiv:1008.3926. Bibcode:2011PhRvE..83a6107K. doi:10.1103/PhysRevE.83.016107. PMID 21405744.
27. Peixoto, Tiago P. (2014-03-24). "Hierarchical Block Structures and High-Resolution Model Selection in Large Networks". Physical Review X. 4 (1): 011047. arXiv:1310.4377. Bibcode:2014PhRvX...4a1047P. doi:10.1103/PhysRevX.4.011047.
28. Martin Rosvall; Carl T. Bergstrom (2007). "An information-theoretic framework for resolving community structure in complex networks". Proceedings of the National Academy of Sciences of the United States of America. 104 (18): 7327–7331. arXiv:physics/0612035. Bibcode:2007PNAS..104.7327R. doi:10.1073/pnas.0611034104. PMC 1855072. PMID 17452639.
29. P. Peixoto, T. (2013). "Parsimonious Module Inference in Large Networks". Phys. Rev. Lett. 110 (14): 148701. arXiv:1212.4794. Bibcode:2013PhRvL.110n8701P. doi:10.1103/PhysRevLett.110.148701. PMID 25167049.
30. Yan, Xiaoran; Jacob E. Jensen; Florent Krzakala; Cristopher Moore; Cosma Rohilla Shalizi; Lenka Zdeborová; Pan Zhang; Yaojia Zhu (2012-07-17). "Model Selection for Degree-corrected Block Models". Journal of Statistical Mechanics: Theory and Experiment. 2014 (5): P05007. arXiv:1207.3994. Bibcode:2014JSMTE..05..007Y. doi:10.1088/1742-5468/2014/05/P05007. PMC 4498413. PMID 26167197.
31. Gopalan, Prem K.; David M. Blei (2013-09-03). "Efficient discovery of overlapping communities in massive networks". Proceedings of the National Academy of Sciences. 110 (36): 14534–14539. Bibcode:2013PNAS..11014534G. doi:10.1073/pnas.1221839110. ISSN 0027-8424. PMC 3767539. PMID 23950224.
32. Decelle, Aurelien; Florent Krzakala; Cristopher Moore; Lenka Zdeborová (2011-12-12). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". Physical Review E. 84 (6): 066106. arXiv:1109.3041. Bibcode:2011PhRvE..84f6106D. doi:10.1103/PhysRevE.84.066106. PMID 22304154.
33. Peixoto, Tiago P. (2014-01-13). "Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models". Physical Review E. 89 (1): 012804. arXiv:1310.4378. Bibcode:2014PhRvE..89a2804P. doi:10.1103/PhysRevE.89.012804. PMID 24580278.
34. Guimerà, Roger; Marta Sales-Pardo (2009-12-29). "Missing and spurious interactions and the reconstruction of complex networks". Proceedings of the National Academy of Sciences. 106 (52): 22073–22078. arXiv:1004.4791. Bibcode:2009PNAS..10622073G. doi:10.1073/pnas.0908366106. PMC 2799723. PMID 20018705.
35. Clauset, Aaron; Cristopher Moore; M. E. J. Newman (2008-05-01). "Hierarchical structure and the prediction of missing links in networks". Nature. 453 (7191): 98–101. arXiv:0811.0484. Bibcode:2008Natur.453...98C. doi:10.1038/nature06830. ISSN 0028-0836. PMID 18451861.
36. M.G. Everett; S.P. Borgatti (1998). "Analyzing Clique Overlap Connections". Connections. 21: 49.
37. T.S. Evans (2010). "Clique Graphs and Overlapping Communities". J. Stat. Mech. 2010 (12): P12037. arXiv:1009.0638. Bibcode:2010JSMTE..12..037E. doi:10.1088/1742-5468/2010/12/P12037.
38. G. Palla; I. Derényi; I. Farkas; T. Vicsek (2005). "Uncovering the overlapping community structure of complex networks in nature and society". Nature. 435 (7043): 814–818. arXiv:physics/0506133. Bibcode:2005Natur.435..814P. doi:10.1038/nature03607. PMID 15944704.
39. Condon, A.; Karp, R. M. (2001). "Algorithms for graph partitioning on the planted partition model". Random Struct. Algor. 18 (2): 116–140. CiteSeerX 10.1.1.22.4340. doi:10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2.
40. A. Lancichinetti; S. Fortunato; F. Radicchi (2008). "Benchmark graphs for testing community detection algorithms". Phys. Rev. E. 78 (4): 046110. arXiv:0805.4770. Bibcode:2008PhRvE..78d6110L. doi:10.1103/PhysRevE.78.046110. PMID 18999496.
41. Fathi, Reza. "Efficient Distributed Community Detection in the Stochastic Block Model". arXiv:1904.07494. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «fat19» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
42. A bot will complete this citation soon. Click here to jump the queue arXiv:1606.01169.
43. Pasta, M. Q.; Zaidi, F. (2017). "Topology of Complex Networks and Performance Limitations of Community Detection Algorithms". IEEE Access. 5: 10901–10914. doi:10.1109/ACCESS.2017.2714018.
44. Reichardt, J.; Leone, M. (2008). "(Un)detectable Cluster Structure in Sparse Networks". Phys. Rev. Lett. 101 (78701): 1–4. arXiv:0711.1452. Bibcode:2008PhRvL.101g8701R. doi:10.1103/PhysRevLett.101.078701. PMID 18764586.
45. Decelle, A.; Krzakala, F.; Moore, C.; Zdeborová, L. (2011). "Inference and Phase Transitions in the Detection of Modules in Sparse Networks". Phys. Rev. Lett. 107 (65701): 1–5. arXiv:1102.1182. Bibcode:2011PhRvL.107f5701D. doi:10.1103/PhysRevLett.107.065701. PMID 21902340.
46. Nadakuditi, R.R; Newman, M.E.J. (2012). "Graph Spectra and the Detectability of Community Structure in Networks". Phys. Rev. Lett. 108 (188701): 1–5. arXiv:1205.1813. Bibcode:2012PhRvL.108r8701N. doi:10.1103/PhysRevLett.108.188701. PMID 22681123.
47. Shai, S.; Kenett, D.Y.; Kenett, Y.N.; Faust, M.; Dobson, S.; Havlin, S. (2015). "Critical tipping point distinguishing two types of transitions in modular network structures". Phys. Rev. E. 92 (6): 062805. Bibcode:2015PhRvE..92f2805S. doi:10.1103/PhysRevE.92.062805. PMID 26764742.
48. Dong, Gaogao; Fan, Jingfang; Shekhtman, Louis M; Shai, Saray; Du, Ruijin; Tian, Lixin; Chen, Xiaosong; Stanley, H Eugene; Havlin, Shlomo (2018). "Resilience of networks with community structure behaves as if under an external field". Proceedings of the National Academy of Sciences. 115 (27): 6911–6915. arXiv:1805.01032. Bibcode:2018PNAS..115.6911D. doi:10.1073/pnas.1801588115. PMC 6142202. PMID 29925594.
49. LD Valdez, LA Braunstein, S Havlin (2020). "Epidemic spreading on modular networks: The fear to declare a pandemic". Physical Review E. 101 (3).
50. Bnaya Gross, Dana Vaknin, Sergey Buldyrev, Shlomo Havlin (2020). "Two transitions in spatial modular networks". New Journal of Physics. 22 (5): 053002. doi:10.1088/1367-2630/ab8263.
51. Gross, B.; Havlin, S. (2020). "Epidemic spreading and control strategies in spatial modular network". Applied Network Science. 5: 1–14.