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

نویسندگان

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

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Introducing a Novel Algorithm SISG to Semantically Summarize Massive Graphs

نویسندگان [English]

  • Mohammad Mahdi Arsanjani
  • Mohammad Reza Kangavari
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Graph
  • Semantical Summarization
  • Summary Graph
  • Scalability
  • Efficiency