ژانویه 22, 2021

مقاله دانشگاهی – شناسایی تشکل‌های همپوشان در شبکه‌های پویا- قسمت ۸

  • روش دوم با رویکرد شبکه های پویا طراحی شده و هدف آن ارائه راهکاری برای تشخیص تشکل های همپوشان در شبکه های پویا است.
  • برای دانلود متن کامل این پایان نامه به سایت  pipaf.ir  مراجعه نمایید.

    در ادامه، ابتدا نگاه دقیق تری به الگوریتم SLPA می‌کنیم و سپس دو روش پیشنهادی را به همراه تحلیل کارایی آنها ارائه می‌دهیم.
    نگاهی دقیق تر به روش انتشار برچسب
    همانطور که در فصل قبل اشاره شد، انتشار برچسب یکی از روش های تشخیص تشکل های همپوشان در شبکه های ایستا است که از کارایی خوبی برخوردار است. از آنجا که روش های پیشنهادی در این رساله، بر پایه انتشار برچسب طراحی شده اند، در اینجا به بررسی دقیق تر یک نمونه از الگوریتم های این روش به نام SLPA یا فرایند انتشار اطلاعات مبتنی بر گوینده-شنونده می‌پردازیم (۲۰).
    الگوریتم SLPA نمونه ارتقا یافته ای از الگوریتم LPA است. در LPA، هر گره تنها یک برچسب را برای خود حفظ می‌کند و این برچسب در هر مرحله تکرار، با توجه به اطلاعات دریافتی از گره های همسایه، بروز رسانی می‌شود. پس از اتمام تکرارها، در پایان الگوریتم، تشکل های غیر همپوشان حاصل می‌شوند. یکی از راه هایی که می‌توان این روش را به گونه ای تغییر داد که بتواند برای تشکل های همپوشان نیز قابل استفاده باشد، این است که اجازه دهیم هر گره بیش از یک برچسب برای خود داشته باشد. الگوریتم SLPA از این ایده استفاده می‌کند.
    الگوریتم
    در فرایند پویا، نیاز به تعریف دو مسئله وجود دارد: یکی نحوه انتشار اطلاعات از یک گره به سایر گره ها و دیگری نحوه پردازش اطلاعات رسیده به یک گره از سایر گره ها. موردی که در خصوص هر دو مسئله باید بررسی شود، نحوه نگهداری اطلاعات و پردازش آنهاست. برای این موضوع، الگوریتم SLPA از رفتار انسان ها الهام می‌گیرد. به این صورت که هر گره می‌تواند به عنوان گوینده و یا شنونده بسته به اینکه در نقش ارائه دهنده اطلاعات و یا دریافت کننده اطلاعات باشد، عمل کند. همچنین هر گره دارای حافظه ای است که می‌تواند برچسب هایی را که دریافت کرده است در آن ذخیره کند. در هر بار دریافت اطلاعات، گره سعی می‌کند اطلاعاتی را ذخیره کند که بیشترین اطمینان را دارد. در هنگام انتشار اطلاعات نیز، اطلاعاتی که فراوانی و تکرار بیشتری داشته باشند، شانس انتشار بیشتری خواهند داشت. این عملکرد در رفتار انسان ها نیز دیده می‌شود.
     
    الگوریتم ۱: الگوریتم SLPA
    به صورت خلاصه می‌توان عملکرد این الگوریتم را در سه مرحله تعریف کرد:

    1. در ابتدا حافظه هر گره، با برچسب همان گره (شناسه گره) مقداردهی می‌شود.
    2. سپس مراحل زیر تا زمان برآورده شدن شرط توقف به صورت تکراری ادامه می‌یابند:

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

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

    این الگوریتم از یک روش بروز رسانی غیر همزمان بهره می‌برد، به این صورت که هنگامی که یک گره حافظه خود را در زمان t بروز رسانی می‌کند، ممکن است برخی از همسایه های آن در زمان t و بعضی دیگر در زمان t-1 بروز رسانی شده باشند.
    این ویژگی که هر گره دارای حافظه ای می‌باشد که مشاهدات خود را در آن ذخیره کرده و در هر بار تصمیم گیری، با مراجعه به حافظه خود، از اطلاعات گذشته برای تصمیم گیری فعلی استفاده می‌کند، قابلیتی است که در دیگر روش های انتشار برچسب به این شکل دیده نمی‌شود.
    شرط خاتمه در این الگوریتم، به صورت ساده، با یک مقدار از پیش تعیین شده T مشخص می‌شود که حداکثر تعداد دفعات تکرار را نشان می‌دهد و با توجه به آزمایش های انجام شده معمولا عددی بزرگتر از ۲۰ در نظر گرفته می‌شود. این مسئله باعث می‌شود که شرط خاتمه، مستقل از اندازه شبکه و ساختار آن باشد.
    در مرحله پردازش نهایی نیز، میزان تکرار برچسب هایی که در حافظه هر گره وجود دارند، میزان تعلق آن گره را به هر تشکل نشان می‌دهد. این میزان تعلق می‌تواند به صورت یک بردار فازی مورد استفاده قرار گرفته و یا حتی با انتخاب برچسبی با بیشترین فراوانی، تبدیل به یک روش برای تعیین تشکل های غیر همپوشان شود. اما به طور معمول، از یک عدد از پیش تعیین شده به عنوان آستانه پذیرش عضویت در تشکل استفاده می‌شود و برچسب هایی که احتمال حضور آنها در حافظه از این مقدار کمتر باشد، از حافظه گره حذف می‌شوند. در نهایت اگر بیش از یک برچسب در حافظه برخی از گره ها موجود باشد، تشکل های همپوشان نیز ممکن خواهند بود و این گره ها به عنوان گره های همپوشان شناسایی خواهند شد. همچنین می‌توان با حذف تشکل هایی که محیط در تشکل بزرگتری هستند نتایج بهتری به دست آورد.
    تحلیل پیچیدگی زمانی
    مقداردهی اولیه به حافظه گره ها نیاز به پیچیدگی زمانی O(n) دارد که در آن n نشانگر تعداد کل گره های شبکه است. حلقه تکرار الگوریتم نیز در صورتی که شبکه تنک باشد پیچیدگی زمانی O(Tn) دارد که در آن T تعداد دفعات تکرار و n تعداد کل گره های شبکه است. در غیر این صورت پیچیدگی زمانی O(Tm) خواهد بود که در آن m تعداد کل یال های شبکه است. بنابراین می‌توان نتیجه گرفت که برای یک پیاده سازی ساده، پیچیدگی زمانی این الگوریتم نسبت به اندازه شبکه خطی است.
    بهبود کارایی روش انتشار برچسب
    اغلب الگوریتم هایی که به آنها اشاره شد با یک مقداردهی اولیه ساده برای مقادیر عضویت یا برچسب گره ها کار خود را آغاز می‌کنند و برای این موضوع از ویژگی های ساختاری شبکه استفاده نمی‌کنند. در الگوریتم SLPA نیز، در ابتدا حافظه هر گره با برچسب خود آن گره مقداردهی می‌شود، بنابراین در شروع الگوریتم، تعداد تشکل ها برابر با تعداد گره های شبکه است و پس از چندین مرحله تکرار، بسیاری از آنها با یکدگیر ادغام می‌شوند. اینطور به نظر می‌رسد که اگر بتوان روش بهتری برای مقداردهی اولیه پیدا کرد، این امر باعث بهبود کارایی الگوریتم شود.
    الگوریتم
    ایده اصلی الگوریتمی که ما ارائه می‌کنیم بر این مطلب استوار است که هر دو ساختار محلی و کلی شبکه می‌توانند برای استخراج اطلاعات مورد استفاده قرار بگیرند. در واقع می‌توان از ساختار محلی شبکه برای استخراج اطلاعات اولیه برای مقداردهی بهتر در شروع کار الگوریتم استفاده کرد و در نهایت تحلیل کارامدتری از کل شبکه ارائه داد. از آنجا که تشکل ها، زیرگراف های متراکم پیوسته ای هستند، این ایده (همانطور که در نتایج آزمایش ها نیز مشخص شده است،) مفید به نظر می‌رسد. مزیت اصلی روش ما، به دست آوردن زمان اجرای بهتر با افزایش سرعت الگوریتم، از طریق تحلیل موازی زیر شبکه های نمونه به عنوان اطلاعات اولیه است.
    تصویر ۱۴: (a) یک نمونه از زیر شبکه های انتخاب شده به همراه تشکل های آن (b و c)
    الگوریتم ۲: الگوریتم بهبود یافته تشخیص تشکل های همپوشان در شبکه های ایستا
    فرایند اصلی الگوریتم پیشنهادی به صورت زیر است:

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