معرفي الگوريتم خلاصه‌سازي معناگراي SIGS براي گراف‌هاي عظيم‌الجثه

Introducing a Novel Algorithm SISG to Semantically Summarize Massive Graphs

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

Abstract Nowadays graphs are widely used in many domains such as software, network, web, chemistry, biology and even communication and sociology to modelling and data processing. In many applications, graphs are very large and complex. So understanding the structure and extracting useful information from them is become more challenging. Here, graph summarization algorithms could be a suitable solution. In this paper, a new graph summarization algorithm has been proposed which is able to produce different summaries from different points of view from one graph regarding to user’s interested subjects. Also users can control the resolution of produced summaries. Moreover, the algorithm is developed using Neo4j database which is one of NoSQL databases. Also, the algorithm using different laboratorial and real data sets is tested. The results show that the produced summaries are in high quality position and also the efficiency and scalability of the algorithm is better that the similar one. Keywords: Graph, Semantical Summarization, Summary Graph, Scalability, Efficiency.