الگوریتم‌های تشخیص جامعه

منتشر‌شده در: towardsdatascience به تاریخ 29 ژانویه 2021
لینک منبع: Community Detection Algorithms

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

پژوهشگران، M. Girvan و M. E. J. Newman دو محقق مشهور در حوزه تشخیص جامعه هستند. آن‌ها در یکی از تحقیقات خود، ساختار جامعه-دارایی را با استفاده از شبکه‌های اجتماعی و شبکه‌های بیولوژیکی برجسته کرده‌اند. با توجه به آن‌ها، گره‌های شبکه به شدت به گروه‌های به‌هم‌پیوسته درون جوامع متصل هستند و به صورت آزادانه بین جوامع ارتباط دارند.

دلیل اهمیت تشخیص جامعه

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

ممکن است به مطالعه مقاله ۶ ابزار استخراج و جمع‌آوری داده‌ها از وب علاقه‌مند باشید.

تشخیص جامعه در مقابل خوشه‌بندی

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

روش‌های تشخیص جامعه

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

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

۱. تشخیص جامعه لون

الگوریتم تشخیص جامعه لون در اصل در سال ۲۰۰۸ به عنوان یک روش گسترش سریع جامعه برای شبکه‌های بزرگ پیشنهاد شد. این رویکرد مبتنی بر مدولار است که تلاش می‌کند تفاوت بین تعداد واقعی یال‌ها در یک جامعه و تعداد مورد انتظار از یال‌ها در جامعه را به حداکثر برساند.
با این حال بهینه‌سازی مدولار در یک شبکه NP-hard است، بنابراین باید از شیوه‌های اکتشافی استفاده کرد. الگوریتم لون به دو مرحله تکرار شونده تقسیم می‌شود.

1. حرکت محلی گره‌ها
2. جمع‌آوری شبکه

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

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

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

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.louvain(G, weight=’weight’, resolution=1., randomize=False)

۲. تشخیص جامعه غافلگیر کننده/ سورپرایز

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

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

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.surprise_communities(G)

۳. تشخیص جامعه لیدن

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

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

1. حرکت محلی گره‌ها
2. اصلاح پارتیشن‌ها
3. تجمع شبکه بر اساس پارتیشن‌های اصلاح‌شده

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

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

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.leiden(G)

۴. تشخیص جامعه Walktrap

الگوریتم Walktrap روش دیگری برای تشخیص جامعه براساس گام‌های تصادفی است که در آن فاصله بین رئوس از طریق گام‌های تصادفی در شبکه اندازه‌گیری می‌شود. آن یک الگوریتم کارآمد است که در پیچیدگی زمانی O (mn²) و پیچیدگی فضایی O (n²) در بدترین حالت اجرا می‌شود. اما در اکثر سناریوهای دنیای واقعی، Walktrap در پیچیدگی زمانی O ((n²) log n و پیچیدگی فضایی O (n²) اجرا می‌شود. شهود اصلی الگوریتم این است که قدم زدن تصادفی بر روی یک گراف / شبکه منجر به گرفتار شدن در بخش‌های با اتصالات متراکم مربوط به جوامع می‌شود. روش Walktrap از نتیجه گام‌های تصادفی برای ادغام جوامع جداگانه به روش پایین به بالا استفاده می‌کنند. کیفیت پارتیشن‌ها را می‌توان با استفاده از هر معیار کیفیت موجود ارزیابی کرد. آن می‌تواند یا مدولار، مانند تشخیص جامعه لون و یا هر اندازه‌گیری دیگری باشد.

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

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.walktrap(G)

نتیجه‌گیری

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

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

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