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

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

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

192631

دانشگاه علم و صنعت ايران

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

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