طراحي و پياده سازي يك روش مبتني بر آنتولوژي براي خلاصه سازي جريان گرافي

دكتري تخصصي

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

194523

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

نرم‌افزار

دكتر محمدرضا كنگاوري