الگوریتم مبتنی بر انتشار برچسب برای تشخیص تشکل های همپوشان در شبکه های پویا

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

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

الگوریتم

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

الگوریتم ۳ : الگوریتم پیشنهادی برای تشخیص تشکل های همپوشان در شبکه های پویا
فرایند اصلی الگوریتم پیشنهادی به صورت زیر است:

1. 1. ابتدا، در اولین برش زمانی از شبکه، از یکی از الگوریتم های تشخیص تشکل های همپوشان که به آنها اشاره شده (به عنوان مثال SLPA) استفاده کرده و تشکل های موجود را شناسایی می‌کنیم. سپس، تشکل های تعیین شده برای هر گره را به همراه برش زمانی آن در یک حافظه نگهداری می‌کنیم.

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

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

       

فصل چهارم

فصل چهارم: آزمایش ها و نتایج

مقدمه

به طور کلی، بررسی کارایی هر الگوریتم پیشنهادی برای تشخیص تشکل ها در شبکه ها، با توجه به این که در اکثر موارد، ساختار تشکل واقعی در دسترس نیست، کار دشواری است. در این فصل به ارائه نتایج حاصل از عملکرد الگوریتم های پیشنهادی بر روی مجموعه داده های آزمایشی می‌پردازیم و هر کدام از آنها را با روش پایه خود مقایسه می‌کنیم. برای این کار، از مجوعه داده های مصنوعی LFR استفاده کرده ایم. علت استفاده از این مجموعه داده، امکان تولید شبکه های مختلف در اندازه ها و ساختارهای متنوع، بررسی دقیق تر نتایج بر اساس معیار NMI، به دلیل دسترسی به تشکل های واقعی شبکه و معتبر بودن این مجموعه داده در مجامع علمی مطرح در این حوزه است. لازم به ذکر است که روش های پیشنهادی، با زبان C# و بر روی سیستمی با مشخصات پردازنده Intel® Core™ i7 CPU 1.73 GHzو حافظه ۴ GB RAM پیاده سازی و اجرا شده اند.

بهبود کارایی روش انتشار برچسب در شبکه های ایستا

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

پیاده سازی روش پایه

برای پیاده سازی الگوریتم پایه ما از روشی مبتنی بر الگوریتم SLPA استفاده کرده ایم. همانطور که در فصل قبل عنوان شد، SLPA یک الگوریتم تکراری است و شامل سه مرحله اصلی می‌باشد: مقداردهی اولیه، حلقه تکرار و پردازش نهایی. هر گره دارای حافظه ای است که برچسب هایی را که از سایر گره ها دریافت کرده است در آن نگهداری می‌کند. در هنگام شروع، حافظه تمام گره ها با برچسب خود آنها (شناسه هر گره) مقداردهی می‌شود. در مرحله تکرار، هر گره به صورت مداوم برچسبی را که در حافظه اش فراوانی بیشتری دارد انتشار می‌دهد و همچنین حافظه اش را بر اساس اطلاعاتی که از همسایه هایش دریافت کرده بروز رسانی می‌کند. پس از چندین تکرار، تشکل های هر گره با استخراج برچسب هایی که بیشترین فراوانی را در حافظه آن دارند تعیین می‌شود. در انتها نیز تشکل های لانه ای^[۹۸] حذف شده و تشکل های نهایی مشخص می‌گردند.
در پیاده سازی ما، حافظه هر گره با برچسب آن مقداردهی می‌شود. ترتیب گره ها به صورت تصادفی مشخص شده و هر گره برچسب جدیدی که بیشترین نرخ را در میان برچسب های پیشنهادی از همسایه هایش دارد به حافظه اش اضافه می‌کند. این فرایند برایبه تعداد T₁ بار برای تمام شبکه ادامه می‌یابد. در انتها نیز حافظه هر گره بررسی شده و برچسب هایی که احتمال حضور آنها از r₁ کمتر باشند از حافظه حذف می‌شوند. پس از حذف تشکل های لانه ای و اطمینان از پیوستگی تشکل های باقیمانده، آنها به عنوان نتایج نهایی ارائه می‌شوند.

پیاده سازی روش پیشنهادی

