بررسی و تحلیل معیارهای مرکزیت برای شناسایی افراد مهم در شبکه‌های پیچیده

گزارش نهایی مقاله درس شبکه‌های پیچیده و پویا

رشته‌ مهندسی کامپيوتر گرايش نرم‌افزار

عنوان

بررسی و تحلیل معیارهای مرکزیت برای شناسایی افراد مهم در شبکه‌های پیچیده

استاد:

دکتر علی‌اکبری

پژوهشگر:

سیدعلی سادات خراسانی

بهمن 1404

چکيده:

شناسایی گره‌های تأثیرگذار و حیاتی در شبکه‌های پیچیده، یکی از چالش‌برانگیزترین مسائل در علم شبکه است که کاربردهای گسترده‌ای از مدیریت جریان اطلاعات تا کنترل شیوع بیماری‌ها دارد. ادبیات کلاسیک این حوزه، با محوریت پژوهش‌های فریمن، مرکزیت را عمدتاً بر اساس ویژگی‌های ساختاری محلی و ایستا مثل درجه، بینابینی و نزدیکی تعریف کرده است. این معیارها فرض می‌کنند که ارزش تمام اتصالات یکسان است. پس از آن بوناسیچ با نقد این دیدگاه، مدل‌های بازگشتی را معرفی کرد که در آن قدرت یک گره تابعی از قدرت همسایگانش است و با پارامتر β، ماهیت تعاملات مثل همکاری یا رقابت را مدل‌سازی می‌کند. این رویکرد بعدها در الگوریتم PageRank برای رتبه‌بندی صفحات وب با استفاده از مدل گردشگر تصادفی توسعه یافت. علیرغم این پیشرفت‌ها، یک چالش بنیادین باقی مانده است، اکثر معیارهای سنتی، شبکه را ساختاری همگن درنظر می‌گیرند و از ساختارهای مزوسکوپیک مثل انجمن‌های همپوشان غافل هستند. پژوهش حاضر با مرور انتقادی سیر تحول معیارهای مرکزیت، نشان می‌دهد که نادیده گرفتن ساختار انجمنی منجر به خطای قابل‌توجه در شناسایی گره‌های پل‌زننده و رهبران محلی می‌شود. در نهایت، این مقاله یک چارچوب پیشنهادی نوین را ارائه می‌دهد که با ترکیب منطق بازگشتی بوناسیچ و مفهوم مرکزیت ماژولار، نفوذ گره‌ها را در دو سطح محلی و جهانی تفکیک کرده و دقت تحلیل را در شبکه‌های واقعی بهبود می‌بخشد.

واژگان کليدي: شبکه‌های پیچیده، مرکزیت، بوناسیچ، PageRank، ساختار انجمنی، نفوذ محلی و جهانی.

فهرست مطالب

فصل اول مقدمه. 7

1-1- بیان مسئله و اهمیت موضوع. 7

1-2 – سیر تحول تاریخی.. 7

1-3 -ظهور مدل‌های بازگشتی و مبتنی بر جریان. 8

1-4 -چالش ساختارهای انجمنی همپوشان. 8

1-5 -نوآوری و ساختار مقاله. 9

فصل دوم مبانی نظری و مرور ادبیات.. 10

2-1- مقدمه. 10

2-2- شفاف‌سازی مفهومی فریمن.. 10

2-3- خانواده معیارهای بوناسیچ. 12

2-4- پیج‌رنک: انقلابی در گراف‌های جهت‌دار وب.. 12

فصل سوم چالش ساختار انجمنی.. 13

3-1- مقدمه. 14

3-2- کوری ساختاری در معیارهای کلاسیک... 14

3-3- چالش انجمن‌های همپوشان. 15

3-4- نارسایی معیارهای جهانی در شبکه‌های پویا 15

3-5- تفکیک نفوذ محلی و جهانی.. 16

فصل چهارم روش پیشنهادی.. 17

4-1- مقدمه. 17

4-2- مدلسازی ریاضی فضا و تعاریف پایه. 17

4-3- تجزیه بردار نفوذ محلی.. 18

4-4- تجزیه بردار نفوذ جهانی.. 18

4-5- تلفیق بازگشتی.. 19

4-5-1- تشریح اجزاء و پارامترها 19

4-6- تحلیل همگرایی و پیچیدگی الگوریتم. 20

4-6-1- پیچیدگی زمانی.. 20

4-7- مقایسه کیفی با روش‌های پیشین.. 21

فصل پنجم روش تحلیل و آزمایش... 22

5-1- مقدمه. 22

5-2- مجموعه داده مورد استفاده 22

5-3- سناریوی مقایسه و نتایج مورد انتظار 22

5-3-1- تحلیل تطبیقی.. 23

5-4- تحلیل نتایج حاصل از اجرا 23

5-5- تحلیل حساسیت پارامتر α. 25

فصل ششم روش نتیجه‌گیری و پیشنهادات.. 26

