ساختار جامعه: تفاوت میان نسخه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
23Cse104 (بحث | مشارکت‌ها)
۱۰ ویرایش‌ها
ایجاد شده توسط ترجمهٔ صفحهٔ «Community structure»
23Cse104 (بحث | مشارکت‌ها)
۱۰ ویرایش‌ها
ایجاد شده توسط ترجمهٔ صفحهٔ «Community structure»
خط ۱: خط ۱:
در مطالعه [[شبکه پیچیده|شبکه های پیچیده]]،اگر گره های شبکه بتوانند به راحتی در مجموعه گره هایی (بالقوه همپوشانی) قرار گیرند، به گونه ای که هر مجموعه از گره ها به طور متراکم در داخل متصل شوند گفته می شود که شبکه دارای '''ساختار جامعه''' است . در مورد خاص یافته های ''عدم تداخل'' جامعه ، این بدان معنی است که شبکه به طور طبیعی به گروه هایی از گره ها با اتصالات متراکم داخلی و ارتباطات پراکنده بین گروه ها تقسیم می شود. اما جوامع ''همپوشانی'' نیز مجاز است. تعریف کلی تر بر این اصل استوار است که اگر جفت گره ها هر دو عضو یک جامعه (ها) باشند ، به احتمال زیاد به هم متصل می شوند و در صورت عدم اشتراک در اجتماعات ، احتمال اتصال آنها کمتر است. یک مسئله مرتبط اما متفاوت جستجوی جامعه است ، جایی که هدف یافتن جامعه ای است که یک راس خاص به آن تعلق دارد.
<nowiki>{{</nowiki>[[الگو:در دست ساخت|در دست ساخت]]<nowiki>}}</nowiki>


== خواص ==
این مقاله در دست ترجمه است لطفا پاک نشود!

