آقای نصرت‌علی اشرفی‌پیامن دانشجوی دکترای جناب آقای دکتر محمدرضا کنگاوری روز دوشنبه مورخ ۱۳۹۹/۰۳/۱۲ ساعت ۱۴:۰۰  از رساله دکتری خود تحت عنوان "طراحی و پیاده‌سازی یک روش مبتنی بر آنتولوژی برای خلاصه‌سازی جریان گرافی " دفاع خواهند نمود.

 

ارائه ­دهنده:
نصرت‌علی اشرفی‌پیامن
  استاد راهنما:
دکتر محمدرضا کنگاوری
  هیات داوران:

دکتر حمید بیگی، دکتر عباس نوذری دالینی، دکتر سعید پارسا، دکتر حسن نادری
زمان : دوشنبه  ۱۲ خرداد ماه ۱۳۹۹

  ساعت ۱۴:۰۰

  نحوه ی برگزاری: به صورت الکترونیک

چکیده پایان نامه :

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

Abstract:
Graph is used in a variety of applications for modeling data and their relationships. Social networks, communication networks, web graphs, biological networks and chemical compounds are examples of data modeled by graphs. These days, many applications generate large scale and massive graphs with billions of nodes and edges and many research works have been done on the theory and engineering of tera-scale graphs.
Graph summarization has been proposed as a solution for processing massive graphs. Graph summarization algorithms reduce a massive graph into a smaller one by removing its details but preserving its overall properties. Graph summarization can be based on the structure, vertex attributes or both.
There are a number of algorithms for structural summarization and we have proposed a new method for structural summarization that constructs a summary with a better quality.
Summarization a graph based on both the structure and the vertex attributes is challenging. Although generating an attribute-based summary is not a hard problem and there are a number of algorithms this purpose, but generating a hybrid summary with the user-specified contributions of the structure and vertex attributes is not easy and this is the main challenge of graph summarization. It is obvious that the importance of structure and vertex attributes in the resultant summary is not the same in all applications and therefore considering variable weighting factors for them is more reasonable.
In this dissertation, the aim has been proposing a new ontology-based method for summarizing an attributed graph stream. A new algorithm has been proposed for graph stream summarization based on sliding window paradigm. Of-course we have proposed new algorithms for structural summarization and hybrid summarization of stationery attributed graph. Our contributions are:

۱- Proposoing a new method for summarizing structural graph: In fact, we have improved the criterion of selecting the best super-node for division.
۲- Proposoing a new method for summarizing attributed graphs: we have proposed a new method for summarizing attributed graphs based on both the structure and vertex attributes.

۳- A new method has been proposed for summarizing an attributed graph stream.
 
Keywords: Graph Summarization, Graph Stream, Super-node, Attributed Graph, Ontology.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی