22032

22032

ارائه روشي نوين براي تشخيص جوامع در شبكه‌هاي اجتماعي پويا بر مبناي تغييرات شبكه و اطلاعات موجود از جوامع پيشين

كارشناسي ارشد

نرم افزار

1395

1398/2/28

دكتر حسن نادري

كامپيوتر

در سال¬هاي اخير، تحقيق در حوزه شبكه¬هاي اجتماعي پويا توجه زيادي را به خود جلب كرده¬است. يكي از مسائل مورد توجه پژوهش¬گران اين حوزه، تشخيص جوامع است كه به شناخت شبكه و افراد عضو شبكه كمك زيادي مي¬كند. از آن¬جايي كه شبكه¬هاي پويا مدام در حال تغيير و تحول¬اند يكي از چالش-هاي موجود، تشخيص جوامع در زمان كم و كيفيت بالاست. براي دستيابي به سرعت بالا نياز است كه جوامع را به صورت افزايشي و با توجه به تغييرات صورت گرفته در هرگام زماني تشخيص داد، زيرا روش هاي هرچند سريع ايستا به دليل تشخيص دوباره جوامعي كه تغيير نكردند موجب بالارفتن زمان اجرا مي¬شوند و اين موضوع به خصوص در شبكه هاي اجتماعي بزرگ به هيچ وجه قابل قبول نيست. اين پژوهش از دو بخش ايستا و پويا تشكيل شده¬است. در بخش ايستا، در اولين گام زماني، يك الگوريتم ايستا به صورت بازگشتي، با هدف يافتن همه جوامع با اندازه مطلوب، اجرا مي¬شود. سپس از اين جوامع، گره¬هاي با اهميت با استفاده از يك معيار كه تركيبي از سه معيار مركزيت درجه، مركزيت بينابيني و درجه گره است، استخراج مي¬شوند. در بخش پويا، گره¬هاي با‌اهميت گام¬زماني پيشين مورد بررسي قرار مي¬گيرند، اگر حذف نشده باشند و نيز هنوز با‌اهميت باشند، آن¬گاه حول اين گره‌هاي مهم جوامع را تشكيل مي¬دهيم. سپس جوامع به دست آمده را از شبكه حذف مي¬كنيم و برروي قسمت باقي¬مانده از گراف از روش ايستا استفاده شده براي تشخيص جوامع اوليه، براي به دست آوردن جوامع استفاده مي¬كنيم. در نهايت از اين جوامع، گره¬هاي مهم را براي استفاده در گام¬زماني بعدي استخراج مي¬كنيم. نتايج حاصل از اين رويكرد برروي چند مجموعه¬داده، نمايان¬گر كاهش زمان¬اجرا و نيز تشخيص درصد بالايي از جوامع با اندازه مطلوب است. رويكرد پيشنهادي ما همچنين توانسته¬است پيمانگي قابل قبولي را به دست بياورد.

1399/03/05

New method for community detection in dynamic social networks based on network changes and existing information from previous communities

5/17/2020 12:00:00 AM

In recent years, research in the field of dynamic social networking has attracted much attention. One of the issues of interest to researchers in this area is community detection which helps to identify networks and their members. Since dynamic networks are constantly evolving, one of the challenges is to identify communities in a timely and high-quality manner. In order to achieve high speed, it is necessary to recognize communities in an incremental manner, taking into account the changes made in each temporal step. That is because static methods, although being fast, increase the running time due to re-identification of communities which have not changed and this is by no means acceptable in large social networks. This research includes two sections: static and dynamic. In the static section, in the first step, a static algorithm is performed recursively, with the goal of finding all initial desirable communities. Then, from these communities, seed nodes are extracted using a measure which is computed collectively from three other measures: the degree of centrality, betweenness centrality, and the node degree. In the dynamic section, the extracted seed nodes from the previous section are examined. If those seed nodes are not deleted and they still keep their importance, then we will form communities around them. Then we remove the obtained communities from the network and use the static method, which was used to identify the initial communities, to obtain communities using the remainder of the graph. Finally, we extract the seed nodes from these communities to use in the next step. The results of this approach on several datasets show a reduction in the running time, as well as recognizing a high percentage of the communities with the desired size. Our proposed approach has also been able to achieve acceptable modularity.

شبكه اجتماعي پويا , تشخيص جامعه , گره با‌اهميت , جوامع مطلوب , زمان اجرا

dynamic social network , community detection , seed node , desirable community , running time