در مطالعه [[شبکه پیچیده|شبکه های پیچیده]] ، گفته می شود که یک شبکه دارای '''ساختار جامعه است''' اگر گره های شبکه بتوانند به راحتی در مجموعه گره هایی (بالقوه همپوشانی) قرار گیرند ، به گونه ای که هر مجموعه از گره ها به طور متراکم در داخل متصل شوند. در مورد خاص یافته های ''عدم تداخل'' جامعه ، این بدان معنی است که شبکه به طور طبیعی به گروه هایی از گره ها با اتصالات متراکم داخلی و ارتباطات پراکنده بین گروه ها تقسیم می شود. اما جوامع ''همپوشانی'' نیز مجاز است. تعریف کلی تر بر این اصل استوار است که اگر جفت گره ها هر دو عضو یک جامعه (ها) باشند ، به احتمال زیاد به هم متصل می شوند و در صورت عدم اشتراک در اجتماعات ، احتمال اتصال آنها کمتر است. یک مسئله مرتبط اما متفاوت جستجوی جامعه است ، جایی که هدف یافتن جامعه ای است که یک راس خاص به آن تعلق دارد.
[[پرونده:Network_Community_Structure.svg|چپ|بندانگشتی| شکل 1: طرحی از یک [[شبکه پیچیده|شبکه]] کوچک که '''ساختار جامعه را''' نشان '''می دهد''' ، با سه گروه گره با اتصالات داخلی متراکم و اتصالات پراکنده بین گروه ها.]]
[[پرونده:Network_Community_Structure.svg|چپ|بندانگشتی| شکل 1: طرحی از یک [[شبکه پیچیده|شبکه]] کوچک که '''ساختار جامعه را''' نشان '''می دهد''' ، با سه گروه گره با اتصالات داخلی متراکم و اتصالات پراکنده بین گروه ها.]]
در بررسی [[شبکه پیچیده|شبکه ها]] ، از قبیل [[شبکه پیچیده|شبکه های]] رایانه ای و اطلاعاتی ، شبکه های اجتماعی و شبکه های بیولوژیکی ، تعدادی از ویژگی های مختلف به طور معمول رخ داده است ، از جمله [[شبکه جهان‌کوچک|ویژگی جهان کوچک]] ، [[توزیع درجه]] [[شبکه بی‌مقیاس|های سنگین]] و [[ضریب خوشگی|خوشه بندی]] و غیره ویژگی مشترک دیگر ، ساختار جامعه است. <ref name="ComSocBio">
در بررسی [[شبکه پیچیده|شبکه ها]] ، از قبیل [[شبکه پیچیده|شبکه های]] رایانه ای و اطلاعاتی ، شبکه های اجتماعی و شبکه های بیولوژیکی، تعدادی از ویژگی‌های مختلف به طور کلی پیدا شده‌است، از جمله [[شبکه جهان‌کوچک|ویژگی جهان کوچک]] ، [[توزیع درجه]] [[شبکه بی‌مقیاس|های سنگین]] و [[ضریب خوشگی|خوشه بندی]] و غیره. یکی از ویژگی های مشترک دیگر ، ساختار جامعه است. <ref name="ComSocBio">
{{Cite journal|last=M. Girvan|last2=M. E. J. Newman|year=2002|title=Community structure in social and biological networks|journal=Proc. Natl. Acad. Sci. USA|volume=99|issue=12|pages=7821–7826|arxiv=cond-mat/0112110|bibcode=2002PNAS...99.7821G|doi=10.1073/pnas.122653799|pmc=122977|pmid=12060727}}</ref> <ref name="PhysRep">
{{Cite journal|last=M. Girvan|last2=M. E. J. Newman|year=2002|title=Community structure in social and biological networks|journal=Proc. Natl. Acad. Sci. USA|volume=99|issue=12|pages=7821–7826|arxiv=cond-mat/0112110|bibcode=2002PNAS...99.7821G|doi=10.1073/pnas.122653799|pmc=122977|pmid=12060727}}</ref> <ref name="PhysRep">
{{Cite journal|last=S. Fortunato|year=2010|title=Community detection in graphs|journal=Phys. Rep.|volume=486|issue=3–5|pages=75–174|arxiv=0906.0612|bibcode=2010PhR...486...75F|doi=10.1016/j.physrep.2009.11.002}}
{{Cite journal|last=S. Fortunato|year=2010|title=Community detection in graphs|journal=Phys. Rep.|volume=486|issue=3–5|pages=75–174|arxiv=0906.0612|bibcode=2010PhR...486...75F|doi=10.1016/j.physrep.2009.11.002}}
خط ۱۲: خط ۱۰:
</ref> <ref name="Notices">
</ref> <ref name="Notices">
{{Cite journal|last=M. A. Porter|last2=J.-P. Onnela|last3=P. J. Mucha|year=2009|title=Communities in Networks|url=http://www.ams.org/notices/200909/rtx090901082p.pdf|journal=Notices of the American Mathematical Society|volume=56|pages=1082–1097, 1164–1166}}
{{Cite journal|last=M. A. Porter|last2=J.-P. Onnela|last3=P. J. Mucha|year=2009|title=Communities in Networks|url=http://www.ams.org/notices/200909/rtx090901082p.pdf|journal=Notices of the American Mathematical Society|volume=56|pages=1082–1097, 1164–1166}}
</ref> <ref name="escri_FaniE17">{{Cite encyclopedia|last=Fani|first=Hossein|title=Community detection in social networks|encyclopedia=Encyclopedia with Semantic Computing and Robotic Intelligence|date=2017|doi=10.1142/S2425038416300019|volume=1|pages=1630001 [8]}}</ref> در زمینه شبکه ها ، ساختار جامعه به وقوع گروهی از گره ها در شبکه اشاره دارد که متراکم تر از بقیه شبکه هستند ، همانطور که در تصویر نمونه سمت راست نشان داده شده است. این ناهمگنی اتصالات نشان می دهد که شبکه دارای تقسیمات طبیعی خاصی در درون خود است.
</ref> <ref name="escri_FaniE17">{{Cite encyclopedia|last=Fani|first=Hossein|title=Community detection in social networks|encyclopedia=Encyclopedia with Semantic Computing and Robotic Intelligence|date=2017|doi=10.1142/S2425038416300019|volume=1|pages=1630001 [8]}}</ref> در زمینه شبکه ها، ساختار جامعه به پدید آمدن گروهی از گره ها در شبکه اشاره دارد که از بقیه شبکه متراکم تر هستند، مانند تصویر سمت راست. این ناهمگنی در اتصالات نشاندهنده ی این است که شبکه در درون خود، دارای تقسیمات طبیعی خاصی است.

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

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

== اهمیت ==
ساختارهای جامعه در شبکه های واقعی بسیار رایج است. شبکه های اجتماعی شامل گروه های اجتماعی بر اساس مکان مشترک، علایق، شغل و غیره است. <ref name="escri_FaniE17">{{Cite encyclopedia|last=Fani|first=Hossein|title=Community detection in social networks|encyclopedia=Encyclopedia with Semantic Computing and Robotic Intelligence|date=2017|doi=10.1142/S2425038416300019|volume=1|pages=1630001 [8]}}<cite class="citation encyclopaedia cs1" data-ve-ignore="true" id="CITEREFFaniBagheri,_Ebrahim2017">Fani, Hossein; Bagheri, Ebrahim (2017). "Community detection in social networks". ''Encyclopedia with Semantic Computing and Robotic Intelligence''. '''1'''. pp.&nbsp;1630001 [8]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1142/S2425038416300019|10.1142/S2425038416300019]].</cite></ref> <ref>{{Cite journal|last=Hamdaqa|first=Mohammad|last2=Tahvildari, Ladan|last3=LaChapelle, Neil|last4=Campbell, Brian|date=2014|title=Cultural Scene Detection Using Reverse Louvain Optimization|url=https://zenodo.org/record/889712|journal=Science of Computer Programming|volume=95|pages=44–72|doi=10.1016/j.scico.2014.01.006|doi-access=free}}</ref>

پیدا کردن یک ساختار اجتماعی زیربنایی در یک شبکه، در صورت وجود، به چند دلیل دارای اهمیت است. جوامع برای ما امکان ایجاد یک نقشه در مقیاس بزرگ از شبکه را فراهم می سازد، زیرا جوامع منفرد مانند متا گره ها (meta-nodes) در شبکه عمل می کنند که مطالعه آن را آسان تر می کند. <ref name="Nemaneigen">{{Cite journal|last=M.E.J.Neman|year=2006|title=Finding community structure in networks using the eigenvectors of matrices|journal=Phys. Rev. E|volume=74|issue=3|pages=1–19|arxiv=physics/0605087|bibcode=2006PhRvE..74c6104N|doi=10.1103/PhysRevE.74.036104|pmid=17025705}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFM.E.J.Neman2006">M.E.J.Neman (2006). "Finding community structure in networks using the eigenvectors of matrices". ''Phys. Rev. E''. '''74''' (3): 1–19. [[آرکایو (بایگانی نوشتارهای علمی)|arXiv]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/physics/0605087 physics/0605087]</span>. [[بیبکد|Bibcode]]:[https://ui.adsabs.harvard.edu/abs/2006PhRvE..74c6104N 2006PhRvE..74c6104N]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1103/PhysRevE.74.036104|10.1103/PhysRevE.74.036104]]. [[پاب‌مد|PMID]]&nbsp;[//pubmed.ncbi.nlm.nih.gov/17025705 17025705]. [[سمانتیک اسکالر|S2CID]]&nbsp;[https://api.semanticscholar.org/CorpusID:138996 138996].</cite></ref>

جوامع فردی همچنین نشان دهنده ی عملکرد سیستم ارائه‌شده توسط شبکه هستند، چرا که جوامع اغلب با واحدهای عملکردی سیستم سروکار دارند. در شبکه های متابولیکی، این گروه های عملکردی مربوط به چرخه ها یا مسیرها هستند در حالی که در [[تعامل پروتئین-پروتئین|شبکه تعامل پروتئین-پروتئین]] ، جوامع مربوط به پروتئین ها، دارای عملکردی مشابه با داخل یک سلول بیولوژیکی هستند. به طور مشابه، شبکه‌های استنادی، جوامع را با موضوع تحقیق تشکیل می‌دهند.<ref name="ComSocBio">
{{Cite journal|last=M. Girvan|last2=M. E. J. Newman|year=2002|title=Community structure in social and biological networks|journal=Proc. Natl. Acad. Sci. USA|volume=99|issue=12|pages=7821–7826|arxiv=cond-mat/0112110|bibcode=2002PNAS...99.7821G|doi=10.1073/pnas.122653799|pmc=122977|pmid=12060727}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFM._GirvanM._E._J._Newman2002">[[میشل گیروان|M. Girvan]]; M. E. J. Newman (2002). [//www.ncbi.nlm.nih.gov/pmc/articles/PMC122977 "Community structure in social and biological networks"]. ''Proc. Natl. Acad. Sci. USA''. '''99''' (12): 7821–7826. [[آرکایو (بایگانی نوشتارهای علمی)|arXiv]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/cond-mat/0112110 cond-mat/0112110]</span>. [[بیبکد|Bibcode]]:[https://ui.adsabs.harvard.edu/abs/2002PNAS...99.7821G 2002PNAS...99.7821G]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1073/pnas.122653799|10.1073/pnas.122653799]]. [[پاب‌مد سنترال|PMC]]&nbsp;<span class="cs1-lock-free" title="Freely accessible">[//www.ncbi.nlm.nih.gov/pmc/articles/PMC122977 122977]</span>. [[پاب‌مد|PMID]]&nbsp;[//pubmed.ncbi.nlm.nih.gov/12060727 12060727].</cite></ref> توانایی شناسایی این ساختارهای فرعی درون یک شبکه، می‌تواند دیدگاهب را نسبت به چگونگی عملکرد شبکه و توپولوژی ایجاد کند. چنین بینشی می تواند در بهبود برخی الگوریتم های نمودار مانند خوشه طیفی مفید باشد. <ref>{{Cite journal|last=Zare|first=Habil|last2=P. Shooshtari|last3=A. Gupta|last4=R. Brinkman|date=2010|title=Data reduction for spectral clustering to analyze high throughput flow cytometry data|journal=BMC Bioinformatics|volume=11|issue=1|pages=403|doi=10.1186/1471-2105-11-403|pmc=2923634|pmid=20667133}}</ref>

یکی از دلایل اهمیت جوامع این است که آنها معمولا دارای خصوصیات بسیار متفاوتی نسبت به خصوصیات متوسط شبکه ها هستند. بنابراین، فقط با تمرکز روی این ویژگی های متوسط، معمولاً بسیاری از ویژگی های مهم و جالب را در داخل شبکه از دست می دهیم. به عنوان مثال ، در یک شبکه اجتماعی معین، هر دو گروه اجتماعی و کم گو باید همزمان با یکدیگر وجود داشته باشند. <ref name="Nemaneigen">{{Cite journal|last=M.E.J.Neman|year=2006|title=Finding community structure in networks using the eigenvectors of matrices|journal=Phys. Rev. E|volume=74|issue=3|pages=1–19|arxiv=physics/0605087|bibcode=2006PhRvE..74c6104N|doi=10.1103/PhysRevE.74.036104|pmid=17025705}}</ref>

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

در آخر، برنامه ای مهم که جامعه یابی در علم شبکه یافته است، پیش بینی لینک های از دست رفته و شناسایی پیوندهای کاذب در شبکه است. در طی فرآیند اندازه گیری، برخی از لینک ها ممکن است به چند دلیل مشاهده نشوند. به همین ترتیب، برخی از لینک ها به دلیل خطاهای اندازه گیری، می توانند به اشتباه وارد داده شوند. هر دو این موارد به خوبی توسط الگوریتم تشخیص جامعه اداره می شوند زیرا امکان تعیین احتمال وجود یک یال بین یک جفت گره‌ها وجود دارد. <ref name="clauset_missing">{{Cite journal|last=Aaron Clauset|last2=Cristopher Moore|last3=M.E.J. Newman|year=2008|title=Hierarchical structure and the prediction of missing links in networks|journal=Nature|volume=453|issue=7191|pages=98–101|arxiv=0811.0484|bibcode=2008Natur.453...98C|doi=10.1038/nature06830|pmid=18451861}}</ref>

== الگوریتم هایی برای یافتن جوامع ==
پیدا کردن جوامع در یک شبکه دلخواه می تواند یک کار دشوار [[نظریه پیچیدگی محاسباتی|محاسباتی]] باشد. تعداد جوامع، در صورت وجود، در داخل شبکه معمولاً ناشناخته است و جوامع اغلب از اندازه و/یا تراکم نابرابر برخوردارند. با وجود این سختی ها، روش های مختلفی برای جامعه یابی ایجاد شده و با موفقیت های زیادی همراه بوده است. <ref name="Notices">
{{Cite journal|last=M. A. Porter|last2=J.-P. Onnela|last3=P. J. Mucha|year=2009|title=Communities in Networks|url=http://www.ams.org/notices/200909/rtx090901082p.pdf|journal=Notices of the American Mathematical Society|volume=56|pages=1082–1097, 1164–1166}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFM._A._PorterJ.-P._OnnelaP._J._Mucha2009">M. A. Porter; J.-P. Onnela; P. J. Mucha (2009). [http://www.ams.org/notices/200909/rtx090901082p.pdf "Communities in Networks"] <span class="cs1-format">(PDF)</span>. ''Notices of the American Mathematical Society''. '''56''': 1082–1097, 1164–1166.</cite>
</ref>

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

در روش حداقل برش (minimum cut)، شبکه به تعدادی از پیش تعیین شده از قطعات تقسیم می شود، که معمولاً تقریبا به اندازه یک اندازه، طوری انتخاب می شوند که تعداد لبه های بین گروه ها حداقل شود. این روش در بسیاری از کاربردها خوب عمل می‌کند که در اصل در نظر گرفته‌شده اما کم‌تر از ایده‌آل برای یافتن ساختار اجتماعی در شبکه‌های عمومی است چرا که جوامع را بدون در نظر گرفتن اینکه آیا آن‌ها در ساختار ضمنی هستند یا نه, و تنها تعداد ثابتی از آن‌ها پیدا خواهد کرد. <ref>
{{Cite journal|last=M. E. J. Newman|year=2004|title=Detecting community structure in networks|journal=Eur. Phys. J. B|volume=38|issue=2|pages=321–330|bibcode=2004EPJB...38..321N|doi=10.1140/epjb/e2004-00124-y|hdl-access=free}}
</ref>

=== خوشه بندی سلسله مراتبی ===
روش دیگری برای پیدا کردن ساختارهای جوامع در شبکه ها [[خوشه‌بندی سلسله‌مراتبی|دسته بندی سلسله مراتبی]] است. در این روش یک معیار شباهت برای کمی کردن برخی (معمولا توپولوژیکی) تشابه بین جفت‌های گره تعریف می‌شود. معیارهایی که معمولاً استفاده می شوند شامل شباهت کسینوس ([[:en:Cosine_similarity|cosine similarity]])، [[اندیس ژاکار|شاخص ژاکارد]] و [[فاصله همینگ]] بین ردیف های [[ماتریس مجاورت]] است. سپس یک گروه با توجه به این معیار، گره‌ها مشابه را به جوامع تبدیل می‌کند. چندین طرح مشترک برای گروه بندی کردن وجود دارد، دوتا از ساده ترین آن ها [[خوشه‌بندی تک‌پیوندی|دسته بندی تک پیوندی]] است که در آن دو گروه به عنوان اجتماع جداگانه در نظر گرفته شده و اگر و فقط اگر همه جفت گره های گروه های مختلف شباهت کمتری نسبت به یک مقدار مشخص داشته باشند، و [[خوشه‌بندی کامل پیوند|خوشه بندی پیوند کامل]]، که در آن همه ی گره های هر گروه شباهت بیشتری نسبت به یک مقدار مشخص دارند. گام مهم این است که چگونه آستانه را برای توقف خوشه‌بندی تجمعی مشخص کنیم، که نشان‌دهنده ساختار جامعه نزدیک به بهینه است. یک استراتژی مشترک شامل ایجاد یک یا چند معیار برای پایش ویژگی‌های جهانی شبکه است، که در یک گام از خوشه‌بندی به اوج می‌رسد. یکی از رویکردهای جالب در این راستا استفاده کردن از معیارهای مختلف و متنوع برای تعیین شباهت یا عدم تشابه است که از طریق مبالغ محدب([[:en:Convex_combination|convex sums]]) ترکیب می شوند. <ref>{{Cite journal|last=Alvarez|first=Alejandro J.|last2=Sanz-Rodríguez|first2=Carlos E.|last3=Cabrera|first3=Juan Luis|date=2015-12-13|title=Weighting dissimilarities to detect communities in networks|journal=Phil. Trans. R. Soc. A|volume=373|issue=2056|pages=20150108|bibcode=2015RSPTA.37350108A|doi=10.1098/rsta.2015.0108|issn=1364-503X|pmid=26527808|doi-access=free}}</ref> تقریب دیگر محاسبه مقدار کنترل کننده چگالی لبه های خوشه ها با توجه به چگالی بین خوشه ها است ، مانند چگالی پارتیشن ، که در صورت تعریف متریک شباهت بین لبه ها (که تعریف تعریف جوامع همپوشانی را ارائه می دهد) پیشنهاد شده است ، <ref>{{Cite journal|last=Ahn|first=Y.-Y.|last2=Bagrow|first2=J.P.|last3=Lehmann|first3=S.|date=2010|title=Link communities reveal multi-scale complexity in networks|journal=Nature|volume=466|issue=7307|pages=761-764|arxiv=0903.3178|doi=10.1038/nature09182}}</ref> و هنگامی که شباهت بین گره ها تعریف می شود ، گسترش می یابد ، که به شما امکان می دهد تعاریف دیگری از جوامع مانند اصناف (به عنوان مثال گروه های گره ای که تعداد پیوندهای مشابهی نسبت به همسایگان مشابه دارند اما لزوماً خود را به هم متصل نمی کنند) در نظر گرفته شود. <ref name="functionink_2020">{{Cite journal|last=Pascual-García|first=Alberto|last2=Bell|first2=Thomas|date=2020|title=functionInk: An efficient method to detect functional groups in multidimensional networks reveals the hidden structure of ecological communities|journal=Methods Ecol Evol|volume=11|issue=7|pages=804-817|doi=10.1111/2041-210X.13377}}</ref> این روش ها را می توان برای در نظر گرفتن شبکه های چند بعدی گسترش داد ، به عنوان مثال وقتی با شبکه هایی دارای گره با انواع مختلف پیوند سروکار داریم. <ref name="functionink_2020">{{Cite journal|title = functionInk: An efficient method to detect functional groups in multidimensional networks reveals the hidden structure of ecological communities|journal = Methods Ecol Evol|date = 2020|pages = 804-817|volume = 11|issue = 7|doi = 10.1111/2041-210X.13377|first1 = Alberto |last1 = Pascual-García|first2 = Thomas|last2 = Bell}}</ref>

=== الگوریتم Girvan – Newman ===
الگوریتم دیگری که معمولاً برای پیدا کردن جوامع استفاده می شود الگوریتم Girvan – Newman است. <ref name="ComSocBio">
{{Cite journal|last=M. Girvan|last2=M. E. J. Newman|year=2002|title=Community structure in social and biological networks|journal=Proc. Natl. Acad. Sci. USA|volume=99|issue=12|pages=7821–7826|arxiv=cond-mat/0112110|bibcode=2002PNAS...99.7821G|doi=10.1073/pnas.122653799|pmc=122977|pmid=12060727}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFM._GirvanM._E._J._Newman2002">[[میشل گیروان|M. Girvan]]; M. E. J. Newman (2002). [//www.ncbi.nlm.nih.gov/pmc/articles/PMC122977 "Community structure in social and biological networks"]. ''Proc. Natl. Acad. Sci. USA''. '''99''' (12): 7821–7826. [[آرکایو (بایگانی نوشتارهای علمی)|arXiv]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/cond-mat/0112110 cond-mat/0112110]</span>. [[بیبکد|Bibcode]]:[https://ui.adsabs.harvard.edu/abs/2002PNAS...99.7821G 2002PNAS...99.7821G]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1073/pnas.122653799|10.1073/pnas.122653799]]. [[پاب‌مد سنترال|PMC]]&nbsp;<span class="cs1-lock-free" title="Freely accessible">[//www.ncbi.nlm.nih.gov/pmc/articles/PMC122977 122977]</span>. [[پاب‌مد|PMID]]&nbsp;[//pubmed.ncbi.nlm.nih.gov/12060727 12060727].</cite></ref> این الگوریتم فقط با پشت سر گذاشتن خود جوامع و با شناسایی لبه های شبکه ای که بین جوامع قرار دارد آنها را حذف می کند. این شناسایی با استفاده از اندازه گیری نظریه گراف بین [[میانی مرکزی|مرکزیت]] انجام می شود که یک عدد به هر لبه اختصاص می دهد که اگر لبه "بین" بسیاری از جفت گره ها باشد، بزرگ است.

الگوریتم Girvan – Newman یک الگوریتم محبوب است به این دلیل که نتایج با کیفیتی را بدست آورده است. در تعدادی از بسته های نرم افزاری استاندارد پیاده سازی شده است. اما به آرامی اجرا شده و بر روی شبکه ای که از ''n'' راس و ''m'' لبه تشکیل شده باشد، زمان O ( ''m'' <sup>2</sup> ''n'' ) به طول می انجامد و این کار را برای شبکه های بیش از چند هزار گره غیر قابل انجام می کند. <ref name="fast">
{{Cite journal|last=M. E. J. Newman|year=2004|title=Fast algorithm for detecting community structure in networks|journal=Phys. Rev. E|volume=69|issue=6|pages=066133|arxiv=cond-mat/0309508|bibcode=2004PhRvE..69f6133N|doi=10.1103/PhysRevE.69.066133|pmid=15244693}}
</ref>

=== به حداکثر رساندن پیمانه ای بودن ===
علیرغم اشکالات شناخته شده، حداکثر سازی مدولار یکی از روش های پرکاربرد برای شناسایی جامعه است. <ref name="fast">
{{Cite journal|last=M. E. J. Newman|year=2004|title=Fast algorithm for detecting community structure in networks|journal=Phys. Rev. E|volume=69|issue=6|pages=066133|arxiv=cond-mat/0309508|bibcode=2004PhRvE..69f6133N|doi=10.1103/PhysRevE.69.066133|pmid=15244693}}<cite class="citation journal cs1" data-ve-ignore="true">M. E. J. Newman (2004). "Fast algorithm for detecting community structure in networks". ''Phys. Rev. E''. '''69''' (6): 066133. [[آرکایو (بایگانی نوشتارهای علمی)|arXiv]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/cond-mat/0309508 cond-mat/0309508]</span>. [[بیبکد|Bibcode]]:[https://ui.adsabs.harvard.edu/abs/2004PhRvE..69f6133N 2004PhRvE..69f6133N]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1103/PhysRevE.69.066133|10.1103/PhysRevE.69.066133]]. [[پاب‌مد|PMID]]&nbsp;[//pubmed.ncbi.nlm.nih.gov/15244693 15244693]. [[سمانتیک اسکالر|S2CID]]&nbsp;[https://api.semanticscholar.org/CorpusID:301750 301750].</cite>
</ref> پیمانه ای بودن عملکرد مفیدی است که کیفیت یک تقسیم خاص از یک شبکه را به جوامع اندازه‌گیری می‌کند. این روش با جستجو در بخش های احتمالی یک شبکه برای یک یا چند مورد که دارای مادولاریسیون خاصی هستند جوامع را تشخیص می دهد. از آنجا که جستجوی جامع و کامل در تمام بخشهای ممکن معمولاً غیر ممکن میباشد، الگوریتم‌های تجربی مبتنی بر روش‌های بهینه‌سازی تقریبی مانند الگوریتم‌های حریصانه، تبرید شبیه‌سازی شده، یا بهینه‌سازی طیفی، با رویکردهای مختلفی که تعادل بین سرعت و دقت مختلف را ارایه می‌دهند.. <ref>
{{Cite journal|last=L. Danon|last2=J. Duch|last3=A. Díaz-Guilera|last4=A. Arenas|year=2005|title=Comparing community structure identification|journal=J. Stat. Mech.|volume=2005|issue=9|pages=P09008|arxiv=cond-mat/0505245|bibcode=2005JSMTE..09..008D|doi=10.1088/1742-5468/2005/09/P09008}}
</ref> <ref>
{{Cite journal|last=R. Guimera|last2=L. A. N. Amaral|year=2005|title=Functional cartography of complex metabolic networks|journal=Nature|volume=433|issue=7028|pages=895–900|arxiv=q-bio/0502035|bibcode=2005Natur.433..895G|doi=10.1038/nature03288|pmc=2175124|pmid=15729348}}
</ref> یک رویکرد محبوب این روش، متد لوین است که با تکرار جوامع محلی را بهینه می‌کند تا زمانی که واحد پیمانه‌ای جهانی دیگر نمی‌تواند به طور همزمان با اختلالات موجود در وضعیت فعلی جامعه بهبود یابد. <ref>
{{Cite journal|last=V.D. Blondel|last2=J.-L. Guillaume|last3=R. Lambiotte|last4=E. Lefebvre|year=2008|title=Fast unfolding of community hierarchies in large networks|journal=J. Stat. Mech.|volume=2008|issue=10|pages=P10008|arxiv=0803.0476|bibcode=2008JSMTE..10..008B|doi=10.1088/1742-5468/2008/10/P10008}}
</ref> <ref>{{Cite journal|date=2013|title=Lightning-fast Community Detection in Social Media: A Scalable Implementation of the Louvain Algorithm}}</ref> الگوریتمی که از طرح RenEEL استفاده می کند و نمونه ای از الگوی یادگیری گروه فوق العاده (EEL) است، در حال حاضر بهترین الگوریتم حداکثر سازی مدولار است. <ref>
{{Cite journal|last=J. Guo|last2=P. Singh|last3=K.E. Bassler|year=2019|title=Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks|journal=Scientific Reports|volume=9|issue=14234|pages=14234|arxiv=1909.10491|bibcode=2019NatSR...914234G|doi=10.1038/s41598-019-50739-3|pmc=6775136|pmid=31578406|doi-access=free}}
</ref> <ref name="RenEEL-Modularity">{{Cite web|title=RenEEL-Modularity|date=31 October 2019|url=https://github.com/kbassler/RenEEL-Modularity}}
</ref>

فایده ی این روش سوال برانگیز است، زیرا نشان داده شده است که این روش اغلب بسته به اندازه شبکه، خوشه هایی را که کوچکتر از مقیاس هستند تشخیص نمی دهد ( حد تفکیک پذیری <ref>
{{Cite journal|last=S. Fortunato|last2=M. Barthelemy|year=2007|title=Resolution limit in community detection|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=104|issue=1|pages=36–41|arxiv=physics/0607100|bibcode=2007PNAS..104...36F|doi=10.1073/pnas.0605965104|pmc=1765466|pmid=17190818}}
</ref> ). از طرفی، چشم انداز مقادیر مدولاریته با انحطاط عظیم پارتیشن ها با مدولاریته بالا، نزدیک به حداکثر مطلق مشخص می شود ، که ممکن است بسیار متفاوت از یکدیگر باشد. <ref>
{{Cite journal|last=B. H. Good|last2=Y.-A. de Montjoye|last3=A. Clauset|year=2010|title=The performance of modularity maximization in practical contexts|journal=Phys. Rev. E|volume=81|issue=4|pages=046106|arxiv=0910.0165|bibcode=2010PhRvE..81d6106G|doi=10.1103/PhysRevE.81.046106|pmid=20481785}}
</ref>

=== استنباط آماری ===
روش های مبتنی بر [[استنباط آماری|استنتاج آماری]] سعی در تطبیق مدل تولیدی با داده های شبکه دارد که ساختار جامعه را رمزگذاری می کند. مزیت کلی این روش در مقایسه با گزینه های جایگزین این است که ماهیت اصولی تری دارد و به طور ذاتی توانایی رسیدگی به موضوعات [[معناداری آماری|مهم آماری]] را دارد. بیشتر روش ها در ادبیات بر اساس [[مدل بلوکی تصادفی|مدل بلوک تصادفی]] ([[:en:Stochastic_block_model|stochastic block model]]) <ref>
{{Cite journal|last=Holland|first=Paul W.|last2=Kathryn Blackmond Laskey|last3=Samuel Leinhardt|date=June 1983|title=Stochastic blockmodels: First steps|journal=Social Networks|volume=5|issue=2|pages=109–137|doi=10.1016/0378-8733(83)90021-7|issn=0378-8733}}
</ref> و همچنین انواع مختلفی از جمله عضویت مختلط، <ref>{{Cite journal|last=Airoldi|first=Edoardo M.|last2=David M. Blei|last3=Stephen E. Fienberg|last4=Eric P. Xing|date=June 2008|title=Mixed Membership Stochastic Blockmodels|url=http://dl.acm.org/citation.cfm?id=1390681.1442798|journal=J. Mach. Learn. Res.|volume=9|pages=1981–2014|issn=1532-4435|pmc=3119541|pmid=21701698|access-date=2013-10-09}}
</ref> <ref>
{{Cite journal|last=Ball|first=Brian|last2=Brian Karrer|last3=M. E. J. Newman|date=2011|title=Efficient and principled method for detecting communities in networks|journal=Physical Review E|volume=84|issue=3|pages=036103|arxiv=1104.3590|bibcode=2011PhRvE..84c6103B|doi=10.1103/PhysRevE.84.036103|pmid=22060452}}
</ref> اصلاح درجه، <ref>
{{Cite journal|last=Karrer|first=Brian|last2=M. E. J. Newman|date=2011-01-21|title=Stochastic blockmodels and community structure in networks|journal=Physical Review E|volume=83|issue=1|pages=016107|arxiv=1008.3926|bibcode=2011PhRvE..83a6107K|doi=10.1103/PhysRevE.83.016107|pmid=21405744}}
</ref> و ساختارهای سلسله مراتبی است. <ref>
{{Cite journal|last=Peixoto|first=Tiago P.|date=2014-03-24|title=Hierarchical Block Structures and High-Resolution Model Selection in Large Networks|journal=Physical Review X|volume=4|issue=1|pages=011047|arxiv=1310.4377|bibcode=2014PhRvX...4a1047P|doi=10.1103/PhysRevX.4.011047}}</ref> انتخاب مدل می تواند با استفاده از رویکردهای اصولی مثل حداقل طول توصیف <ref>{{Cite journal|last=Martin Rosvall|last2=Carl T. Bergstrom|year=2007|title=An information-theoretic framework for resolving community structure in complex networks|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=104|issue=18|pages=7327–7331|arxiv=physics/0612035|bibcode=2007PNAS..104.7327R|doi=10.1073/pnas.0611034104|pmc=1855072|pmid=17452639}}</ref> <ref>{{Cite journal|last=P. Peixoto|first=T.|date=2013|title=Parsimonious Module Inference in Large Networks|journal=Phys. Rev. Lett.|volume=110|issue=14|page=148701|arxiv=1212.4794|bibcode=2013PhRvL.110n8701P|doi=10.1103/PhysRevLett.110.148701|pmid=25167049}}</ref> (یا معادلا، [[عامل بیز|انتخاب مدل بیزی]] ) و [[آزمون نسبت درست‌نمایی|آزمون نسبت احتمال]] انجام شود. <ref>
{{Cite journal|last=Yan|first=Xiaoran|last2=Jacob E. Jensen|last3=Florent Krzakala|last4=Cristopher Moore|last5=Cosma Rohilla Shalizi|last6=Lenka Zdeborová|author-link6=Lenka Zdeborová|last7=Pan Zhang|last8=Yaojia Zhu|date=2012-07-17|title=Model Selection for Degree-corrected Block Models|journal=Journal of Statistical Mechanics: Theory and Experiment|volume=2014|issue=5|page=P05007|arxiv=1207.3994|bibcode=2014JSMTE..05..007Y|doi=10.1088/1742-5468/2014/05/P05007|pmc=4498413|pmid=26167197}}</ref> در حال حاضر الگوریتم های زیادی برای انجام استنباطی کارآمد از مدل های بلوک تصادفی وجود داشته و از جمله ی آنها میتوان به [[انتشار باور]] <ref>
{{Cite journal|last=Gopalan|first=Prem K.|last2=David M. Blei|date=2013-09-03|title=Efficient discovery of overlapping communities in massive networks|journal=Proceedings of the National Academy of Sciences|volume=110|issue=36|pages=14534–14539|bibcode=2013PNAS..11014534G|doi=10.1073/pnas.1221839110|issn=0027-8424|pmc=3767539|pmid=23950224}}</ref> <ref>
{{Cite journal|last=Decelle|first=Aurelien|last2=Florent Krzakala|last3=Cristopher Moore|last4=Lenka Zdeborová|author-link4=Lenka Zdeborová|date=2011-12-12|title=Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications|journal=Physical Review E|volume=84|issue=6|pages=066106|arxiv=1109.3041|bibcode=2011PhRvE..84f6106D|doi=10.1103/PhysRevE.84.066106|pmid=22304154}}
</ref> و [[روش مونت‌کارلو|مونت کارلو تجمعی]] اشاره کرد. <ref>{{Cite journal|last=Peixoto|first=Tiago P.|date=2014-01-13|title=Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models|journal=Physical Review E|volume=89|issue=1|pages=012804|arxiv=1310.4378|bibcode=2014PhRvE..89a2804P|doi=10.1103/PhysRevE.89.012804|pmid=24580278}}
</ref>

برخلاف رویکردهایی که تلاش در دسته بندی کردن یک شبکه با عملکردی عینی دارند، اینگونه روش ها بر اساس مدل های مولد ساخته شده اند که نه تنها به عنوان توصیف کننده ی ساختار شبکه در مقیاس بزرگ عمل می کنند بلکه می توانند برای ''تعمیم'' داده ها و پیش بینی وقوع پیوندهای گمشده یا جعلی در شبکه استفاده شوند. <ref>{{Cite journal|last=Guimerà|first=Roger|last2=Marta Sales-Pardo|date=2009-12-29|title=Missing and spurious interactions and the reconstruction of complex networks|journal=Proceedings of the National Academy of Sciences|volume=106|issue=52|pages=22073–22078|arxiv=1004.4791|bibcode=2009PNAS..10622073G|doi=10.1073/pnas.0908366106|pmc=2799723|pmid=20018705}}</ref> <ref>
{{Cite journal|last=Clauset|first=Aaron|last2=Cristopher Moore|last3=M. E. J. Newman|date=2008-05-01|title=Hierarchical structure and the prediction of missing links in networks|journal=Nature|volume=453|issue=7191|pages=98–101|arxiv=0811.0484|bibcode=2008Natur.453...98C|doi=10.1038/nature06830|issn=0028-0836|pmid=18451861}}
</ref>

=== روش های مبتنی بر کلیک ===
[[گروهک (نظریه گراف)|کلیک ها]] زیرگراف هایی هستند که در آنها هر گره به تمام گره های دیگر در دسته متصل است. از آنجایی که گره ها نمی توانند اتصالی محکم تر از این داشته باشند،تعجبی ندارد که رویکردهای زیادی برای شناسایی جامعه در شبکه ها براساس شناسایی کلیک ها در گراف و تحلیل چگونگی این همپوشانی ها وجود دارد. توجه کنید که یک گره می تواند عضو بیش از یک کلیک باشد و در این روش ها یک گره می تواند عضو بیش از یک جامعه باشد که " ''ساختار جامعه را با هم تداخل می دهد'' ".

یکی از رویکردها، یافتن " ''حداکثر دسته'' " است. به این معنی که دسته هایی را پیدا کنید که زیر مجموعه هیچ دسته دیگری نیستند. یک الگوریتم کلاسیک برای یافتن این موارد الگوریتم Bron – Kerbosch است. هم پوشانی این ها را می‌توان برای تعریف جوامع به چندین روش مورد استفاده قرار داد. ساده ترین راه این است که حداکثر کلیک های بزرگتر از حداقل اندازه (تعداد گره ها) را در نظر بگیریم. اجتماع این دسته ها یک زیرگراف را تشکیل می دهد که اجزای آن (اجزای جدا شده) جوامع را مشخض می کنند. <ref name="Everett1998">
{{Cite journal|last=M.G. Everett|last2=S.P. Borgatti|year=1998|title=Analyzing Clique Overlap Connections|journal=Connections|volume=21|pages=49}}
</ref> رویکردهایی از این قبیل معمولا در نرم افزار تجزیه و تحلیل شبکه های اجتماعی مانند UCInet پیاده سازی می شوند.

روش جایگزین استفاده از دسته هایی با اندازه ثابت است <math>k</math> . از همپوشانی این موارد می توان برای تعریف نوعی استفاده کرد <math>k</math> به طور منظم [[ابرگراف|hypergraph]] یا یک ساختار که یک تعمیم از [[گراف خط|نمودار خط]] (مورد زمانی که <math>k=2</math> ) معروف به " ''نمودار کلیك'' ". <ref name="Evans2010">{{Cite journal|last=T.S. Evans|year=2010|title=Clique Graphs and Overlapping Communities|journal=J. Stat. Mech.|volume=2010|issue=12|pages=P12037|arxiv=1009.0638|bibcode=2010JSMTE..12..037E|doi=10.1088/1742-5468/2010/12/P12037}}
</ref> نمودارهای کلیس دارای رئوس هستند که نمای کلی ها را در نمودار اصلی نشان می دهند در حالی که لبه های نمودار دسته همپوشانی کلیک را در نمودار اصلی ثبت می کنند. با استفاده از هر یک از روش های تشخیص جامعه قبلی (که هر گره را به یک انجمن اختصاص می دهد) به نمودار کلیک ، سپس هر کلیک را به یک انجمن اختصاص می دهد. سپس می توان برای تعیین عضویت در جامعه در گره های موجود در کلیک ها استفاده کرد. دوباره به عنوان گره ممکن است در چند کلیک باشد ، می تواند عضو چندین انجمن باشد. به عنوان مثال روش نفوذ کلیک <ref>
{{Cite journal|last=G. Palla|last2=I. Derényi|last3=I. Farkas|last4=T. Vicsek|year=2005|title=Uncovering the overlapping community structure of complex networks in nature and society|journal=Nature|volume=435|issue=7043|pages=814–818|arxiv=physics/0506133|bibcode=2005Natur.435..814P|doi=10.1038/nature03607|pmid=15944704}}
</ref> جوامع را به عنوان [[نظریه تراوش|خوشه های تراوش در تعریف می کند]] [[گروهک|<math>k</math> -کلیک]] برای انجام این کار همه چیز را پیدا می کند <math>k</math> -کلیک های موجود در یک شبکه ، یعنی تمام زیر نمودارهای کامل <math>k</math> گره ها سپس دو تعریف می کند <math>k</math> در صورت اشتراك بودن ، كلیكها مجاور خواهند بود <math>k-1</math> گره ها ، این برای تعریف لبه ها در نمودار کلیک استفاده می شود. سپس یک جامعه به عنوان حداکثر اتحادیه تعریف می شود <math>k</math> - کلیساهایی که در آن می توانیم به هر مکانی برسیم <math>k</math> - از هر کس دیگری استفاده کنید <math>k</math> - از طریق مجموعه ای از <math>k</math> مجاورت کلیک یعنی جوامع فقط اجزای متصل شده در نمودار دسته هستند. از آنجا که یک گره می تواند به چندین مورد مختلف تعلق داشته باشد <math>k</math> خوشه های لایه برداری به طور همزمان ، جوامع می توانند با یکدیگر همپوشانی داشته باشند.

== روش های آزمایش الگوریتم های جوامع ==
ارزیابی الگوریتم ها ، برای تشخیص که در تشخیص ساختار جامعه بهتر هستند ، هنوز یک سوال باز است. این باید بر اساس تجزیه و تحلیل شبکه های ساختار شناخته شده باشد. یک نمونه معمول ، آزمون "چهار گروه" است که در آن شبکه ای به چهار گروه با اندازه یکسان تقسیم می شود (معمولاً هر کدام از آنها 32 گره است) و احتمال اتصال در داخل و بین گروه ها متفاوت است تا ساختارهای کم و بیش چالش برانگیزی برای تشخیص الگوریتم این نمودارهای معیار مورد خاصی از مدل پارتیشن L <ref name="PlantedPartitionModel">
{{Cite journal|last=Condon|first=A.|last2=Karp|first2=R. M.|author-link2=Richard Karp|year=2001|title=Algorithms for graph partitioning on the planted partition model|journal=Random Struct. Algor.|volume=18|issue=2|pages=116–140|citeseerx=10.1.1.22.4340|doi=10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2}}
</ref> Condon و [[ریچارد ام. کارپ|Karp]] یا به طور کلی " [[مدل بلوکی تصادفی|مدل های بلوک تصادفی]] " است ، یک کلاس کلی از مدل های شبکه تصادفی حاوی ساختار جامعه. معیارهای انعطاف پذیر دیگری نیز ارائه شده است که امکان تغییر اندازه گروه و توزیع درجه غیرپیشرفته را فراهم می کند ، مانند معیار LFR <ref name="LFR">
{{Cite journal|last=A. Lancichinetti|last2=S. Fortunato|last3=F. Radicchi|year=2008|title=Benchmark graphs for testing community detection algorithms|journal=Phys. Rev. E|volume=78|issue=4|pages=046110|arxiv=0805.4770|bibcode=2008PhRvE..78d6110L|doi=10.1103/PhysRevE.78.046110|pmid=18999496}}
</ref> <ref name="fat19">{{Cite arXiv|last1=Fathi|first1=Reza|title=Efficient Distributed Community Detection in the Stochastic Block Model|arxiv=1904.07494}}</ref> که گسترش معیار چهار گروه است که شامل توزیع های ناهمگن درجه گره و اندازه جامعه است و باعث می شود یک آزمایش شدیدتر از روش های تشخیص جامعه. <ref name="QF">
{{Cite arXiv|year=2017|title=Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures|arxiv=1606.01169}}
</ref> <ref>{{Cite journal|last=Pasta|first=M. Q.|last2=Zaidi|first2=F.|date=2017|title=Topology of Complex Networks and Performance Limitations of Community Detection Algorithms|journal=IEEE Access|volume=5|pages=10901–10914|doi=10.1109/ACCESS.2017.2714018|doi-access=free}}</ref>

معیارهای رایج تولید شده رایانه ای با شبکه ای از جوامع کاملاً مشخص شروع می شوند. سپس ، این ساختار با سیم کشی یا حذف پیوندها تخریب می شود و تشخیص پارتیشن اصلی برای الگوریتم ها دشوارتر می شود. در پایان ، شبکه به نقطه ای می رسد که اساساً تصادفی است. این نوع معیار را می توان "باز" نامید. عملکرد این معیارها با معیارهایی مانند [[اطلاعات متقابل]] عادی یا تغییر اطلاعات ارزیابی می شود . آنها راه حل بدست آمده توسط یک الگوریتم <ref name="fat19">{{Cite arXiv|last=Fathi|first=Reza|title=Efficient Distributed Community Detection in the Stochastic Block Model|eprint=1904.07494|date=April 2019|class=cs.DC}}<cite class="citation arxiv cs1" data-ve-ignore="true" id="CITEREFFathi2019">Fathi, Reza (April 2019). "Efficient Distributed Community Detection in the Stochastic Block Model". [[آرکایو (بایگانی نوشتارهای علمی)|arXiv]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/1904.07494 1904.07494]</span> [[//arxiv.org/archive/cs.DC cs.DC]].</cite></ref> با ساختار اصلی جامعه مقایسه می کنند و شباهت هر دو پارتیشن را ارزیابی می کنند.

== قابل تشخیص بودن ==
دز سال های اخیر، نتایج نسبتاً شگفت انگیزی توسط گروه های مختلف به دست آمده است که نشان دهنده ی وجود یک مرحله انتقال در مسئله شناسایی جامعه است، این نتایج نشان می دهند که هرچه تراکم اتصالات درون جوامع و بین جوامع بیشتر می شود یا هر دو کوچکتر می شوند (به طور یکسان، با ضعف بیش از حد ساختار جامعه یا شبکه بسیار پراکنده)، ناگهان جوامع غیرقابل شناسایی می شوند. یعنی جوامع هنوز وجود دارند، زیرا وجود و عدم وجود لبه ها همچنان با عضویت جامعه در نقاط انتهایی آنها ارتباط دارد. اما نام گذاری و برچسب زدن گره ها بهتر از شانس، یا حتی تشخیص نمودار از نمودار تولید شده توسط یک مدل پوچ مانند مدل [[مدل اردیش-رنیی|Erdos – Renyi]] بدون ساختار جامعه ، از نظر تئوری غیرممکن است. این انتقال مستقل از نوع الگوریتمی است که برای شناسایی جوامع استفاده می شود ، و این بدان معناست که محدودیت اساسی در توانایی ما برای شناسایی جوامع در شبکه ها ، حتی با استنباط بهینه بیزی (یعنی بدون در نظر گرفتن منابع محاسباتی ما) وجود دارد. <ref name="reichardt">
{{Cite journal|last=Reichardt|first=J.|last2=Leone|first2=M.|year=2008|title=(Un)detectable Cluster Structure in Sparse Networks|journal=Phys. Rev. Lett.|volume=101|issue=78701|pages=1–4|arxiv=0711.1452|bibcode=2008PhRvL.101g8701R|doi=10.1103/PhysRevLett.101.078701|pmid=18764586}}
</ref> <ref name="Decelle">
{{Cite journal|last=Decelle|first=A.|last2=Krzakala|first2=F.|last3=Moore|first3=C.|last4=Zdeborová|first4=L.|author-link4=Lenka Zdeborová|year=2011|title=Inference and Phase Transitions in the Detection of Modules in Sparse Networks|journal=Phys. Rev. Lett.|volume=107|issue=65701|pages=1–5|arxiv=1102.1182|bibcode=2011PhRvL.107f5701D|doi=10.1103/PhysRevLett.107.065701|pmid=21902340}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFDecelleKrzakalaMooreZdeborová2011">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]]:<span class="cs1-lock-free" title="Freely accessible">[//arxiv.org/abs/1102.1182 1102.1182]</span>. [[بیبکد|Bibcode]]:[https://ui.adsabs.harvard.edu/abs/2011PhRvL.107f5701D 2011PhRvL.107f5701D]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1103/PhysRevLett.107.065701|10.1103/PhysRevLett.107.065701]]. [[پاب‌مد|PMID]]&nbsp;[//pubmed.ncbi.nlm.nih.gov/21902340 21902340]. [[سمانتیک اسکالر|S2CID]]&nbsp;[https://api.semanticscholar.org/CorpusID:18399723 18399723].</cite>
</ref> <ref name="rajrao">
{{Cite journal|last=Nadakuditi|first=R.R|last2=Newman|first2=M.E.J.|author-link2=Mark Newman|year=2012|title=Graph Spectra and the Detectability of Community Structure in Networks|journal=Phys. Rev. Lett.|volume=108|issue=188701|pages=1–5|arxiv=1205.1813|bibcode=2012PhRvL.108r8701N|doi=10.1103/PhysRevLett.108.188701|pmid=22681123}}
</ref>

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

: <math>p_\text{in}=c_\text{in}/n</math> و <math>p_\text{out}=c_\text{out}/n</math>

سپس تشخیص جوامع غیرممکن می شود: <ref name="Decelle">
{{Cite journal|last=Decelle|first=A.|last2=Krzakala|first2=F.|last3=Moore|first3=C.|last4=Zdeborová|first4=L.|author-link4=Lenka Zdeborová|year=2011|title=Inference and Phase Transitions in the Detection of Modules in Sparse Networks|journal=Phys. Rev. Lett.|volume=107|issue=65701|pages=1–5|arxiv=1102.1182|bibcode=2011PhRvL.107f5701D|doi=10.1103/PhysRevLett.107.065701|pmid=21902340}}
</ref>

: <math>c_\text{in}-c_\text{out}=\sqrt{2(c_\text{in}+c_\text{out})}</math>

== انعطاف پذیری شبکه های مدولار ==
انعطاف پذیری شبکه های پیمانه ای به دلیل خرابی گره یا لینک معمولاً با استفاده از تئوری نفوذ (percolation theory) مطالعه می شود. ساختار شبکه هنگام حمله به گره های داخلی (به عنوان مثال گره هایی که جوامع را به یکدیگر متصل می کنند) مورد مطالعه قرار گرفته است. <ref>
{{Cite journal|last=Shai|first=S.|last2=Kenett|first2=D.Y.|last3=Kenett|first3=Y.N.|last4=Faust|first4=M.|last5=Dobson|first5=S.|last6=Havlin|first6=S.|year=2015|title=Critical tipping point distinguishing two types of transitions in modular network structures|journal=Phys. Rev. E|volume=92|issue=6|pages=062805|bibcode=2015PhRvE..92f2805S|doi=10.1103/PhysRevE.92.062805|pmid=26764742|doi-access=free}}
</ref> همچنین، اخیرا مطالعه ای به مطالعه ی چگونگی تقویت ارتباطات بین جامعه برای مقاومت در برابر جوامع پرداخته است. <ref>
{{Cite journal|last=Dong|first=Gaogao|last2=Fan|first2=Jingfang|last3=Shekhtman|first3=Louis M|last4=Shai|first4=Saray|last5=Du|first5=Ruijin|last6=Tian|first6=Lixin|last7=Chen|first7=Xiaosong|last8=Stanley|first8=H Eugene|last9=Havlin|first9=Shlomo|year=2018|title=Resilience of networks with community structure behaves as if under an external field|journal=Proceedings of the National Academy of Sciences|volume=115|issue=27|pages=6911–6915|arxiv=1805.01032|bibcode=2018PNAS..115.6911D|doi=10.1073/pnas.1801588115|pmc=6142202|pmid=29925594}}
</ref>

== اپیدمی ها در شبکه های مدولار ==
مطالعه مدل های اپیدمی در شبکه های پیمانه ای توسط والدز و همکاران انجام شده است. <ref>{{Cite journal|last=LD Valdez, LA Braunstein, S Havlin|date=2020|title=Epidemic spreading on modular networks: The fear to declare a pandemic|journal=Physical Review E|volume=101|issue=3}}</ref> این نویسندگان همچنین معیار اعلام بیماری همه‌گیر را مورد مطالعه قرار دادند.

== شبکه های مدولار فضایی ==
[[File:The_spatial_modular_model.png|چپ|بندانگشتی| تصویرگری از مدل. مدل مدولار فضایی نشان دهنده ساختاری از شبکه کانالهای آلودگی در داخل شهرها (ماژول ها) و بین شهرها است. در داخل یک شهر ، کانالهای آلودگی متراکم هستند و بصورت تصادفی بین مناطق مختلف شهر پخش می شوند (پیوندهای سبز) مانند شبکه Erdős – Rénii که دارای ساختاری کاملاً تصادفی است در حالیکه کانالهای آلودگی از یک شهر به شهر دیگر معمولاً بین شهرهای همسایه امکان پذیر است (قرمز پیوندها) دارای ساختار مکانی مانند]]
مدلی برای شبکه های مدولار فضایی توسط Gross و همکاران ایجاد شده است. <ref>{{Cite journal|last=Bnaya Gross, Dana Vaknin, Sergey Buldyrev, Shlomo Havlin|date=2020|title=Two transitions in spatial modular networks|journal=New Journal of Physics|volume=22|issue=5|pages=053002|doi=10.1088/1367-2630/ab8263|doi-access=free}}</ref> این مدل به عنوان مثال ، زیرساخت ها را در کشوری توصیف می کند که در آن جوامع (ماژول ها) شهرهای دارای اتصالات زیادی را در فضای دو بعدی نشان می دهند. پیوندهای بین جوامع (شهرها) کمتر و معمولاً با نزدیکترین همسایگان است (شکل 2 را ببینید). شیوع اپیدمی در چنین شبکه هایی در گروس و هاولین بررسی شده است. <ref>{{Cite journal|last=Gross|first=B.|last2=Havlin|first2=S.|date=2020|title=Epidemic spreading and control strategies in spatial modular network|journal=Applied Network Science|volume=5|pages=1-14}}</ref>

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

* [[شبکه پیچیده]]
* [[سلسله‌مراتب|سلسله مراتب]]
* [[نظریه شبکه]]
* [[نظریه تراوش]] 

* [http://digitalinterface.blogspot.it/2013/05/community-detection-in-graphs.html شناسایی جامعه در نمودارها] - مقدمه
* [https://stackoverflow.com/questions/5822265/are-there-implementations-of-algorithms-for-community-detection-in-graphs آیا پیاده سازی الگوریتم هایی برای تشخیص جامعه در نمودارها وجود دارد؟] - [[استک اورفلو|پشته سرریز]]
* [https://stackoverflow.com/questions/9471906/what-are-the-differences-between-community-detection-algorithms-in-igraph/ تفاوت های الگوریتم های تشخیص جامعه در igraph چیست؟] - [[استک اورفلو|پشته سرریز]]
[[رده:شبکه‌ها]]
[[رده:شبکه‌ها]]

نسخهٔ ‏۲۶ آوریل ۲۰۲۱، ساعت ۱۶:۵۰

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

خواص

شکل 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 2 n ) به طول می انجامد و این کار را برای شبکه های بیش از چند هزار گره غیر قابل انجام می کند. [۱۴]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

و

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

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

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

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

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

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

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

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

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

  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.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. S2CID 138996. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Nemaneigen» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
  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. {{cite journal}}: Cite journal requires |journal= (help)
  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.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. S2CID 18399723. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Decelle» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
  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).{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  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.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  51. ↑ Gross, B.; Havlin, S. (2020). "Epidemic spreading and control strategies in spatial modular network". Applied Network Science. 5: 1–14.
برگرفته از «https://fa.wikipedia.org/w/index.php?title=ساختار_جامعه&oldid=31906784»