Skip to content
بازگشت به نتایج جست‌وجو

مرکزیت بردار ویژه

معرفی‌شده توسط
Bonacich, P.
سال
1972
نوع
Centrality measure
خانواده
Network science

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

مرکزیت بردار ویژه، که در سال ۱۹۷۲ توسط بوناکیک معرفی شد، نفوذ یک گره را با در نظر گرفتن نه تنها تعداد همسایگانش، بلکه میزان نفوذ آن همسایگان اندازه‌گیری می‌کند. گره‌ای که به گره‌های پرنفوذ دیگر متصل است، امتیاز بالایی کسب می‌کند و این امر آن را به معیاری بازگشتی و آگاه از کل شبکه برای اهمیت ساختاری تبدیل می‌کند.

شهود پشت روش

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

تاریخ

مرکزیت بردار ویژه توسط فیلیپ بوناکیک در مقاله‌ای در سال ۱۹۷۲ در مورد رویکردهای فاکتورگیری و وزن‌دهی به امتیازات وضعیت، رسمی شد و پایه نظری برای معیارهای مرکزیت مبتنی بر اعتبار ایجاد کرد. این ایده که اهمیت یک گره متناسب با مجموع اهمیت همسایگانش است، در مفهوم جامعه‌شناختی وضعیت پیش از بوناکیک وجود داشت، اما فرمول‌بندی جبری او آن را قابل محاسبه کرد. این معیار به طور گسترده در تحلیل شبکه‌های اجتماعی و سپس در کتاب‌سنجی و تحلیل گراف وب پذیرفته شد و مستقیماً الهام‌بخش الگوریتم PageRank گوگل (۱۹۹۸) شد که یک ضریب میرایی برای مدیریت گراف‌های جهت‌دار و ناپیوسته اضافه می‌کند.

چه زمانی استفاده شود

هنگامی که می‌خواهید گره‌هایی را شناسایی کنید که نه تنها به دلیل داشتن اتصالات زیاد، بلکه به دلیل قرار گرفتن در مناطق متراکم و با وضعیت بالا در شبکه، نفوذ دارند، از مرکزیت بردار ویژه استفاده کنید — که معمولاً در شبکه‌های استنادی، تحقیقات نفوذ اجتماعی و تحلیل اعتبار سازمانی یافت می‌شود. این روش برای شبکه‌های بدون جهت یا جهت‌دار متقارن که مفهوم تقویت متقابل معنای اساسی دارد، مناسب است. از آن در گراف‌های ناپیوسته (امتیازات برای مولفه‌های مجزا تعریف نشده باقی می‌مانند)، گراف‌های جهت‌دار بدون دور (بردار ویژه پیشرو تخریب می‌شود) یا زمانی که اتصال محلی به جای اعتبار جهانی، سوال تحقیق است، اجتناب کنید. برای شبکه‌های جهت‌دار با نفوذ نامتقارن، PageRank معمولاً ترجیح داده می‌شود.

محدودیت‌ها و ملاحظات

  • در گراف‌های ناپیوسته و گراف‌های جهت‌دار بدون دور تعریف نشده یا تخریب شده است، که در آن‌ها بردار ویژه پیشرو امتیازات معناداری را برای همه گره‌ها به دست نمی‌دهد.
  • به تراکم و ساختار شبکه حساس است: در شبکه‌های بسیار پراکنده تقریباً همه گره‌ها به امتیازات نزدیک به صفر فرو می‌ریزند به جز یک هاب کوچک.
  • طول مسیر یا نقش‌های پل‌زننده را در نظر نمی‌گیرد؛ گره‌ای که دو خوشه متراکم را به هم متصل می‌کند ممکن است علی‌رغم اهمیت ساختاری خود، امتیاز پایینی کسب کند.
  • برای شبکه‌های جهت‌دار نامتقارن، این معیار نیاز به تطبیق دارد (مانند PageRank)، و کاربرد خام آن می‌تواند گمراه‌کننده باشد.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

  • شناسایی اعتبار و نفوذ در شبکه‌های استنادی دانشگاهی و گراف‌های هم‌نویسندگی.
  • نقشه‌برداری ساختارهای قدرت و رهبران نظر در شبکه‌های سازمانی و سیاسی.
  • شناسایی گره‌های هاب در شبکه‌های تعامل پروتئین و تنظیم ژنی بیولوژیکی.
  • رتبه‌بندی صفحات وب و اسناد بر اساس اقتدار ساختاری (پایه PageRank).
  • تحلیل انتشار نفوذ و منتشرکنندگان کلیدی در شبکه‌های رسانه‌های اجتماعی.
  • ارزیابی سلسله مراتب وضعیت در مطالعات شبکه‌های جامعه‌سنجی و دوستی.

