عنوان مقاله:

نویسندگان:

بهروز احدزاده، زینب شویدی، سید مهدی وحیدی پور

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

بازنمایی گراف، قدم زنی تصادفی، گراف زمانی، فرمون

برای لینک‌دهی به این مقاله از آدرس زیر استفاده نمایید:

برای ارجاع در منابع از عبارت زیر استفاده کنید:
احدزاده، بهروز، شویدی، زینب، مهدی وحیدی پور، سید، 1404، tdGraph_PheroWalk: یک الگوریتم جدید برای یادگیری بازنمایی گراف‌های پویا، بیست و یکمین کنفرانس ملی دانشجویی مهندسی برق ایران، https://conference.uok.ac.ir/fa/archive_index.php?c=HN-iscee21&aid=1517961