6-1- مقدمه. 26

6-2- محدودیت‌ها و مسیرهای پژوهشی آینده 26

فصل هفتم منابع. 28

فصل اول
مقدمه

1-1-    بیان مسئله و اهمیت موضوع

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

1-2 – سیر تحول تاریخی

تلاش‌های اولیه برای کمی‌سازی اهمیت گره‌ها، با دسته‌بندی کلاسیک لینتون فریمن در سال ۱۹۷۹ به بلوغ رسید. او نشان داد که مرکزیت یک مفهوم سه‌وجهی است:

1.     مرکزیت درجه: نشان‌دهنده فعالیت ارتباطی است.

2.     مرکزیت بینابینی: بر پتانسیل کنترل جریان اطلاعات دلالت دارد.

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

1-3 -ظهور مدل‌های بازگشتی و مبتنی بر جریان

برای رفع نقص مدل‌های قبلی، فیلیپ بوناسیچ در سال ۱۹۸۷ یک تغییر پارادایم ایجاد کرد. او استدلال کرد که مرکزیت یک ویژگی مطلق نیست، بلکه حاصل تعاملات بازگشتی در شبکه است. در مدل او، مرکزیت هر گره متناسب با مجموع مرکزیت همسایگانش است. بوناسیچ با معرفی پارامتر β نشان داد که در شبکه‌های مبادله‌ای، قدرت ناشی از اتصال به افراد ضعیف و وابسته است (β < 0)، در حالی که در شبکه‌های ارتباطی، اتصال به افراد قدرتمند باعث افزایش نفوذ می‌شود (β > 0).

این دیدگاه بازگشتی، پایه و اساس انقلاب موتورهای جستجو در دهه ۹۰ میلادی شد. سرگی برین و لری پیج با معرفی الگوریتم PageRank، ایده بوناسیچ را برای گراف جهت‌دار وب توسعه دادند. آن‌ها با مدل‌سازی رفتار یک گردشگر تصادفی[2] و حل مشکل بن‌بست‌های گراف از طریق بردار منبع E، معیاری ارائه دادند که اهمیت جهانی یک صفحه را بر اساس کیفیت لینک‌های ورودی می‌سنجید، نه صرفاً تعداد آن‌ها.

1-4 -چالش ساختارهای انجمنی همپوشان

علیرغم تکامل معیارهای قبل، اکثر پژوهش‌های کلاسیک شبکه را به صورت یک ساختار یکپارچه و بدون مرز در نظر می‌گیرند. اما مطالعات مدرن نشان می‌دهد که شبکه‌های واقعی دارای ساختار مزوسکوپیک[3] نظیر انجمن‌ها هستند. نکته مهم‌تر آن است که در بسیاری از شبکه‌های اجتماعی و زیستی، این انجمن‌ها همپوشان هستند؛ یعنی یک گره می‌تواند همزمان عضو چندین گروه باشد. مثل فردی که همزمان در شبکه خانواده، همکاران و دوستان خودش عضویت دارد.

معیارهای کلاسیک مثل PageRank و بینابینی امکان تفکیک نقش گره‌ها در این لایه‌های مختلف را ندارند. آن‌ها نمی‌توانند تمایز قائل شوند میان یک رهبر محلی که فقط در انجمن خودش نفوذ دارد و یک پل جهانی که انجمن‌های مختلف را به هم وصل می‌کند. غلمان و همکاران در سال ۲۰۱۹ نشان دادند که نادیده گرفتن این ساختار، منجر به درک ناقص از داینامیک شبکه می‌شود و پیشنهاد دادند که مرکزیت باید ترکیبی از نفوذ محلی و نفوذ جهانی باشد.

1-5 -نوآوری و ساختار مقاله

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

فصل دوم
مبانی نظری و مرور ادبیات

2-1- مقدمه

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

2-2- شفاف‌سازی مفهومی فریمن

لینتون فریمن در مقاله مرجع خود با عنوان (مرکزیت در شبکه‌های اجتماعی: شفاف‌سازی مفهومی)، به آشفتگی موجود در ادبیات آن زمان پایان داد. او با استفاده از گراف ستاره به عنوان نقطه مرجع، استدلال کرد که هر معیار معتبر مرکزیت باید برای گره مرکزی یک گراف ستاره، بیشترین مقدار ممکن را تولید کند. فریمن سه مفهوم متمایز را تفکیک کرد[1]:

الف) مرکزیت درجه: فعالیت و قابلیت رویت

این معیار بر پایه ایده فعالیت ارتباطی[1] بنا شده است. گره‌هایی که درجه بالایی دارند، احتمالاً در کانون اتفاقات هستند.

برای یک گراف با مشخصات G = (V , E) با n گره، درجه گره pk برابر است با تعداد یال‌های متصل به آن:

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

ب) مرکزیت بینابینی: کنترل و دروازه‌بانی

