view in publisher's site

Mixed-case community detection problem in social networks: Algorithms and analysis

Highlights•A novel objective function of community detection problem is proposed.•The Greedy, Semi-Sandwich Approximation and Local Search algorithms are devised to solve the worst-case problem.•An efficient Terminal-based algorithm is proposed to solve the average-case problem.•An algorithm with the approximate guarantee is proposed for any mixed-case problem.•The experimental results indicate that our proposed methods can form a high-quality community partition.AbstractThe problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i.e., average-case) but also the sum of edge weights within the minimum community (i.e., worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition.

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

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


پر ارجاع‌ترین مقالات مرتبط:

  • مقاله Theoretical Computer Science
  • ترجمه مقاله Theoretical Computer Science
  • مقاله علوم کامپیوتر نظری
  • ترجمه مقاله علوم کامپیوتر نظری
  • مقاله General Computer Science
  • ترجمه مقاله General Computer Science
  • مقاله علوم کامپیوتر عمومی
  • ترجمه مقاله علوم کامپیوتر عمومی
سفارش ترجمه مقاله و کتاب - شروع کنید

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