محاسبه انواع مرکزیت در گراف مترو

در این مثال قصد داریم تا گراف متروی شهر تایپه پایتخت کشور تایوان را مورد بررسی قرار دهیم. هر ایستگاه مترو را به عنوان یک گره (Node) در گراف در نظر می گیریم. ارتباط بین ایستگاه ها از طریق یال (Edge) به دست می آید.

برای شناسایی گره های مهم در گراف معیارهای مختلفی وجود دارد. معیارdegree centrality (DC) تعداد اتصالات (degree) هر ایستگاه را نمایش می دهد. معیار closeness centrality (CC) یکی از شاخص ها برای شناسایی گره های مهم در شبکه هست و هر گره از نظر میانگین فاصله با سایر گره ها ارزیابی می شود و طبق این فرض کار می کند که گره مهم کمترین فاصله را با سایر گره ها در گراف را دارد.

معیار بعدی برای ارزیابی گره های مهم betweenness centrality (BC) است. در این شاخص گره ها از نظر میزان تکرار در مسیر سایر گره ها ارزیابی می شوند. به این ترتیب گره ای مهم به شمار می آید که به عنوان واسطه ارتباط بین سایر گره ها قرار می گیرد و طبق معادله زیر به محاسبه می شود:

معیارهای Graph Fourier transform centrality (GFT-C) وgraph regularization centrality (GRC) براساس تئوری پردازش سیگنال گراف توسعه داده شده است.
روش های دیگری برای سنجش گره های مهم در گراف (مثل eigenvector centrality (EC)) وجود دارد که براساس شرایط مساله و رفتار شبکه می توان از آنها استفاده کرد. در ادامه معیارهای مرکزیت ذکر شده در گراف متروی شهر تایپه محاسبه شده است. رنگ های تیره تر نمایش دهنده مرکزیت بالاتر گره است.