فریمن استدلال کرد که جریان اطلاعات همیشه از مسیرهای مستقیم عبور نمی‌کند. گره‌ای که بین گره‌های دیگر قرار گرفته، پتانسیل کنترل یا قطع جریان را دارد. اگر gij تعداد کل کوتاه‌ترین مسیرها بین گره i و j باشد و gij(pk) تعداد آن مسیرهایی باشد که دقیقاً از گره pk عبور می‌کنند، احتمال اینکه گره k واسطه ارتباط آن دو باشد، برابر است با  مرکزیت بینابینی گره k مجموع این احتمالات برای تمام جفت‌گره‌هاست:

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

این معیار در شناسایی نقاط شکست[2] و گلوگاه‌های شبکه بسیار حیاتی است.

ب) مرکزیت نزدیکی: استقلال و کارایی

سومین مفهوم، به حداقل رساندن فاصله تا دیگران است. گره‌ای که به بقیه نزدیک است، مستقل است زیرا برای ارسال پیام به واسطه‌های کمتری نیاز دارد. سابیدوسی (۱۹۶۶) این مفهوم را با دوری تعریف کرد که مجموع فواصل ژئودزیک است:

همچنین برای مقایسه بین شبکه‌ها، فریمن فرمول زیر را ارایه داد:

این شاخص نشان‌دهنده سرعت انتشار اطلاعات از یک گره به کل شبکه است.

2-3- خانواده معیارهای بوناسیچ

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

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

که در اینجا R ماتریس مجاورت و I ماتریس همانی است.

تحلیل پارامتر :

بوناسیچ نشان داد که علامت و اندازه  تفسیر قدرت را تغییر می‌دهد [2]:

1.    شبکه‌های ارتباطی (  > 0): در اینجا، اتصال به افراد قدرتمند باعث افزایش قدرت می‌شود. این مدل با مفهوم وضعیت (Status) سازگار است. هرچه همسایگان شما مرکزی‌تر باشند، شما نیز مرکزی‌تر خواهید بود.

2.    شبکه‌های مبادله‌ای (  < 0): بر اساس تئوری مبادله کوک (1983)، قدرت در چانه‌زنی ناشی از وابستگی دیگران است. اگر شما به گره‌هایی متصل باشید که ارتباطات کمی دارند، قدرت شما افزایش می‌یابد. بنابراین، داشتن همسایگان ضعیف با درجه پایین باعث افزایش قدرت شما می‌شود.

این مدل نشان داد که مرکزیت یک ویژگی مطلق نیست، بلکه تابعی از دینامیک حاکم بر شبکه است.

2-4- پیج‌رنک: انقلابی در گراف‌های جهت‌دار وب

در اواخر دهه ۹۰، پیج و برین الگوریتم PageRank را برای حل مشکل رتبه‌بندی در وب ارائه دادند. این الگوریتم در واقع بسطی از ایده مرکزیت بردار ویژه [3]بود، اما با یک نوآوری حیاتی برای مدیریت گراف‌های جهت‌دار و گسسته. فرمول پایه مشابه بوناسیچ با استفاده از معیار    > 0 بود:

اما این مدل در مواجهه با دو پدیده وب شکست می‌خورد:

1. Rank Sinks: صفحاتی که لینک ورودی دارند اما لینک خروجی ندارند یا به خودشان لینک می‌دهند، باعث می‌شوند امتیاز در آن‌ها انباشته شود.

2. گراف‌های ناهمبند: وب یک گراف یکپارچه نیست.

راه‌حل: مدل گردشگر تصادفی[4]

پیج‌رنک فرض می‌کند کاربر با احتمال d روی لینک‌ها کلیک می‌کند و با احتمال 1-d خسته شده و به صورت تصادفی به یک صفحه دیگر می‌پرد که  به آن Teleportation می‌گویند بنابراین فرمول اصلاح شده آن عبارت است از [3]:

معمولاً 0.85 = dدر نظر گرفته می‌شود. از دیدگاه جبر خطی، بردارPageRank بردار ویژه اصلی ماتریس انتقال احتمالاتی[5] شبکه است. این مدل توانست با موفقیت مفهوم کیفیت لینک را کمی‌سازی کند؛ لینکی که از یک صفحه معتبر مثلYahoo می‌آید، وزن بسیار بیشتری نسبت به لینکی از یک صفحه شخصی دارد.

فصل سوم
چالش ساختار انجمنی

3-1- مقدمه

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

3-2- کوری ساختاری در معیارهای کلاسیک

معیارهای سنتی مرکزیت، شبکه را به صورت یک توده یکپارچه و مسطح می‌بینند. در این دیدگاه، یک یال تنها یک یال است و تفاوت کیفی میان یال‌های مختلف قائل نمی‌شوند. اما در واقعیت، شبکه‌های پیچیده نظیر شبکه‌های اجتماعی، استنادی و بیولوژیک دارای ساختار انجمنی هستند؛ یعنی نواحی متراکمی که در آن‌ها گره‌ها اتصالات داخلی فراوانی دارند، در حالی که اتصالات بین این نواحی یعنی یال‌های میان‌بر اندک است [4].