در پیاده سازی انجام شده، ابتدا به تعداد c مورد زیر شبکه با اندازه s از شبکه اصلی تهیه می‌شود. برای انتخاب هر زیر شبکه، ابتدا یک گره به صورت تصادفی انتخاب شده و سپس با بهره گرفتن از روش انتخاب اول- سطح^[۹۹]، گره های مجاور آن به زیر شبکه اضافه شده تا جایی که اندازه آن بیش از حداکثر اندازه تعیین شده نشود.
سپس برای هر زیر شبکه با بهره گرفتن از روش SLPA، تشکل ها تشخیص داده می‌شوند. به این صورت که ابتدا حافظه هر گره با برچسب خود آن مقداردهی شده و در یک فرایند تکراری، ابتدا ترتیب گره ها به صورت تصادفی مشخص شده و سپس برای هر گره، برچسب جدیدی که بیشترین پیشنهاد را از سوی همسایه های آن دارد به حافظه اضافه می‌شود. پس از T₂ بار تکرار، حافظه هر گره بررسی شده و برچسب هایی که احتمال حضور کمتر از r₂ دارند از آن حذف می‌شوند. برچسب های باقیمانده به عنوان مقادیر اولیه برای حافظه گره های انتخاب شده در تشخیص تشکل ها برای شبکه اصلی مورد استفاده قرار می‌گیرند.
پس از پایان تشخیص تشکل ها در تمام زیر شبکه ها، حافظه گره هایی که اطلاعات برای آنها استخراج شده است با برچسب های استخراج شده با وزن w و گره هایی که اطلاعاتی برای آنها در دسترس نیست با برچسب خودشان مقداردهی می‌شوند. سپس از روش پایه برای تشخیص تشکل ها استفاده می‌شود.

مجموعه داده ها

برای مقایسه عملکرد الگوریتم پایه و الگوریتم پیشنهادی، ما از مجموعه داده های LFR که در فصل دو اشاره شد و در این حوزه کاملا شناخته شده هستند استفاده کرده ایم. ابزار LFR این امکان را فراهم می‌آورد که بتوانیم شبکه هایی در اندازه ها، ساختارها و درجه های مختلف همپوشانی تولید کنیم. در آزمایش های انجام شده ما از شبکه هایی با ۵۰۰۰ گره استفاده کرده ایم. میانگین درجه گره برای این شبکه ها، ۱۰ در نظر گرفته شد که مقداری معمول در مقالات مختلف است. توزیع درجه شبکه ها و اندازه تشکل ها از توزیع قانون توانی^[۱۰۰] با توان های به ترتیب ۲ و ۱ پیروی می‌کنند. حداکثر درجه هر گره نیز ۵۰ در نظر گرفته شده است. اندازه تشکل ها نیز بین ۲۰ تا ۱۰۰ گره متغیر است. همچنین پارامتر ترکیبی نیز در دو حالت ۰.۱ و ۰.۳ مقداردهی شده است که میزان مورد انتظار تعداد یال هایی را که یک گره را به تشکل های دیگر متصل می‌کند، مشخص می کند. همچنین O_n که نشانگر تعداد گره های همپوشان است در این آزمایش ها ۱۰% (معادل با ۵۰۰ گره همپوشان) تعیین شده است. پارامتر O_m نیز که نشانگر تعداد تشکل های هر گره همپوشان می‌باشد، در آزمایش های انجام شده، متفاوت در نظر گرفته شده است.

معیار ارزیابی

معیار ارزیابی مورد استفاده در این آزمایش ها NMI است که در فصل دو به آن اشاره شد. خروجی این معیار در بازه ۰ تا ۱ تعریف می‌شود و هرچه به ۱ نزدیک تر باشد، نتایج بهتری را نشان می‌دهد.

نتایج آزمایش ها

نتایج اجرای دو الگوریتم پایه و پیشنهادی به صورت زیر است. نمودارهای ارائه شده برای حالات مختلف آزمایش به ازای میانگین ۱۰۰ اجرا با انحراف معیار ۰.۰۱ ارائه شده است.

نمودار ۷: نتایج معیار NMI برای هر تکرار T₁ در تشخیص تشکل های شبکه اصلی، با مقادیر: O_m=2 و µ=۰.۱.
r₁=0.05، c=100، s=50، T₂=10، r₂=0.4 و w=1.

نمودار ۸: نتایج معیار NMI برای هر تکرار T₁ در تشخیص تشکل های شبکه اصلی، با مقادیر: O_m=4 و µ=۰.۳.
r₁=0.01، c=100، s=50، T₂=10، r₂=0.4 و w=1.

نمودار ۹: نتایج معیار NMI برای هر تکرار T₁ در تشخیص تشکل های شبکه اصلی، با مقادیر: O_m=2 و µ=۰.۱.
r₁=0.05، s=50، T₂=10، r₂=0.4 و w=1.

نمودار ۱۰: نتایج معیار NMI برای هر تکرار T₁ در تشخیص تشکل های شبکه اصلی، با مقادیر: O_m=2 و µ=۰.۱.
r₁=0.05، c=100، T₂=10، r₂=0.4 و w=1.

نمودار ۱۱: نتایج معیار NMI برای هر تکرار T₁ در تشخیص تشکل های شبکه اصلی، با مقادیر: O_m=2 و µ=۰.۱.
r₁=0.05، c=100، s=50، T₂=10 و w=1.

تحلیل نتایج

همانطور که در نمودارهای ۷ و ۸ مشاهده می‌شود، در دو شبکه LFR با مقادیر مختلف µ و O_m که در مورد اول هر گره همپوشان متعلق به دو تشکل و در دومی در چهار تشکل می‌باشد، الگوریتم پیشنهادی در هر مرحله از تکرار، به وضوح از الگوریتم پایه نتایج بهتری را ارائه داده است.