صفحه نخست --> تحلیل شبکه های اجتماعی --> بررسی ساختار و توپولوژی گراف شبکه های اجتماعی

بررسی ساختار و توپولوژی گراف شبکه های اجتماعی

بررسی ساختار و توپولوژی گراف شبکه های اجتماعی

شبکه‌های اجتماعی  به طور عمده از دو دیدگاه قابل بررسی می‌باشند: ساختار و دینامیک ( به زبان ساده داینامیک یعنی تحلیل در بستر زمان). بررسی‌ها نشان می‌دهد که این شبکه ها در خصوصیات مشترک ساختاری به طرز قابل توجّهی اشتراک دارند. تحلیل های با ارزشی به منظور گراف کاوی تا کنون ارائه شده است. ولی معمولا چند دسته الگوریتم زیر بیشترین کاربرد ها را دارند.
۱- الگوریتم های تشخیص مرکزیت
۲- الگوریتم های تشخیص انجمن
۳- الگوریتم های بصری سازی
۴- الگوریتم های پیشبینی ارتباطات
۵- الگوریتم های نمومه برداری

در این قسمت ابتدا به خصوصیات ساختاری که در سال‌های اخیر و با توجّه به افزایش میزان داده‌های قابل دسترسی در مورد شبکه‌ها و نیز افزایش قدرت محاسباتی برای بررسی آن‌ها کشف گردیده است، اشاره می‌نماییم. سپس به مدل‌های ریاضی‌ای که برای ایجاد گراف‌هایی با این خصوصیات ساختاری پیشنهاد شده‌اند خواهیم پرداخت. در بخش های دیگر به ویژگیهای دینامیکی خواهیم پرداخت.

در دهه‌ی اخیر، بررسی ساختار شبکه‌ها با استفاده از داده‌های واقعی و ابزار‌های پردازشی قوی،‌ خصوصیات مشابه انواع شبکه‌ها با یکدیگر را آشکار کرده است. به عنوان مثال کوچک بودن میانگین کوتاهترین فاصله‌ها، بالا بودن خوشه‌بندی  و وجود انجمنها در شبکه‌های پیچیده تنها برخی از خصوصیات مشترک شبکه‌ها در علوم مختلف می‌باشد. حضور تمامی این خصوصیات در شبکه‌های واقعی آنان را از مدل‌های بررسی شده در ریاضیات، مانند تور‌ها (Lattice) و گراف‌های تصادفی(Random Graphs)، متمایز می‌کند. این خصوصیات موجب شده است که نحوه‌ی شکل‌گیری تکاملی شبکه‌های واقعی مورد بررسی دقیق قرار گیرد و مدل‌هایی برای ایجاد شبکه‌های پیچیده با چنین ساختار‌هایی با الهام از نحوه‌ی شکل‌گیری شبکه‌های واقعی ارائه گردد.

 

žتوپولوژی شبکه های اجتماعی نقش مهمی در استخراج برخی اطلاعات از آنها ایفا میکند. توپولوژی شبکه به ساختار و نحوه اتصال نودهای آن اشاره دارد. قسمت اعظم فرایند استخراج توپولوژی شبکه با استفاده از توزیع درجه نودها انجام می شود.
امروزه با بررسی ساختار شبکه‌ها با استفاده از داده‌های واقعی و ابزار‌های پردازشی قوی،‌ خصوصیات مشابه انواع شبکه‌ها با یکدیگر را آشکار کرده است. به عنوان مثال کوچک بودن میانگین کوتاهترین فاصله‌ها  ، بالا بودن خوشه‌بندی  و وجود انجمنها در شبکه‌های پیچیده تنها برخی از خصوصیات مشترک شبکه‌ها در علوم مختلف می‌باشد. حضور تمامی این خصوصیات در شبکه‌های واقعی آنان را از مدل‌های بررسی شده در ریاضیات، مانند تور‌ها(Lattice) و گراف‌های تصادفی(Random Graphs)، متمایز می‌کند. این خصوصیات موجب شده است که نحوه‌ی شکل‌گیری تکاملی شبکه‌های واقعی مورد بررسی دقیق قرار گیرد و مدل‌هایی برای ایجاد شبکه‌های پیچیده با چنین ساختار‌هایی با الهام از نحوه‌ی شکل‌گیری شبکه‌های واقعی ارائه گردد. برخی از مهم ترین خصوصیات ساختاری شبکه های اجتماعی در ذیل آمده است/

  • توزیع فراوانی درجات گره ها(Degree distribute)
  • ضریب کلوپ  پولداران(Rich club)
  • قطر گراف (Diameter)
  • ضریب تراگذری (Transitivity coefficient )
  • ضریب خوشه بندی(Clustering Coefficient)
  • محاسبه کوتاهترین مسیر میان گرههای گراف
  • فاصله متوسط گره ها از هم

