22328

ارائه الگوريتم كشف اجتماعات همپوشان در شبكه¬هاي جهت-دار موزون؛ مورد مطالعه: شبكه همكاري رانندگان حمل و نقل (بارنامه)

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

سيستم هاي كلان اقتصادي و اجتماعي

1396-1399

1399/05/29

دكتر مهدي غضنفري

مهندسي پيشرفت

كشف اجتماع توجه زيادي را در دهه¬هاي گذشته به خود جلب كرده است. الگوريتم¬هاي زيادي براي حل اين مسئله توسعه داده شده¬اند. در بسياري از كارهاي مشابه قبلي وزن و جهت يال¬ها به صورت همزمان در مدل¬ها لحاظ نشده است و همين امر باعث مي¬شود تا مدل از دنياي واقع دور شود. در نظر گرفتن اوزان و جهت يال¬ها باعث واقعي¬تر شدن مدل از يكسو و باعث جلوگيري از هدر رفتن اطلاعات ارزشمند شبكه مي¬شود. در اين پايان نامه يك الگوريتم كشف اجتماعات همپوشان براي شبكه¬هاي موزون و جهت¬دار ارائه مي¬گردد. در اين پايان نامه از مفهوم جريان¬¬هاي اطلاعاتي در ميان گره¬ها استفاده مي¬شود؛ يعني هرچه جريان¬هاي اطلاعاتي موجود در يك جامعه قويي¬تر باشد، جامعه نيز مستحكم¬تر خواهد بود. مفهوم جريان اطلاعاتي با استفاده از حلقه¬هاي بسته موزون با شروع از يك گره و پايان به همان گره پياده¬سازي شده است. با بهره¬گيري از فرض فوق، يك معيار ماژولاريتي جديد به نام ماژولاريتي جريان موزون توسعه داده شد. سپس يك امتياز همپوشاني جديد توسعه داده شد كه همپوشاني در گره و يال¬ را به صورت همزمان در نظر مي¬گيرد كه از نظر زمان اجرا بسيار بهينه است. نتايج كشف اجتماع از لحاظ دقت و سرعت با الگوريتم OSLOM روي 74 شبكه آزمايشگاهي با پيچيدگي¬هاي مختلف تست شد و با استفاده از شاخص NMI مقايسه گرديد. همچنين روي شبكه¬هاي دنياي واقعي نيز عملكرد الگوريتم مورد بررسي قرار گرفت. در نهايت يك مورد مطالعه از شبكه¬هاي واقعي داخل كشور به نام شبكه همكاري رانندگان حمل و نقل نيز مورد بررسي قرار گرفت.

1399/06/03

Presenting a model for overlapping community detection in weighted directed social networks; case study: drivers’ collaboration network

8/24/2020 12:00:00 AM

Community detection has gained much attention in past few decades. So many algorithms have been developed to tackle this problem. In previous related works the weight of the edges and directionality were not considered at the same time in the models. Considering weights and directionality makes the models more realistic and prevents the loss of information in the network. In this article we propose an overlapping community detection algorithm for networks with weighted and directed edges. We used the concept of information flows among the vertices i.e. the more flows exist in a community, the stronger the community. We implemented the concept of flow using weighted closed flows starting from a given node and ending to the same node. By using the mentioned assumption, we developed a new modularity measure called weighted flow modularity (WFM) based on M function modularity. And then we developed an overlapping score criteria which considers overlap in vertices and edges at the same time and is much faster in the terms of run time. We compared the community detection results in terms of accuracy and running time with Order statistics local optimization method (OSLOM) on 74 LFR benchmark networks using normalized mutual information score. We also implemented the community detection process using LCFE on real world datasets and evaluated the community detection results using EQ measure. The experimental analysis results show that the LCFE is more accurate in most cases and is competitive in other cases with OSLOM.

تحليل شبكه هاي اجتماعي , كشف اجتماع

Social Netowrk Analysis , Community Detection