کاربر تحلیل شبکه در منابع انسانی - قسمت اول

مفهوم نمودار تو قرن ۱۸ میلادی به وجود اومد، وقتی یه ریاضی‌دان سعی کرد یه مسئله رو به صورت تصویری حل کنه. اینکه نمودار رو به این شکل تصور کنیم منطقیه، چون شهودی و راحت برای فهمیدن و انتقال دادن به دیگرانِ و تو خیلی از موارد، یه شکل به ما کمک می‌کنه تا بهتر با مشکلی که داریم حل می‌کنیم، روبرو بشیم. اما شکل کشیدن فقط یه راه برای نمایش یه نموداره و خیلی هم مقیاس‌پذیر نیست. کشیدن یه شکل برای یه نمودار با چندتا گره و یال (مثل مسئله پل‌های کنيگسبرگ ما) راحته، اما اگه مسئله‌ی ما شامل هزارتا گره و میلیون‌ها یال باشه چی؟ بیشتر نمودارهای جالبی که می‌خوایم مطالعه کنیم، ماهیت پیچیده‌تری دارن و صدها یا هزارها گره و خیلی بیشتر یال دارن، و شکل کشیدن از این نمودارهای بزرگ همیشه تو حل کردن مشکلات به ما کمک نمی‌کنه.

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

تئوری مقدماتی گراف‌ها

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

تعریف کلی گراف

یک گراف G از دو مجموعه تشکیل شده است. مجموعه اول V مجموعه رأس‌ها (یا گره‌ها) نامیده می‌شود. مجموعه دوم E مجموعه یال‌ها نامیده می‌شود و از زوج‌های مرتب از اعضای V تشکیل شده است. با توجه به اینکه یک گراف از این دو مجموعه تشکیل شده، اغلب گراف را به صورت G = (V, E) نمایش می‌دهیم. اگر دو رأس به صورت یک زوج مرتب در E ظاهر شوند، آنگاه گفته می‌شود که آن رأس‌ها همسایه یا متصل هستند.

بیایید برای درک بهتر این تعریف از یه مثال استفاده کنیم. شکل زیر نمودار یک گراف G کار است که چهار رأس دارد که نشان‌دهنده‌ی چهار نفر هستند. یک یال، دو رأس را وصل می‌کند در صورتی که و فقط در صورتی که آن دو نفر با هم کار کرده باشند.

مجموعه رأس‌های ما V برای گراف Gکار است: V = {David, Suraya, Jane, Zubin}

مجموعه‌ی یال‌های ما E برای گراف Gکار باید به صورت زوج‌های مرتب از اعضای مجموعه رأس‌ها V نمایش داده بشه. راه‌های زیادی برای نمایش این وجود داره. یه مثال برای نمایش مجموعه یال‌ها با نمادگذاری رسمی تئوری مجموعه‌هاست:

E = {{David, Zubin}, {David, Suraya}, {David, Jane}, {Jane, Zubin}, {Jane,Suraya}}

همچنین می‌تونیم از یه نمادگذاری جایگزین استفاده کنیم:

E = {David ⟷ Zubin, David ⟷ Suraya, David ⟷ Jane, Jane ⟷ Zubin, Jane ⟷ Suraya}

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

رابطه ای که ما با یال‌ها در گراف Gکار مدل‌سازی می‌کنیم، ماهیت متقابل داره. اگر دیوید با زوبین کار کرده باشه، پس اتوماتیک نتیجه می‌گیریم که زوبین هم با دیوید کار کرده. بنابراین نیازی به جهت‌دار بودن یال‌های Gکار نیست. به چنین گرافی، گراف بدون جهت (undirected graph) می‌گیم. تو یه گراف بدون جهت، ترتیب گره‌ها تو هر زوج از مجموعه یال‌ها E مهم نیست. مثلا David⟷ Zubin هم‌ معنیه با Zubin ⟷ David.

گرافی که جهت مهمه، گراف جهت‌دار (directed graph) نامیده می‌شه. به‌عنوان مثال، بیایید یه گراف Gمدیریت رو با همون مجموعه رأس‌های چهار نفره در نظر بگیریم، اما یالی بین دو نفر وجود داره در صورتی که نفر اول، مدیر نفر دوم باشه، همونطور که تو شکل زیر می‌بینیم.

انواع گراف ها

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

یک گراف چندگانه (multigraph) گرافی‌ست که می‌تونه بین دو رأسِ یکسان، چندین یال وجود داشته باشه. معمولا این اتفاق می‌افته چون یال‌ها انواع مختلفی از روابط رو تعریف می‌کنن. مسیرهای مسافرت، مثال‌های رایج گراف‌های چندگانه هستن، جایی که هر یال نماینده‌ی یه شرکت حمل‌ونقل متفاوته. برای مثال، شکل زیر یه گراف از پروازهای بین فرودگاه‌های سان‌فرانسیسکو (SFO)، فیلادلفیا (PHL) و توسان (TUS) بر اساس داده‌های دسامبر ۲۰۱۰ است. این گراف روی یه نقشه از ایالات متحده قرار داده شده. مسیر فیلادلفیا به توسان مسیر رایجی نیست و فقط توسط یه شرکت حمل‌ونقل در یه جهت ارائه می‌شه، در حالی که چندین شرکت حمل‌ونقل در هر دو جهت بین فیلادلفیا و سان‌فرانسیسکو و بین سان‌فرانسیسکو و توسان فعالیت می‌کنن.

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