این کوری ساختاری منجر به خطای سیستماتیک در ارزیابی اهمیت گره‌ها می‌شود. برای تشریح این خطا، دو نوع گره متمایز را در نظر بگیرید:

1. هاب‌های استانی: گره‌هایی که درجه بالایی دارند اما تمام اتصالاتشان محدود به یک انجمن خاص است. این گره‌ها در حفظ انسجام داخلی گروه خود حیاتی هستند اما در انتشار سراسری اطلاعات[2] نقش محدودی دارند.

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

معیارهای کلاسیک نظیر PageRank یا بردار ویژه، تمایل دارند امتیاز را در نواحی متراکم شبکه هاب‌های استانی انباشته کنند و اغلب ارزش استراتژیک پل‌های ارتباطی را نادیده می‌گیرند. غلمان نشان می‌دهد که در فرآیندهای انتشار اپیدمی یا شایعه، گره‌های پل‌زننده حتی با درجه پایین بسیار خطرناک‌تر و مؤثرتر از هاب‌های ایزوله هستند، زیرا دسترسی سریع به بخش‌های بکر شبکه را فراهم می‌کنند. معیارهای کلاسیک قادر به تمایز میان این دو نقش نیستند [4].

3-3- چالش انجمن‌های همپوشان

پیچیدگی مسئله فراتر از وجود انجمن‌های مجزاست. در اکثر شبکه‌های اجتماعی واقعی، انجمن‌ها دارای مرزهای صلب نیستند، بلکه همپوشان[3] هستند. یک کاربر در توییتر یا فیس‌بوک، همزمان عضو کلاستر همکاران، دوستان دوران تحصیل و علاقه‌مندان به تکنولوژی است. غلمان و همکاران استدلال می‌کنند که معیارهای سنتی که برای هر گره تنها یک عدد اسکالر مثل یک عدد PageRank تولید می‌کنند، ذاتاً برای توصیف این واقعیت چندبعدی ناتوان هستند. وقتی یک گره عضو k انجمن مختلف است، نفوذ او ماهیت برداری پیدا می‌کند. یک گره ممکن است در انجمن A یک رهبر فکری باشد و دارای نفوذ محلی بالا باشد، اما در انجمن B تنها یک عضو حاشیه‌ای باشد. مدل‌های تک‌بعدی[4] با میانگین‌گیری از این نقش‌ها، اطلاعات حیاتی درباره موقعیت استراتژیک گره را از بین می‌برند.

3-4- نارسایی معیارهای جهانی در شبکه‌های پویا

یکی دیگر از ابعاد نقد ما، مسئله پویایی است. در شبکه‌های پویا که یال‌ها مدام اضافه یا حذف می‌شوند، تأثیر یک تغییر توپولوژیک بر مرکزیت گره‌ها یکسان نیست.

• اضافه شدن یک یال در داخل یک انجمن متراکم، تأثیر کمی بر ساختار کلان شبکه و طول مسیرها دارد.

• اما اضافه شدن یک یال میان دو انجمن جدا افتاده، می‌تواند قطر شبکه را به شدت کاهش دهد و الگوی جریان اطلاعات را دگرگون کند.

معیارهای کلاسیک مثل Closeness یا PageRank که کل گراف را یک ماتریس واحد می‌بینند، برای به‌روزرسانی نیاز به محاسبات سنگین دارند و نمی‌توانند به سرعت تشخیص دهند که آیا یال جدید یک لینک محلی است یا یک لینک جهانی. این عدم تفکیک پذیری باعث می‌شود در کاربردهای Real-time، شناسایی تغییرات ناگهانی در ساختار قدرت با تأخیر یا خطا همراه باشد.

3-5- تفکیک نفوذ محلی و جهانی

با توجه به نقد‌های فوق، این مقاله همگام با پژوهش‌های غلمان، پیشنهاد می‌کند که مفهوم مرکزیت باید از یک کمیت اسکالر به یک مفهوم دو‌بعدی ارتقا یابد. ما نیازمند چارچوبی هستیم که بتواند برای هر گره u، دو مؤلفه متعامد را محاسبه کند:

1. نفوذ محلی (CL – Local Influence): معیاری که نشان دهد گره u چقدر در داخل انجمن‌های خودش (یک یا چند انجمن) محوریت دارد. این معیار باید نسبت به اندازه انجمن نرمال‌سازی شود تا انجمن‌های بزرگ‌تر به طور ناعادلانه بر انجمن‌های کوچک‌تر سایه نندازند.

2. نفوذ جهانی (CG – Global Influence): معیاری که بر اساس تنوع[5] اتصالات سنجیده می‌شود. این شاخص نباید صرفاً تعداد لینک‌های بیرونی را بشمارد، بلکه باید بسنجد که این لینک‌ها چقدر در سطح شبکه پخش شده‌اند.

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

فصل چهارم
روش پیشنهادی

4-1- مقدمه

در بخش‌های پیشین، نشان دادیم که معیارهای کلاسیک مثل درجه، بینابینی و غیره، به دلیل نادیده گرفتن ساختار انجمنی، و معیارهای ماژولار موجود مثل کارهای اولیه غلمان به دلیل نادیده گرفتن ماهیت بازگشتی قدرت، دارای نقص هستند. در این بخش، ما یک مدل ریاضی نوین با عنوان مرکزیت ماژولار بازگشتی پویا (Dynamic Recursive Modular Centrality - DRMC) را توسعه می‌دهیم. این مدل بر مبنای یک فرضیه اصلی بنا شده است و آنهم این است که اهمیت یک گره، حاصل‌ضرب موقعیت استراتژیک آن در ساختار انجمنی (توپولوژی) و کیفیت همسایگان آن (جریان) است.

در ادامه، اجزای این مدل را به صورت گام‌به‌گام فرمول‌بندی می‌کنیم.

4-2- مدلسازی ریاضی فضا و تعاریف پایه

فرض کنید شبکه مورد مطالعه به صورت گراف G = (V, E) مدل‌سازی شود که در آن V مجموعه شامل N گره و E مجموعه شامل M یال است. ماتریس مجاورت شبکه را با A نشان می‌دهیم که در آن Aij=1 اگر ارتباطی وجود داشته باشد و در غیر این صورت صفر است.

برخلاف رویکردهای سنتی که یک افراز[1] سخت برای شبکه در نظر می‌گیرند، ما فرض می‌کنیم شبکه دارای K انجمن همپوشان   است. برای مدل‌سازی ریاضی این همپوشانی، برای هر گره u یک بردار عضویت به شکل زیر تعریف می‌کنیم:

4-3- تجزیه بردار نفوذ محلی

نخستین مؤلفه مدل پیشنهادی، سنجیدن قدرت گره در قلمرو خودی است. ما این مؤلفه را  می‌نامیم. چالش اصلی در اینجا، تفاوت اندازه انجمن‌هاست. یک گره با ۵ اتصال در یک انجمن ۶ نفره، قدرتمندتر از یک گره با ۵ اتصال در یک انجمن ۱۰۰ نفره است. معیارهای کلاسیک این تفاوت نسبی را درک نمی‌کنند.

برای حل این مشکل، ما از فرمول درجه نرمال‌سازی شده درون‌انجمنی استفاده می‌کنیم که مستقیماً از منطق غلمان استخراج شده اما برای مدیریت همپوشانی تعمیم یافته است:

تحلیل فرمول:

• عبارت  نشان می‌دهد گره u چه کسری از همسایگان ممکن در انجمن c را تسخیر کرده است و به آن چگالی اتصال می‌گویند.

• عبارت  نشان می‌دهد از آنجا که گره ممکن است در چندین انجمن عضو باشد، ما میانگین نفوذ او را در تمام انجمن‌هایش محاسبه می‌کنیم.

• بنابراین اگر  به عدد 1 میل کند، گره u یک هاب استانی مطلق است که تمام اعضای گروه‌هایش را می‌شناسد و رهبری می‌کند و در همه انجمن‌هایش مهم‌ترین گره است.

4-4- تجزیه بردار نفوذ جهانی

دومین مؤلفه یعنی ، نشان‌دهنده توانایی گره در ایفای نقش پل ارتباطی بین کلاسترهای متفاوت است. گره‌هایی که این ویژگی را دارند، گلوگاه‌های انتقال اطلاعات هستند. معیارهایی مثل Betweenness برای محاسبه این ویژگی بسیار پرهزینه هستند و از پیچیدگی  هستند.

بنابراین ما برای محاسبه سریع و کارآمد نفوذ جهانی، از مفهوم آنتروپی اتصالات یا ضریب مشارکت[2] استفاده می‌کنیم. این شاخص بر اساس تنوع سیمپسون[3] طراحی شده است:

اثبات رفتار ریاضی:

• حالت ایزوله: اگر تمام اتصالات گره u فقط در یک انجمن باشد (مثلاً c = 1)، آنگاه مقدار کسر برابر ۱ شده و  این یعنی گره هیچ نفوذ جهانی ندارد.

• حالت پل ایده‌آل: اگر اتصالات گره u به طور مساوی بین K انجمن توزیع شده باشد، مقدار داخل سیگما مینیمم شده و  به مقدار حداکثر خود یعنی  نزدیک می‌شود.

این فرمول تضمین می‌کند که ما گره‌هایی را که صرفاً لینک‌های بیرونی زیادی دارند اما همه به یک انجمن خاص می‌روند با گره‌هایی که واقعاً به انجمن‌های متنوع متصل‌اند، اشتباه نگیریم.

4-5- تلفیق بازگشتی

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