چگونه کار می‌کند

چگونه کار می‌کند

1

شبکه به صورت ماتریس مجاورت A نمایش داده می‌شود، که در آن درایه A_ij برابر با ۱ (یا وزن یال برای شبکه‌های وزن‌دار) است اگر گره‌های i و j به هم متصل باشند، و در غیر این صورت صفر است. این ماتریس کل توپولوژی اتصالات را که مرکزیت بر روی آن‌ها محاسبه می‌شود، رمزگذاری می‌کند.

2

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

فرمول
\mathbf{A}\mathbf{x} = \lambda_{\max}\mathbf{x}
3

به هر گره، مؤلفه متناظر بردار ویژه پیشرو به عنوان امتیاز مرکزیت آن اختصاص داده می‌شود. این امتیاز شرط نقطه ثابت را برآورده می‌کند: امتیاز گره برابر است با (۱/λ_max) ضربدر مجموع امتیازات همسایگانش، بنابراین گره‌های با امتیاز بالا به طور بازگشتی امتیاز همسایگان خود را بالا می‌برند.

فرمول
x_i = \frac{1}{\lambda_{\max}} \sum_{j \in N(i)} x_j
4

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

دام‌های رایج

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

پرسش‌های متداول

مرکزیت بردار ویژه چگونه با مرکزیت درجه متفاوت است؟

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

چرا مرکزیت بردار ویژه در گراف‌های جهت‌دار بدون دور شکست می‌خورد؟

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

آیا می‌توانم از مرکزیت بردار ویژه در شبکه‌های وزن‌دار استفاده کنم؟

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

چگونه باید مرکزیت بردار ویژه را در یک مقاله گزارش کنم؟

امتیازات مرکزیت بردار ویژه نرمال‌شده (حداکثر = ۱) را گزارش دهید، نرم‌افزار و نسخه مورد استفاده را مشخص کنید (مانند NetworkX، igraph)، بیان کنید که آیا شبکه جهت‌دار بوده یا بدون جهت، و تأیید کنید که اگر گراف ناپیوسته بود، بزرگترین مولفه متصل استفاده شده است. یک تجسم که گره‌ها را بر اساس امتیازشان رنگ‌آمیزی یا اندازه‌بندی می‌کند، به تفسیر کمک زیادی می‌کند.

رابطه بین مرکزیت بردار ویژه و PageRank چیست؟

PageRank یک تعمیم جهت‌دار و میرا شده از مرکزیت بردار ویژه است. این الگوریتم یک ضریب میرایی (معمولاً ۰.۸۵) و یک احتمال تله‌پورت یکنواخت را برای مدیریت گراف‌های ناپیوسته و جهت‌دار اضافه می‌کند. برای شبکه‌های بدون جهت و متصل، PageRank و مرکزیت بردار ویژه رتبه‌بندی‌های تقریباً یکسانی تولید می‌کنند.

روش‌های مرتبط

منابع

  1. Bonacich, P. (1972). Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1), 113–120.

    باز کردن مرجع DOI
    کپی شد.
  2. Eigenvector centrality. Wikipedia.

    باز کردن مرجع انتشار
    کپی شد.