ارائه ی یک روش بهبود یافته مبتنی بر انتشار برچسب و رویکرد بهینه سازی ماژولاریتی برای تشخیص جوامع در شبکه های اجتماعی پویا
محورهای موضوعی : عمومی
محمد ستاری
1
,
کارمران زمانی فر
2
1 - مرکز تحقیقات فناوری اطلاعات در امور سلامت، دانشگاه علوم پزشکی اصفهان، اصفهان، ایران
2 - گروه مهندسی نرم¬افزار، دانشکده مهندسی کامپيوتر، دانشگاه اصفهان، اصفهان، ايران
کلید واژه: رتبه بندی برچسب مبتنی بر زمان حریصانه, رتبه بندی برچسب مبتنی بر زمان, رویکرد انتشار برچسب, تشخیص جوامع, شبکه ی اجتماعی پویا,
چکیده مقاله :
تشخیص جوامع در شبکههای اجتماعی پویا یکی از مهمترین موضوعات تحقیقاتی است که در سالیان اخیر مورد توجه قرار گرفته شده است. رویکردهای گوناگونی برای تشخیص جوامع در شبکههای اجتماعی در حالت پویا وجود دارد. از بین رویکردها، رویکرد انتشار برچسب به عنوان یک رویکرد ساده، کارا و تصادفی مطرح شده است. این رویکرد شامل روشهای بسیاری است که غالبا مبتنی بر حالت تصادفی این رویکرد هستند. از میان این روشها، روش رتبهبندی برچسب مبتنی بر زمان این رویکرد را از حالت تصادفی خارج کرده است و به آن قطعیت بخشیده است. البته مسلما این رویکرد هم با مشکلاتی مواجه است، یکی از مشکلات این است وقتی یک گره میخواهد به یک جامعه بپیوندد، ساختار درونی آن جامعه جهت پیوستن گره در نظر گرفته نمیشود. بنابراین برای حل این مشکل، یک رویکرد جدید به نام حریصانه به رویکرد انتشار برچسب اضافه شده است. رویکرد جدید ارائهشده به همراه روش رتبهبندی برچسب مبتنی بر زمان و نسخهی غیراشتراکی روش انتشار برچسب برجستهی گسترشیافته در مجموعههای دادهای مورد ارزیابی اعم از واقعی و ساختگی پیادهسازی شدهاند. نتایج نشان میدهد که روش پیشنهادی نسبت به دو روش دیگر از لحاظ میزان صحت براساس دو پارامتر ماژولاریتی و اطلاعات متقابل نرمال شده بهتر عمل کرده است.
Community detection in temporal social networks is one of the most important topics of research which attract many researchers around the world. There are variety of approaches in detecting communities in dynamic social network among which label propagation approach is simple and fast approach. This approach consists of many methods such as LabelRankT is one with high speed and less complexity. Similar to most methods for detecting communities in dynamic social networks, this one is not trouble free. That is, it is not considered the internal connection of communities, when it expands communities of the previous snapshots in the current snapshot. This drawback decreases the accuracy of community detection in dynamic social networks. For solving the drawback, a greedy approach based on local modularity optimization is added to LabelRankT method. Here, the newly proposed GreedyLabelRankT, LabelRankT and non-overlapping version of Dominant Label Propagation Algorithm Evolutionary (DLPAE-Non Overlapping) on real and synthetic datasets are implemented. Experimental results on both real and synthetic network show that the proposed method detect communities more accurately compared to the benchmark methods. Moreover, the finding here show that running time of the proposed method is close to LabelRankT. Therefore, the proposed method increase the accuracy of community detection in dynamic social networks with no noticeable change in the running time of that.