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

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

community detection in complex networks using learning automata

social networks are one of the types of complex networks. identifying communities in social networks is an effective way to use their information, for which several algorithms have been presented so far. in this paper, novel algorithms are designed, in which a learning automaton is attached to each node; the number of actions of learning automata is fixed and equal to the estimate of the number of network communities. at each step, each of the learning automata chooses an action from its set of actions. choosing any of these actions means assigning the label of that community to the node. the action chosen by each automaton is evaluated based on the chosen actions of its neighbors ((local attention) and/or communities detected by the entire method (global screening). the result of the evaluation leads to generate rewards or punish signal for the automata. by receiving a reward, the probability of re-choosing the chosen action by the automaton, or the community label, increases, and otherwise, by receiving a fine, the probability of this action decreases. by repeating the algorithm, the optimal action is determined as long as no change occurs in the selected label of the corresponding automata of each node with more iterations, and as a result, the optimal communities are determined as the output of the algorithm. the comparison of the results of the experiments shows the effectiveness of the proposed methods in comparison with the previous methods.