چگونه الگوریتم‌های بینابینی، نزدیکی و بردار ویژه، قدرت را در یک شبکه تعریف می‌کنند

در ژانویه ۲۰۲۶، پژوهشگرانی که در arXiv مقاله منتشر کردند، یک چارچوب یکپارچه را برای ساماندهی به بیش از ۱۰۰ معیار رقیب مرکزیت شبکه پیشنهاد دادند؛ معیارهایی که در حال حاضر برای نقشه‌برداری از همه‌چیز، از شبکه‌های برق گرفته تا نفوذ اجتماعی، استفاده می‌شوند. این پیش‌چاپ به یک ابهام ریاضیاتی دیرینه می‌پردازد: تعریف اینکه چه چیزی یک گره منفرد را مهم می‌سازد. در گرافی با ۱۰ میلیون نقطه متصل به هم، بحرانی‌ترین گره به‌ندرت گرهی است که بیشترین اتصالات مستقیم را دارد.[1]

چالش کمّی‌سازی مزیت ساختاری به فرمول‌بندی مفهوم بینابینی توسط جامعه‌شناس، لینتون فریمن (Linton Freeman) در سال ۱۹۷۷ بازمی‌گردد، اما گراف‌های محاسباتی مدرن این تعاریف را بسط داده‌اند. بر اساس مستندات فنی Memgraph، «مرکزیت بینابینی گره‌هایی را شناسایی می‌کند که به عنوان پل از یک بخش گراف به بخش دیگر عمل می‌کنند.» یک گره ممکن است تنها دو اتصال داشته باشد، اما اگر همان دو اتصال تنها حلقه ارتباطی میان دو خوشه عظیم و منزوی باشند، آن گره جریان کل شبکه را کنترل می‌کند.[3]

اندازه‌گیری این کنترل نیازمند محاسبه کوتاه‌ترین مسیرها میان تمام جفت‌گره‌های ممکن در شبکه است. اگر یک گره خاص در درصد بالایی از این کوتاه‌ترین مسیرها قرار گیرد، امتیاز بینابینی آن افزایش می‌یابد. با این حال، این محاسبه دقیق برای گراف‌های متراکم و بدون وزن دارای پیچیدگی زمانی O(V³) است؛ به این معنا که با افزایش تعداد رأس‌ها، زمان محاسبات به توان سه می‌رسد.[4]

برای شبکه‌هایی با بیش از ۱۰۰٬۰۰۰ گره، محاسبه دقیق بینابینی از نظر محاسباتی غیرممکن می‌شود. کتابخانه NetworkX، که یک کتابخانه استاندارد پایتون برای تحلیل گراف است، به‌طور پیش‌فرض از الگوریتم براندس (Brandes) استفاده می‌کند که این پیچیدگی را برای گراف‌های بدون وزن به O(V × E) کاهش می‌دهد. حتی با این بهینه‌سازی، محاسبه بینابینی روی یک گراف ۱۰ میلیون گرهی نیازمند تکنیک‌های تقریب است تا نتایج را در کمتر از سه ثانیه برگرداند.[3][4]

زمانی که هدف از کنترل جریان به پخش سریع اطلاعات تغییر می‌کند، مرکزیت نزدیکی دریچه ریاضیاتی متفاوتی را ارائه می‌دهد. معیار نزدیکی، معکوس مجموع طول کوتاه‌ترین مسیرها میان یک گره و تمام گره‌های دیگر در گراف را محاسبه می‌کند. امتیاز بالای نزدیکی نشان می‌دهد که یک گره می‌تواند با کمترین گام‌های ممکن به تمام بخش‌های دیگر شبکه دسترسی پیدا کند.[4][5]

این معیار در اپیدمیولوژی و لجستیک بسیار حیاتی است. در مطالعه‌ای که در آوریل ۲۰۲۳ در MDPI منتشر شد و شبکه‌های گیاهی ۵۴ گونه را تحلیل می‌کرد، پژوهشگران از مرکزیت نزدیکی برای شناسایی گره‌های بیولوژیکی که منابع را با بیشترین کارایی توزیع می‌کردند، بهره بردند. این الگوریتم فرض می‌کند که اطلاعات یا منابع به‌طور همزمان در امتداد تمام کوتاه‌ترین مسیرها جریان می‌یابند، که آن را برای مدل‌سازی گسترش ویروسی یا دینامیک سیالات ایده‌آل می‌سازد.[2]

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

مرکزیت بردار ویژه مشکل متفاوتی را حل می‌کند: کیفیت اتصالات به جای کمیت صرف آن‌ها. این الگوریتم که توسط فیلیپ بوناسیچ (Phillip Bonacich) در سال ۱۹۸۷ پیشنهاد شد، بر اساس این اصل به تمام گره‌ها امتیازات نسبی اختصاص می‌دهد که اتصال به گره‌های با امتیاز بالا، بیشتر از اتصال برابر به گره‌های با امتیاز پایین، در امتیاز گره مورد نظر نقش دارد.[1][5]

الگوریتم اولیه PageRank گوگل، نوع معروفی از مرکزیت بردار ویژه است که یک ضریب میرایی — معمولاً روی ۰٫۸۵ تنظیم می‌شود — را برای مدل‌سازی احتمال اینکه یک کاربر تصادفی به جای شروع مجدد، به کلیک روی لینک‌ها ادامه دهد، معرفی می‌کند. کتابخانه علم داده گراف Neo4j از روش تکرار توان برای محاسبه این امتیازات در مقیاس بزرگ استفاده می‌کند و ارزش هر گره را بر اساس همسایگانش به‌روزرسانی می‌کند تا زمانی که امتیازات همگرا شوند.[5]

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

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

مرز بعدی در تحلیل شبکه، فراتر از توپولوژی ایستا حرکت می‌کند. از آنجا که گراف‌ها در زمان واقعی به‌روزرسانی می‌شوند — با یال‌هایی که در کسری از میلی‌ثانیه شکل می‌گیرند و از بین می‌روند — الگوریتم‌ها باید مرکزیت زمانی را بدون محاسبه مجدد کل شبکه از ابتدا، محاسبه کنند. چالش ریاضیاتی دیگر تنها تعریف اهمیت نیست، بلکه ردیابی آن در حین حرکت است.[6]