این منطق، ما را به سمت استفاده از مدل بازگشتی بوناسیچ و PageRank سوق می‌دهد. ما مدل خطی غلمان را به یک مدل غیرخطی و تکراری تبدیل می‌کنیم. فرض کنیم   امتیاز مرکزیت گره u در تکرار tام باشد. فرمول پیشنهادی ما عبارت است از:

4-5-1- تشریح اجزاء و پارامترها

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

2.     ارزش اکتسابی: بخش دوم، قدرت جریان‌یافته از سمت شبکه است.

·      ما مجموع امتیاز همسایگان یعنی  را محاسبه می‌کنیم مثل PageRank.

·      ضریب فیلترینگ: نکته مهم اینجاست که ما این مجموع را در  ضرب می‌کنیم. این یعنی گره u تنها به اندازه‌ای می‌تواند از قدرت همسایگانش بهره‌مند شود که توانایی توزیع جهانی داشته باشد. یک گره با  (کاملاً محلی)، هیچ قدرتی از شبکه جهانی دریافت نمی‌کند و فقط به قدرت محلی خود متکی است.

3.   پارامتر تنظیم (α): ضریب  نقش یک نوار لغزنده را بازی می‌کند:

• اگر α به 0 میل کند آنگاه مدل بر حفظ انسجام انجمن‌ها و رهبران محلی تمرکز می‌کند.

• اگر α به 1 میل کند آنگاه مدل بر جریان اطلاعات و پل‌های میان‌گروهی تمرکز می‌کند.

4-6- تحلیل همگرایی و پیچیدگی الگوریتم

یرای پیاده‌سازی این مدل، ما از روش Power Iteration Method استفاده می‌کنیم. این فرمول را می‌توان به صورت ماتریسی و به شکل زیر بازنویسی کرد:

که در آن L بردار نفوذ محلی، G ماتریس قطری نفوذ جهانی و W ماتریس انتقال تصادفی است.

4-6-1- پیچیدگی زمانی

1.     محاسبه  و : با فرض استفاده از لیست مجاورت، پیچیدگی محاسبه این بخش برای هر گره برابر  و برای کل شبکه برابر O(M) است (که M برابر تعداد یال‌هاست).

2.     حلقه تکرار: در هر تکرار، یک ضرب ماتریس- بردار اسپارس انجام می‌شود که هزینه آن O(M) است. اگر تعداد تکرارها برای همگرایی برابر T باشد، کل پیچیدگی برابر است با:

از آنجا که T معمولاً عدد کوچکی است (حدود ۲۰ تا ۵۰ برای دقت بالا)، این الگوریتم بسیار سریع‌تر از روش‌هایی مثل Betweenness با پیچیدگی  است و قابلیت اجرا روی شبکه‌های عظیم را دارد.

4-7- مقایسه کیفی با روش‌های پیشین

جدول زیر تمایز نظری روش پیشنهادی ما یعنی (DRMC) با روش‌های گفته شده را نشان می‌دهد:

جدول 4-1: مقایسه روش‌های سابق و روش پیشنهادی

ویژگی

مرکزیت درجه

پیج رنک

ماژولار استاتیک

DRMC

درک ساختار انجمتی

خیر

خیر

بله

بله

هم‌پوشانی انجمن‌ها

خیر

خیر

بله

بله

اثر بازگشتی (قدرت همسایه)

خیر

بله

خیر

بله

تفکیک محلی و جهانی

خیر

خیر

بله

بله

این جدول به وضوح نشان می‌دهد که روش پیشنهادی، مدل ریاضی جامعی است که سعی کرده است تمام ویژگی‌های مثبت روش‌های قبلی را تجمیع کرده است.

فصل پنجم
روش تحلیل و آزمایش

5-1- مقدمه

برای ارزیابی کارایی چارچوب پیشنهادی (DRMC)، ما یک سناریوی تجربی را بر روی داده‌های استاندارد طراحی می‌کنیم تا نشان دهیم چگونه ترکیب ساختار انجمنی و منطق بازگشتی می‌تواند گره‌های پنهان اما حیاتی را آشکار سازد که روش‌های کلاسیک از دیدن آن‌ها عاجز هستند.

5-2- مجموعه داده مورد استفاده

به عنوان اثبات مفهوم، از شبکه اجتماعی باشگاه کاراته زاخاری[1] استفاده می‌شود. این شبکه شامل ۳۴ گره (اعضای باشگاه) و ۷۸ یال (ارتباطات دوستی) است.

• چرا این دیتاست؟ این شبکه دارای یک ساختار انجمنی ذاتی است که پس از اختلاف میان مربی (گره 0) و مدیر (گره ۳3)، باشگاه به دو گروه مجزا تقسیم می‌شود. این ویژگی به ما اجازه می‌دهد تا رفتار معیار DRMC را در شناسایی رهبران محلی و پل‌های ارتباطی بین دو گروه بررسی کنیم.

