20263

۲۰۲۶۳

متقارن سازي گراف هاي جهت دار براي تشخيص جوامع توسط الگوريتم هاي بدون جهت

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

هوش مصنوعي و رباتيك

۹۷-۹۸

۱۳۹۷/۹/۱۴

دكتر مرتصي آنالويي

كامپيوتر

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

1397/11/29

Graph symmetrization for undirected community detection algorithms

2/18/2019 12:00:00 AM

Graph symmetrization methods seek to find symmetric graphs to provide the possibility of using a community detection algorithms in undirected graphs on a directed graph. it's a big challenge to obtain an undirected graph that maintains the information of the undirected graph and the quality of societies resulting from the application of community detection algorithms. Community recognition algorithms have been studied and investigated in non-directional graphs and have been developed to some extent. Our goal is to provide a method for converting a directed graph to an undirected graph, with the explanation that the focus of this study is on networks such as an co-citation network that provides text contents of the nodes. Our approach is to utilize the textual content of nodes and use probabilistic models to infer the similarity of the content of the nodes.