Recently, graph mining approaches have become very popular, especially in certain domains such as bioinformatics, chemoinformatics and social networks. One of the most challenging tasks is frequent subgraph discovery. This task has been highly motivated by the tremendously increasing size of existing graph databases. Due to this fact, there is an urgent need of efficient and scaling approaches for frequent subgraph discovery. In this paper, we propose a novel approach to approximate large-scale subgraph mining by means of a density-based partitioning technique, using the MapReduce framework. Our partitioning aims to balance computational load on a collection of machines. We experimentally show that our approach decreases significantly the execution time and scales the subgraph discovery process to large graph databases

چکیده 
اخیراً، روش‌های گراف کاوی به ابزاری بسیار رایج مخصوصاً در دامنه‌هایی اعم از بیوانفورماتیک، فناوری شیمی انفورماتیک (شیمی داده‌ورزی) و شبکه‌های اجتماعی مبدل گردیده‌اند. یکی از وظایف چالش‌برانگیز که پیش روی این روش‌ها قرار داد، مسئله‌ی کشف زیر گراف می‌باشد. البته با افزایش اندازه‌ی پایگاه‌های داده‌ای گراف، کشف این زیر گراف‌ها به یک ضرورتی بسیار مهم مبدل می‌گردد. در همین راستا، نیاز به روش‌هایی کارآمد و روش‌های مقیاس بندی برای کشف زیر گراف های تکرار شونده احساس می‌شود. در این مقاله قصد داریم با بکار گیری یک تکنیک پارتیشن بندی مبتنی بر چگالی که از چارچوب MapReduce استفاده می‌کند، روش جدیدی را برای زیر گراف کاوی در مقیاس بزرگ ارائه دهیم. هدف از این پارتیشن بندی، ایجاد توازن در بین بار محاسباتی  (لود بالانسینگ) و جمع‌آوری ماشین‌ها می‌باشد. به شکلی تجربی نشان خواهیم داد که روش پیشنهادی ما می‌تواند زمان اجرا و مقیاس فرآیند کشف زیر گراف را به طور قابل ملاحظه‌ای برای پایگاه‌های داده‌ای بزرگ گراف کاهش دهد.

1-مقدمه

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