5-3- سناریوی مقایسه و نتایج مورد انتظار

ما سه معیار را بر روی این شبکه اعمال و ۱۰ گره برتر را استخراج می‌کنیم:

1.     مرکزیت درجه: به عنوان نماینده روش‌های محلی سنتی.

2.     پیج‌رنک: به عنوان نماینده روش‌های بازگشتی.

3.     روش پیشنهادی (DRMC): با تنظیم پارامتر 0.5 = α تعادل میان نفوذ محلی و جهانی را برقرار می‌کند.

5-3-1- تحلیل تطبیقی

• تشخیص رهبران (Hubs): انتظار می‌رود که هر سه روش، گره‌ ۱ یعنی مربی و گره ۳۴ یعنی مدیر را به عنوان مهم‌ترین گره‌ها شناسایی کنند. این گره‌ها هم درجه بالا دارند و هم در مرکز انجمن‌های خود هستند. در اینجا  (نفوذ محلی) در فرمول ما نقش اصلی را بازی می‌کند.

• تشخیص پل‌های ارتباطی(Bridges) - :

نقطه تمایز اصلی در گره‌هایی مانند گره ۹ یا گره ۲۰ ظاهر می‌شود. این گره‌ها ممکن است درجه بالایی نداشته باشند، اما نقش حیاتی در اتصال دو گروه دارند.

• شکست PageRank: پیج‌رنک ممکن است به این گره‌ها امتیاز متوسطی بدهد، چون جریان احتمالاتی در داخل کلاسترهای متراکم حبس می‌شود.

• موفقیت DRMC: در مدل پیشنهادی ما، این گره‌ها دارای نفوذ جهانی یعنی  بالایی هستند. فرمول بازگشتی ما، وزن همسایگان قدرتمند آن‌ها را در ضریب  ضرب می‌کند. بنابراین، گره‌ای که پلی میان دو رهبر قدرتمند باشد، جهش رتبه قابل توجهی در DRMC خواهد داشت که در روش‌های دیگر دیده نمی‌شود.

5-4- تحلیل نتایج حاصل از اجرا

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

در این آزمایش، ۱۰ گره برتر شبکه بر اساس سه معیار مرکزیت درجه، PageRank و DRMC با پارامتر 0.5 = α برای ایجاد تعادل رتبه‌بندی شده‌اند.

نتایج کمی حاصل از این مقایسه در جدول زیر ارائه شده است:

جدول 5-1: مقایسه امتیازدهی روش‌های نامبرده شده

رتبه

شناسه گره

مرکزیت درجه

PageRank

DRMC

نفوذ محلی

نفوذ جهانی

1

0

0.48

0.088

0.083

0.85

0.59

2

33

0.51

0.096

0.080

0.87

0.30

3

1

0.27

0.057

0.069

0.75

0.49

4

32

0.36

0.075

0.062

0.68

0.15

5

2

0.30

0.062

0.058

0.62

0.58

6

3

0.18

0.037

0.056

0.62

0.27

7

5

0.12

0.033

0.050

0.57

0.00

8

6

0.12

0.031

0.050

0.57

0.00

9

10

0.09

0.020

0.038

0.42

0.00

10

4

0.09

0.020

0.038

0.42

0.00

همان‌طور که در جدول بالا مشاهده می‌شود، اگرچه همپوشانی کلی میان گره‌های برتر در سه روش وجود دارد، اما جابجایی‌های معناداری در رتبه‌بندی رخ داده است که برتری مدل DRMC را در شناسایی موقعیت‌های استراتژیک اثبات می‌کند.

الف) تقابل کمیت و کیفیت (تحلیل گره ۳۳ در برابر گره ۰):

مهم‌ترین یافته این آزمایش در دو ردیف اول جدول نهفته است.

• در دیدگاه کلاسیک معیارهای درجه و پیج‌رنک، گره ۳۳ (مدیر) را به عنوان مهم‌ترین گره شناسایی کرده‌اند (با درجه ۰.۵۱). دلیل این امر، تعداد بالای اتصالات مستقیم اوست. اما با نگاهی به ستون نفوذ جهانی درمی‌یابیم که نفوذ جهانی این گره تنها ۰.۳۰ است؛ به این معنا که اکثر اتصالات او محدود به انجمن خودش است و او نقش یک هاب محلی را بازی می‌کند.

• در دیدگاه پیشنهادی یعنی DRMC در مقابل، گره ۰ (مربی) اگرچه درجه کمتری دارد (۰.۴۸)، اما دارای نفوذ جهانی بسیار بالاتری ۰.۵۹ است. این یعنی اتصالات او بین انجمن‌های مختلف توزیع شده است. مدل پیشنهادی ما با تشخیص این ویژگی و اعمال اثر بازگشتی، گره ۰ را به رتبه نخست ارتقا داده است. این نتیجه نشان می‌دهد که DRMC برای گره‌هایی که نقش پل ارتباطی را دارند و جریان اطلاعات را بین گروه‌ها ممکن می‌سازند، ارزش بیشتری قائل است.