همانطور که میبینید تنوع این معیارها و تعداد آنها بسیار زیاد است از همین رو ما به توضیح مهمترین و پرکاربردترین آنها  اکتفا خواهیم کرد. معیارهای مورد بررسی ما در اینجا عبارتند از:

  • خصوصیت استقلال از مقیاس (به عبارتی توزیع فراوانی درجات گره ها)

žدرجه یک گره تعداد گره هایی است که با آن گره در همسایگی مستقیم قرار دارد.žهر چقدر درجه یک گره بیشتر باشد، اهمیت آن گره بیشتر می شود.žمثلا در شبکه وب، اگر درجه ورودی یک دامنه زیاد باشد، یعنی سایت مرجع است، و اگر درجه خروجی آن زیاد باشد، یعنی اینکه سایتی است که از اطلاعات (اخبار) سایت های دیگر استفاده می کند.ž توزیع درجات، توزیع احتمال این درجات روی کل شبکه است. žتوزیع درجات شبکه  p(k) با استفاده از رابطه p(k)=n_k/n   محاسبه می شود.

گراف‌های مورد بررسی در ریاضیات عموماً از ساختار همگونی(Homogenous) مانند تورها و گراف‌های تصادفی برخوردارند. تا قبل از بررسی شبکه‌های واقعی تصور بر این بود که توزیع درجه‌ی شبکه‌های واقعی مانند این‌گونه گراف‌ها پوآسن باشد. امّا با بررسی بیشتر روشن شد که توزیع درجه در اکثریت قریب به اتّفاق شبکه‌های واقعی از توزیع “قانون توانی (Power Law)” تبعیت می‌کند. همان‌طور که مشاهده می‌شود تعداد گره‌هایی با درجه بالا کم و تعداد گره‌هایی با درجه کم زیاد است و این توزیع را می­توان با یک توزیع توانی تخمین زد. ترسیم نمودار log-log این گراف یک خط راست را نشان می‌دهد.

توزیع درجات
توزیع درجات

به این‌گونه شبکه‌ها، شبکه‌های “مستقل از مقیاس(Scale Free)” می‌گویند. چرا که این توزیع درجه تنها توزیع درجه‌ای است که در صورت بزرگ و کوچک شدن مقیاس (به غیر از اضافه شدن یک ضریب) ثابت می‌ماند. این شبکه‌ها از تعداد بسیار زیادی رأس با درجه‌ی بسیار پایین و تعداد بسیار کمی رأس با درجه بالا که به آن‌ها مرکز(Hub) می‌گوییم تشکیل شده اند.

توزیع درجات
توزیع درجات گراف شبکه اجتماعی با گراف تصادفی

  • خصوصیت دنیای کوچک شده

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

دنیای کوچک شده
دنیای کوچک شده

یکی از نشانه‌های این پدیده اوّلین بار در شبکه‌های آشنایی اجتماعی توسط میلگرم(Milgram) مشاهده شده است. او در آزمایش مشهور خود از افرادی که به تصادف از ایالت نبراسکا(Nebraska) انتخاب نموده بود، خواست که نامه‌هایی را به فردی در ایالت بوستون(Boston) که تنها نام، شغل و محدوده‌ی زندگی او به صورت تقریبی روشن بود ارسال نمایند. او دریافت که به طور میانگین هر نامه با ۶ بار ارسال به دست فرد مورد نظر رسیده است. این پدیده اخیراً در رد و بدل کردن ایمیل‌ها نیز مشاهده شده است.این خصوصیت در شبکه‌های بیولوژیکی و تکنولوژیکی نیز قابل مشاهده است.

  • خصوصیت ضریب خوشه بندی بالا

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

ضریب خوشه بندی
ضریب خوشه بندی

معیار پیمانگی یا ماژولاریتی در سالیان اخیر به عنوان یکی ار اصلی‌ترین معیارهای ارزیابی کیفیت روش‌های خوشه‌بندی مورد استفادده قرار گرفته است. اگر تعداد یال‌های درون خوشه‌ای بهتر از حالت گراف تصادفی نباشد، پیمانگی برابر صفر است.  حداکثر مقدار پیمانگی زمانی به دست می‌آید که تمام رئوس هر خوشه به هم متصل باشند و یالی خوشه‌ها را به هم متصل نکند. تجربه نشان می‌دهد که در گراف‌های متعلق به شبکه‌های اجتماعی این مقدار میان ۰٫۳ تا ۰٫۷ است.

t.me/bigdata_channel

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *