ژانویه 22, 2021

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

مجموعه داده ها
بررسی کارایی و مقایسه الگوریتم های مطرح شده برای تشخیص تشکل های همپوشان، از آنجا که معمولا ساختار تشکل واقعی در دسترس نیست، کاری بسیار دشوار بنظر می‌آید. به این منظور، مجموعه داده هایی به عنوان نمونه آزمایشی تعیین شده اند که در سطح مجامع علمی شناخته شده بوده و می‌توان نتایج حاصل از عملکرد الگوریتم های مختلف بر روی آنها را با یکدیگر مقایسه کرد. این مجموعه داده ها در دو گروه مصنوعی (تولید شده توسط ماشین) و واقعی (حاصل از مشاهدات دنیای واقعی) قرار می‌گیرند. در ادامه به معرفی چند نمونه از این مجموعه داده ها می‌پردازیم.
مجموعه داده های مصنوعی[۸۸]
با توجه به اینکه ساختار تشکل اغلب شبکه های اجتماعی واقعی در دسترس نیست، نمی‌توان از این داده ها برای بررسی کارایی الگوریتم پیشنهادی استفاده نمود. به همین دلیل، محققان اغلب به فکر ایجاد مجموعه داده های مصنوعی هستند. به همین منظور، تعدادی از این شبکه های مصنوعی تولید شده و مورد استقبال زیادی قرار گرفته اند. یکی از مهمترین این شبکه های مصنوعی، شبکه LFR (24) است که در اینجا به آن اشاره می‌کنیم.
برای تولید گراف های مصنوعی با ساختار تشکل از پیش معلوم، روشی توسط Lancichinetti و Fortunato ارائه شد که قابلیت تولید گراف هایی با اندازه های دلخواه و همراه با ساختار تشکل آن ها را دارد. پیچیدگی محاسباتی این روش، خطی و بر اساس تعداد یال ها بوده و گراف هایی را به ترتیب قدم های زیر تولید می‌کند:

برای دانلود متن کامل این پایان نامه به سایت  fumi.ir  مراجعه نمایید.

  1. تعداد تشکل هایی که هر رأس باید عضو آن ها باشد تولید کرده و به هر رأس بر اساس توزیع قانون توانی[۸۹] با نمای درجه نسبت می‌دهد.
  2. برای تعداد ثابتی از تشکل ها، اندازه های آن ها را با یک توزیع قانون توانی دیگر با نمای نسبت می‌دهد.
  3. گراف دوبخشی بین رأس ها و تشکل ها را بر اساس مدل configuration را تشکیل می‌دهد.
  4. برای هر رأس، بر اساس (پارامتر ترکیب)، درجه های داخلی[۹۰] هر تشکل و همچنین درجه ی بین تشکل ها[۹۱] را نسبت می‌دهیم.
  5. گراف ها را برای هر تشکل و یال های بین تشکل ها را با توجه به مدل configuration می‌سازیم.

این گراف ها دارای پارامترهایی هستند که پیش از تولید گراف باید تعیین شوند. پارامتر n نشانگر تعداد گره های شبکه می‌باشد. kavg و kmax به ترتیب میانگین و حداکثر درجه هر گره در گراف هستند. Smin و Smax حداقل و حداکثر اندازه تشکل ها هستند. On تعداد گره های همپوشان و Om تعداد تشکل هایی است که هر گره همپوشان به آنها تعلق دارد.
مجموعه داده های واقعی[۹۲]
به دلیل اینکه ممکن است قضاوت بر مبنای مجموعه داده های مصنوعی، اطمینان لازم را حاصل نکند، معمولا تعدادی از مجموعه داده های واقعی نیز مورد استفاده قرار می‌گیرند. از جمله این مجموعه داده ها می‌توان به: شبکه Flicker (شبکه اجتماعی اشتراک گذاری تصاویر)، شبکه DBLP (شبکه روابط نویسندگان مقالات)، شبکه Dolphin (شامل مجموعه ای از دلفین ها)، شبکه Zachary Karate Club (اعضای یک باشگاه کاراته)، شبکه American Football College (شامل نتایج مسابقات فوتبال) و شبکهHigh School Friendship (روابط بین دانش آموزان یک مدرسه) اشاره کرد. در این میان، تعدادی از آن ها، بسیار بزرگ و پویا بوده و تنها می‌توان به پاره ای از مشاهدات اکتفا کرد و برخی، بسیار کوچک و ایستا بوده و ساختار تشکل مشخصی دارند.
معیارهای ارزیابی[۹۳]
برای ارزیابی کارایی یک الگوریتم پیشنهادی برای شناسایی تشکل ها، همواره نیاز به تعریف معیاری است که نشان دهنده ی میزان شباهت ساختار تشکل شناسایی شده توسط الگوریتم و ساختار تشکل واقعی گراف مورد نظر است. برای این کار، معیارهای زیادی ارائه شده است که در اینجا به یکی از مطرح ترین و معتبرترین آنها اشاره می‌کنیم.
معیار NORMALIZED MUTUAL INFORMATION
ما در اینجا به نسخه ی ارتقا یافته ی NMI که با ساختارهای تشکل همپوشان سازگاری دارد اشاره می‌کنیم (۱۴). این معیار طبق رابطه ی زیر محاسبه می‌شود.

این متغیر در بازه ی [۱و۰] قرار دارد و زمانی برابر ۱ است که دو تشکل و یکسان باشند. برای محاسبه ی این مقدار، به محاسبات زیر نیاز داریم:

که در آن، از رابطه زیر بدست می‌آید:

Copyright © All rights reserved. | Newsium by AF themes.