تو خیلی از تحلیل‌های واقعی، با گراف‌های چندگانه سر و کار داریم چون این گراف‌ها برای ثبت کردن انواع مختلفی از روابط بین موجودیت‌های مختلف ساخته می‌شن. برای مثال، یه گراف از یه شبکه‌ی سازمانی ممکنه رأس‌هایی داشته باشه که نشون‌دهنده‌ی افراد، واحدهای سازمانی و حوزه‌های دانش باشن. انواع مختلفی از روابط می‌تونن بین افراد وجود داشته باشن (مثل «باهاش کار کرده»، «مدیرشه»، «باهاش مقاله منتشر کرده»)، بین افراد و واحدهای سازمانی (مثل «عضو» یا «رهبر»)، بین افراد و حوزه‌های دانش (مثل «مرتبط با» یا «کارشناس تو») و انواع دیگه از ارتباطات.

‏گراف‌های با خود-حلقه (pseudographs) گراف‌هایی هستن که به رأس‌ها اجازه می‌دن به خودشون وصل بشن. گراف‌های با خود-حلقه زمانی به وجود میان که بعضی یال‌ها، روابطی رو بین همون رأس نشون بدن. برای مثال، فرض کنید یه گراف Gقهوه داریم که همون چهار شخصیت از Gکار در بخش قبلی رو داره و نشون می‌ده که چه کسی برای چه کسی قهوه می‌خره. اگه دیوید بره برای زوبین قهوه بخره، احتمالا برای خودش هم یه قهوه می‌خره. بنابراین، می‌تونید مجموعه یال‌های زیر رو انتظار داشته باشید:

E = {David ⟶ Zubin, David ⟶ David}

یه مثال از جایی که گراف‌های با خود-حلقه به وفور پیدا می‌شن، تحلیل تراکنش‌های مالیه. فرض کنید یه گراف با سه رأس داریم که نماینده‌ی سه شرکت A، B و C هستن، جایی که یه یال نشون‌دهنده‌ی یه انتقال بانکی از یه شرکت به یه شرکت دیگه تو یه روز مشخصه. اگه یه شرکتی چندتا حساب بانکی داشته باشه، ممکنه همچین گرافی شبیه‌ی شکل زیر به نظر برسه. یالی که یه رأس رو به خودش وصل می‌کنه معمولا حلقه (loop) نامیده می‌شه.

یک گراف کامل (complete graph) گرافی‌ست که همه‌ی رأس‌ها با یه یال به هم وصل شدن. بذارید به چهار شخصیت تو Gکار از بخش قبلی برگردیم. ممکنه متوجه بشید که فقط یه زوج از این شخصیت‌ها با هم کار نکردن. فرض کنیم یه ماه بعد برمی‌گردیم و گرافمون رو به‌روز می‌کنیم و به نظر می‌رسه که زوبین و سورایا حالا با هم کار کردن. این یعنی گراف ما به یه گراف کامل تبدیل می‌شه، همونطور که تو شکل زیر نمایش داده شده.

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

‏گراف‌های دو-نگاره (bipartite graphs) گراف‌هایی هستن که دو مجموعه جدا از هم از رأس‌ها دارن، به طوری که هیچ دو رأسی تو همون مجموعه به هم وصل نمی‌شن. تصور کنید که بخواهیم سه فرد جدید از یه بخش دیگه رو به رأس‌های Gکار اضافه کنیم، و روابطمون رو دوباره تعریف کنیم تا یه یال به این معنی باشه که دو فرد با هم از بخش‌های مختلف کار کردن. بعد، گراف جدید، Gجدید ممکنه شبیه‌ی شکل زیر به نظر برسه، با مجموعه‌های متمایز از رأس‌ها که نشون‌دهنده‌ی افراد تو بخش‌های مختلف هستن.

با گسترش دادن ایده‌ی گراف‌های دو-نگاره، گراف‌های k-نگاره (k-partite graphs) گراف‌هایی هستن که k مجموعه جدا از هم از رأس‌ها دارن، به طوری که هیچ دو رأسی تو همون مجموعه به هم وصل نمی‌شن.

درخت‌ها (Trees) هم می‌تونن به عنوان مجموعه‌ای از رأس‌ها که با یال به هم وصل شدن، دیده بشن، پس درخت‌ها هم نوعی گراف هستن. برای مثال، گراف Gمدیریت ما تو بخش قبلی یه درخت به حساب میاد چون یه ساختار مدیریت سلسله‌مراتبی بین افراد رو نشون می‌ده. برای اینکه یه گراف به عنوان درخت در نظر گرفته بشه، باید دقیقا یه مسیر بین هر جفت از رأس‌ها وجود داشته باشه، حتی اگه اون رو به صورت یه گراف بدون جهت در نظر بگیریم.

معمولا درخت‌ها گراف‌هایی هستن که یال‌هاشون یه نوع رابطه‌ی سلسله‌مراتبی یا تو در تو رو نشون می‌دن مثل شکل زیر