tGraph_PheroWalk : یک الگوریتم جدید برای یادگیری بازنمایی گراف های پویا

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

کلیدواژه ها:

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