در نمودارهای ۹ ، ۱۰ و ۱۱ میتوان تاثیر مقادیر مختلف c، s و r2 را بر روی عملکرد الگوریتم پیشنهادی مشاهده کرد. بر اساس نتایج به دست آمده میتوان گفت، با انتخاب زیر شبکه های بیشتر از شبکه اصلی، نتایج بهتر خواهند شد، زیرا مناطق بیشتری از شبکه پوشش داده شده و اطلاعات بیشتری جمع آوری خواهد شد، اما از سوی دیگر نیاز به توان پردازشی بیشتری نیز برای این کار میباشد (نمودار ۹). همچنین با افزایش تعداد گره های زیر شبکه ها، اطلاعات بیشتری استخراج خواهد شد، اما در عوض زمان پیش پردازش افزایش خواهد یافت، چون این زمان با اندازه زیر شبکه ها رابطه مستقیم دارد و همچنین زمان مورد نیاز برای تشخیص تشکل ها در زیر شبکه ها نیز افزایش مییابد (نمودار ۱۰). با افزایش آستانه پذیرش برچسب ها در تعیین تشکل های زیر شبکه ها، اطلاعات استخراج شده قابل اطمینان تر بوده ولی میزان آن کاهش خواهد یافت (نمودار ۱۱). با افزایش تعداد تکرار T2 در مرحله تشخیص نیز، تشکل های استخراج شده برای زیر شبکه ها قابل اطمینان تر خواهند بود اما زمان پیش پردازش، افزایش خواهد یافت و همچنین ممکن است برخی از تشکل ها در زیر شبکه ها از دست بروند. با افزایش وزن اعمال اطلاعات در مقداردهی اولیه برای شبکه اصلی، الگوریتم تشخیص تشکل ها به مقادیر اولیه حساس تر خواهد بود.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
تحلیل پیچیدگی زمانی
با فرض اینکه اگر از الگوریتم SLPA برای دو مرحله مقداردهی اولیه و تحلیل نهایی استفاده شود، پیچیدگی زمانی به صورت زیر خواهد بود:
پیچیدگی زمانی برای مرحله استخراج اطلاعات و مقداردهی اولیه به صورت O(c.s.T2) خواهد بود که در آن c تعداد زیر شبکه های نمونه، s اندازه زیر شبکه ها و T2 حداکثر تکرار الگوریتم تشخیص تشکل ها خواهد بود. از آنجا که تحلیل زیر شبکه ها به صورت موازی قابل انجام است میتوان از پارامتر c صرفنظر کرد.
پیچیدگی زمانی برای مرحله تشخیص تشکل های شبکه اصلی بر اساس الگوریتم SLPA به صورت O(nT1) خواهد بود که در آن n تعداد کل گره های شبکه و T1 حداکثر تکرارهای الگوریتم خواهد بود.
از آنجا که در کاربردهای واقعی اندازه شبکه ها عموما بزرگ است (n>1000)، بنابراین مقدار n.T1 بسیار بزرگتر از s.T2 خواهد بود و میتوان گفت که پیچیدگی زمانی الگوریتم پیشنهادی نسبت به اندازه شبکه خطی است.
تشخیص تشکل های همپوشان در شبکه های پویا
هدف از ارائه روش پیشنهادی، طراحی الگوریتمی است که بتواند به صورت کاراتری برای تشخیص تشکل های همپوشان در شبکه های پویا عمل کند. برای نمایش میزان کارایی این روش، آزمایشی به صورت زیر طراحی گردید:
-
- ابتدا از روی هر مجموعه داده LFR (که یک شبکه ایستا است و در فصل ۲ به آن اشاره شد)، با روشی که در ادامه به آن پرداخته شده است، یک سری از شبکه ها به عنوان وضعیت های قبلی شبکه اصلی، تولید میشوند.
-
- برای مقایسه، الگوریتمی مبتنی بر SLPA را (مانند آزمایش های قبل،) به عنوان روش پایه، برای تشخیص تشکل ها در شبکه نهایی بکار میگیریم.
-
- سپس با بهره گرفتن از الگوریتم پیشنهادی، در آزمایش های مختلف، از یک وضعیت مشخص قبلی، آغاز کرده و تشخیص تشکل ها را تا رسیدن به شبکه اصلی ادامه میدهیم، به گونه ای که روش تشخیص آن در حالت نهایی، مشابه روش پایه باشد. به این ترتیب، میتوان میزان تاثیر اطلاعات استخراج شده از گذشته را که در روش پیشنهادی ارائه شده است با حالتی که صرفا از یک روش ایستا برای تشخیص استفاده شود، مقایسه کرد.
-
- در انتها، نتایج حاصل از عملکرد دو الگوریتم را محاسبه و با یکدگیر مقایسه میکنیم.
مجموعه داده ها
از آنجا که تاکنون مجموعه داده شناخته شده ای که در آن تشکل های همپوشان برای شبکه های پویا مشخص شده باشد ارائه نشده است، ما از یک روش ابتکاری برای تولید این داده ها از روی مجموعه داده های شناخته شده موجود در حوزه شبکه های ایستا استفاده کرده ایم. برای این منظور، الگوریتمی طراحی گردید که پارامترهای: تعداد گره ها و یال های حذف شده و تعداد گره ها و یال های اضافه شده را دریافت کرده و از روی شبکه فعلی، شبکه جدیدی را ایجاد میکند. در آزمایش های انجام شده از چندین شبکه LFR به عنوان ورودی برای تولید وضعیت های پیش از آن استفاده شده است. مشخصات این شبکه ها در جدول ۳ آمده است.
تصویر ۱۵ : شبکه اولیه (سمت راست) و شبکه های ایجاد شده از روی آن
شبکه
N
kavg
kmax
µ
minC
maxC
On
Om
۱
۱۰۰۰
۱۰
۵۰
۲
۱
۰.۰۱
۱۰
۵۰
۱۰%
۲
۲
۱۰۰۰
۲۰
۱۰۰
۲
۱
۰.۰۳
۲۰
۱۰۰
