کاهش تنگنای گراف بر مبنای داده کاوی به وسیله ی بهبود تأثیر تست ایزومورفیزم بر برچسب های گراف

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

کلیدواژه ها:

داده کاوی ، روشهای کاوش والگوریتم تست ایزومورفیزم ، Graph signature ، درخت جستجوی فضای حالت