22165

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

دكتري تخصصي

نرم‌افزار

1399/3/12

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

كامپيوتر

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

1399/05/27

Design and implementation of an ontology-based method for graph stream summarization

6/2/2021 12:00:00 AM

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 structural, attributed-absed or based on both the structure and vertex attributes if the graph is an attributed graph. There are a number of algorithms for structural summarization and we have proposed a new method for structural summarizing 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 summary based on both the graph structure and vertex attributes (hybrid summarization) 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. Recently two algorithms have been proposed for hybrid summarization/clustering of a graph. In this dissertation, the aim has been proposing a new ontology-based method for summarizating 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: 1- Proposing a new method for summarizing structural graph: In fact, we have improved the criterion of selecting the best super-node for division. 2- Proposing 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. 3- A new method has been proposed for summarizing an attributed graph stream