خانه بیگ دیتا تحلیل شبکه های اجتماعی، متن کاوی، داده کاوی، اوسینت و داده های حجیم
تحلیل دینامیک پیگیری انجمن ها (Community Tracking) در شبکه های اجتماعی
پیگیری انجمن ها:
با توجه به ساختار جهان هستی و اصالت داشتن رابطه‌ها در آن، گراف‌ها به عنوان ساختارهایی که روابط اشیا با هم را در سطح انتزاع مناسبی نشان می‌دهند به طور گسترده در مدل‌سازی مسائل مختلف مورد استفاده قرار گرفته‌اند. به همین سبب، در اختیار داشتن ابزارهایی مناسب برای تحلیل آنها به یک ضرورت مبدل شده و محققان بسیاری در زمینه های گوناگون به ارائه روش‌هایی برای این کار پرداخته‌اند. لذا با توجه به اهمیت خوشه‌بندی در تحلیل داده‌ها و گستردگی استفاده از گراف در مدل‌سازی مسائل، خوشه‌بندی گراف‌ها به طور خاصی مورد توجه محققان قرار گرفته و روش‌های مختلفی برای آن ارائه شده است. از آنجایی که محققان رشته‌های مختلفی بر روی این مسئله کار کرده‌اند، رویکردهای متفاوتی نسبت به آن وجود دارد. ولی کلیت بیشتر این روش‌ها پیدا کردن زیرگراف‌هایی است که ارتباط درونی زیاد و ارتباطات بیرونی کمی دارند. به این دلیل که مفهوم جامع و مانعی از “ارتباط درونی زیاد” و “ارتباط بیرونی کم” وجود ندارد، در هر روش تعریفی خاصی از این موضوع شده است و بر اساس آن راه‌حلی برای آن ارائه شده است.
پیگیری انجمن‌ها (Community Tracking) در گراف شبکه
گراف‌های موجود در دنیای واقعی معمولا ساختار ثابتی ندارند و در طول زمان تغییر می‌کنند. این تغییر می‌تواند در سطح رأس‌ها یا یال‌ها باشد. به عنوان مثال در یک شبکه اجتماعی واقعی، ممکن است در طول زمان یک رابطه دوستی بین دو شخص موجود در شبکه ایجاد شود. بدین ترتیب یک یال به مجموعه یال‌های موجود در گراف اضافه می‌شود. به طریق مشابه ممکن است یک رأس در طول زمان از شبکه اجتماعی خارج شود. لذا، یک رأس از مجموعه رئوس گراف حذف می‌شود. تغییر مجموعه رئوس و یال‌های گراف در طول زمان می‌تواند بر ساختار انجمن‌های موجود در گراف نیز تاثیر بگذارد. بدین ترتیب ممکن است یک انجمن در طول زمان بزرگتر شده و شامل نودهای بیشتری شود و یال ممکن است یک انجمن با از دست دادن اعضای خودش در طول زمان کوچکتر شود. همچنین در طول زمان ممکن است انجمن‌های جدیدی شکل گیرد یا یک انجمن به انجمن‌های کوچکتری شکسته شود. لذا، ردیابی انجمن‌ها[1] را می‌توان یکی از کارهای اساسی در زمینه تحلیل شبکه‌های اجتماعی پویا دانست. ردیابی انجمن‌ها به فرایند شناسایی و پیگیری تغییرات انجمن‌های موجود در گراف اطلاق می‌شود. ردیابی انجمن‌ها این امکان را فراهم می‌کند که بتوانیم تغییرات انجمن‌های موجود در گراف را دنبال کرده و از نحوه تغییر آنها مطلع شویم. همچنین با تحلیل تغییرات موجود در انجمن‌ها می‌توان رئوس مهمی را که دارای بیشترین تاثیر در تغییرات موجود در گراف هستند شناسایی کنیم.
در این مبحث به بررسی برخی از روش‌های مبتنی بر رخداد برای پیگیری انجمن ها می‌پردازیم. این روش‌ها از گراف موجود در نقاط زمانی مختلف تصویر می‌گیرند. در واقع این روش‌ها فرایند تکامل و تغییر گراف را به مجموعه‌ای از تصاویر ایستا می‌شکنند. سپس با استفاده از روش‌های یافتن انجمن، این روش‌ها انجمن‌های گراف هر تصویر را شناسایی می‌کنند. سپس، انجمن‌های موجود در تصاویر متوالی با یکدیگر تطبیق داده می‌شوند. در نهایت، این روش‌ها به منظور شناسایی نحوه تغییر انجمن‌ها در طول زمان، مجموعه‌ای از رخدادها را تعریف کرده و تغییرات انجمن‌ها را ردیابی می‌کنند. در ادامه به توصیف روش‌های موجود در این دسته می‌پردازیم.
اصول ریاضی برای پیگیری انجمن ها
تاکنون روش‌های مختلفی سعی کرده‌اند با ارائه چارچوبی ریاضی تغییرات موجود در شبکه‌های اجتماعی را مدل کنند. این شیوه در ردیابی انجمن‌ها در شبکه‌های اجتماعی نیز مورد استفاده قرار گرفته است. بدین منظور در مرجع [1] یک چارچوب محاسباتی و ریاضی برای ردیابی انجمن‌ها و تحلیل تغییرات آنها ارائه شده است. در این پژوهش، ابتدا در بازه‌های زمانی مختلف از گراف شبکه اجتماعی تصویر گرفته شده است. سپس، انجمن‌های موجود در گراف هر تصویر شناسایی شده است. در ادامه، شباهت انجمن‌های موجود در دو تصویر متوالی محاسبه شده و انجمن‌های مشابه در دو تصویر متوالی شناسایی شده‌اند. به منظور محاسبه شباهت دو انجمن هر معیار شباهتی که دارای خصوصیات زیر باشد می‌تواند مورد استفاده قرار گیرد:
- Sim(g, g) که برابر با شباهت انجمن g با خودش است باید بیشترین مقدار ممکن را داشته باشد.
- Sim(h, g) که برابر با شباهت انجمن g و انجمن h است باید با افزایش |h∩g| زمانی که مقدار |h|+ |g| ثابت است، بصورت یکنواخت افزایش یابد.
- Sim(h, g) باید با کاهش مقدار |h|+ |g| زمانی که |h∩g| ثابت است، بصورت یکنواخت افزایش یابد.
در نهایت، در این پژوهش از تعریف ابر انجمن[2] استفاده شده است. یک ابر انجمن مجموعه‌ای از انجمن‌های مشابه است که در بازه‌های زمانی متوالی شناسایی شده‌اند. ابر انجمن به منظور شناسایی و پیگیری تغییرات انجمن در طول زمان تعریف شده است.
پس از شناسایی ابر انجمن‌ها، در این پژوهش معیارهای مختلفی برای تحلیل تغییرات انجمن‌ها در طول زمان مانند طول متوسط ابر انجمن‌ها، میزان پایداری انجمن‌ها و میزان پایداری گره‌ها ارائه شده است.
در ادامه، پژوهشگران این پژوهش در پژوهش بعدی خود [2] این مدل را گسترش داده‌اند. در این پژوهش، مساله شناسایی و ردیابی انجمن‌ها بصورت یک مساله رنگ‌آمیزی گراف در نظر گرفته شده است. بدین منظور، ابتدا مساله بصورت یک مساله بهینه‌سازی ریاضی در نظر گرفته شده است. همچنین در این پژوهش از تعریف گروه که مجموعه‌ای از گره‌ها است که دارای یال با یکدیگر هستند در حالی که با اعضای سایر گروه‌ها یالی ندارند، استفاده شده است. برای مدل کردن مساله بصورت یک مساله ریاضی، فرضیات زیر برای رفتار هر گره در طول زمان صورت گرفته است:
- در هر برهه زمانی، هر گروه نشانگر یک انجمن است.
- در هر برهه زمانی، یک گره عضو تنها یک انجمن است. در واقع، این چارچوب فرض می‌کند که انجمن‌ها همپوشان نیستند.
- یک گره در طول زمان تمایل کمی به تغییر مکرر انجمن خود دارد و گره‌ها پایداری بالایی دارند.
- اگر یک گره در طول زمان بصورت مکرر انجمن خود را تغییر دهد، این تغییر بین تعداد معدودی از انجمن‌ها صورت می‌گیرد. در واقع، هر گره در طول زمان عضو تعداد معدودی از انجمن‌ها است.
پس از انجام فرضیات فوق، گراف گروه‌ها و گره‌ها در طول زمان ایجاد می‌شود. در این گراف بین هر گره در زمان t با همان گره در زمان t+1 یک یال ایجاد می‌شود. همچنین بین هر گره و گروهی که گره عضو آن است نیز یک یال ایجاد می‌شود.
[1] Snapshot
[2] metacommunity
منبع:
https://www.researchgate.net/figure/Examples-of-community-evolution-over-three-snapshot-graphs-by-matching-temporal-clusters_fig12_278697296
آدرس کانال تلگرام ما:
t.me/bigdata_channel
آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel
بازدیدها: 2373
برچسبCommunity Tracking پیگیری انجمن ها تحلیل دینامیک انجمن‌ها ردیابی انجمن‌ها شبکه‌های اجتماعی شناسایی انجمن‌ها