ب) شناسایی ظرفیت‌های پنهان (گره ۲):

گره ۲ مثال بارز دیگری از دقت مدل است. این گره درجه نسبتاً پایینی دارد (۰.۳۰) و در پیج‌رنک نیز امتیاز متوسطی گرفته است. اما به دلیل اینکه نفوذ جهانی آن بسیار بالاست ۰.۵۸، مدل DRMC جایگاه آن را تثبیت کرده است. این نشان می‌دهد گره‌هایی که شاید مشهور نباشند (درجه پایین) اما بانفوذ هستند (اتصال‌دهنده گروه‌ها)، در مدل ما بهتر دیده می‌شوند.

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

5-5- تحلیل حساسیت پارامتر α

یکی از ویژگی‌های برجسته مدل ما، قابلیت تنظیم‌پذیری با پارامتر α است

• در کاربردهایی که هدف حفظ انسجام داخلی است مثل تیم‌سازی، مقدار α به 0 میل داده می‌شود تا وزن پارامتر CL بالا رود.

• در کاربردهایی که هدف انتشار سریع اطلاعات یا «یروس‌شناسی است، مقدار α به 1 میل داده می‌شود تا گره‌هایی با CG بالا که توانایی پخش بین گروه‌ها را دارند، در صدر لیست قرار گیرند.

فصل ششم
روش نتیجه‌گیری و پیشنهادات

6-1- مقدمه

مسئله شناسایی گره‌های مرکزی در شبکه‌های پیچیده، همواره با چالش تعریف اهمیت روبرو بوده است. در این پژوهش، ما سیر تکاملی این مفهوم را از معیارهای ایستا و ساختار کور فریمن به سوی مدل‌های بازگشتی بوناسیچ و پیج‌رنک مرور کردیم. استدلال اصلی ما این بود که رویکردهای موجود، یا ساختار مزوسکوپیک انجمن‌ها را نادیده می‌گیرند و یا مانند کارهای اولیه در مرکزیت ماژولار از دینامیک بازگشتی جریان غافل‌اند.

مقاله حاضر با معرفی چارچوب مرکزیت ماژولار بازگشتی پویا، یک راهکار ترکیبی ارائه داد. این مدل با تفکیک نفوذ گره به دو مؤلفه متعامد محلی و جهانی و تزریق آن‌ها در یک فرآیند تکراری مشابه PageRank، توانست:

1.     ماهیت همپوشان انجمن‌ها را در فرمولاسیون ریاضی لحاظ کند.

2.     گره‌هایی را شناسایی کند که شاید درجه بالایی نداشته باشند، اما به دلیل اتصال استراتژیک به انجمن‌های متنوع، شاه‌راه‌های جریان اطلاعات محسوب می‌شوند.

6-2- محدودیت‌ها و مسیرهای پژوهشی آینده

اگرچه مدل پیشنهادی گامی رو به جلو محسوب می‌شود، اما مسیرهای نویی را برای پژوهش‌های آینده می‌گشاید که با توجه به فایل موضوعات پیشنهادی، می‌توانند شامل موارد زیر باشند:

1. یادگیری پارامتر α با هوش مصنوعی: در مدل فعلی، α یک عدد ثابت دستی است. در کارهای آتی می‌توان با استفاده از شبکه‌های عصبی گراف (GNN)، مقدار بهینه α را برای هر شبکه به صورت خودکار و بر اساس ویژگی‌های توپولوژیک یاد گرفت.

2. شبکه‌های زمانی: فرمول فعلی برای شبکه‌های ایستا (یا اسنپ‌شات‌های ثابت) طراحی شده است. تعمیم این فرمول برای شبکه‌هایی که یال‌های آن دارای برچسب زمانی (t) هستند، می‌تواند پروژه‌ای چالش‌برانگیز و نوآورانه باشد.

3. پیاده‌سازی مقیاس‌پذیر: برای گراف‌های میلیاردی (مثل وب یا توییتر)، محاسبه ضریب مشارکت می‌تواند پرهزینه باشد. استفاده از الگوریتم‌های تقریبی یا پردازش توزیع‌شده Spark GraphX برای پیاده‌سازی این مدل پیشنهاد می‌شود.

فصل هفتم
منابع

[1] L. C. Freeman, "Centrality in social networks: Conceptual clarification," Social Networks, vol. 1, no. 3, pp. 215-239, 1979.

[2] P. Bonacich, "Power and Centrality: A Family of Measures," American Journal of Sociology, vol. 92, no. 5, pp. 1170-1182, 1987.

[3] L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web," Technical Report, Stanford InfoLab, 1998.

[4] Z. Ghalmane, C. Cherifi, H. Cherifi, and M. El Hassouni, "Centrality in Complex Networks with Overlapping Community Structure," Scientific Reports, vol. 9, no. 1, p. 10133, 2019.