یکی از اولین کار های که نتورک ساینس ها در پروسه کاری خود انجام میدهند آنالیز اولیه نتورک و به دست آوردن بعضی از اطلاعات اولیه از نتورک خود هست .
من سعی میکنم با آنالیز های بسیار ساده حرکت بکنیم و بعد سعی میکنم نسبت به نوع نتورک آنالیز های اون نوع گراف رو معرفی بکنم.
انواع نتورک ها
اگر بخواهیم نتورک ها را دسته بندی بکنیم تقریبا به سه دسته تقسیم میشن اما خب اگر به چشم ریاضی به موضوع نگاه بکنیم میتونیم عمیقتر هم بشیم و تعداد خیلی بیشتر میشه اما به سه دسته نگاه میکنیم برای ساده نگه داشتن مطلب.
گراف Undirected
این نوع گراف به گراف هایی گفته میشود که که بین دو نود ارتباط دارای جهت نیست و فقط دیتا هست مثل ارتباط در لینکدن شما برای دوستانتان تقاضای دوستی و ارتباط میفرستید و بعد از قبولی توسط آنها ارتباط برقرار خواهد شد .
گراف Directed
در این نوع شبکه ارتباط ها دارای جهت هستند و ارتباط یک نود با نود دیگر معنای داشتن ارتباط معکوس نیست . مثالی از این نوع ارتباط اینستاگرام میتواند باشد یا نوعی از معرفی نقشه و ترافیک و مترو و ...
گراف weighted
به شخصه من عاشق این نوع گراف ها هستم . این نوع گراف ها در هر ارتباط یا edge دارای مقداری عددی هست . برای مثال گراف های ارتباط بین فرودگاه ها . هر پرواز دارای فاصله ای هست که بین دو فرودگاه کشیده میشود .
لود کردن دیتاست
توجه : کد های این آموزش در گیتهاب به صورت کامل تر هستند :
@SeyedHosseinTafakh/network_analysis_tutorial_1
سرفصل هر اموزش اسم فایل نوت بوک مورد نظر میباشد.
در مرحله اول سعی میکنیم از گراف های موجود در کتبخانه networkx استفاده کنیم و اطلاعات کلی گراف مورد نظر را بگیریم
import networkx as nx myGraph = nx.karate_club_graph() print(nx.info(myGraph))
Name: Zachary's Karate Club Type: Graph Number of nodes: 34 Number of edges: 78 Average degree: 4.5882
در مثال بالا که اطلاعات اولیه گراف را پرینت گرفتیم در اول اسم گراف
بعد نوع گراف که در اینجا گرافی undirected هست
بعد تعداد نود ها
بعد تعداد ارتباط ها یا ادج ها
بعد هم متوسط ارتباط نود ها با هم مشخص میشود که میتواند نوعی نشان دهنده تراکم باشد.
کشیدن گراف
اولین کاری که شاید دوست داشته باشید انجام بدهید کشیدن این گراف باشد چرا که به نظر من هیچ چیز مثل دیدن اطلاعات و پلات کردن این اطلاعات به پروسه انالیز نمیتواند کمک کند
import matplotlib.pyplot as plt myGraph = nx.karate_club_graph() nx.draw(myGraph,with_labels=True)
یا میتوان همین گراف را به صورت دایره ای کشید :
nx.draw_circular(myGraph,with_labels=True)
بعد از دیدن آنکه با چه نوع گرافی و با چند دیتاست سر و کله میزنیم شاید بهتر باشد بیشتر برویم سمت اعداد و ارقام .
به فارسی توزیع درجه یا اسم بهتر آن degree distribution در واقع دو کار را انجام میدهد .
1- نشان میدهد که ارتباط بین نود ها در شبکه چگونه توزیع شده یا به عبارتی نود ها بیشتر دارای چند ارتباط با همسایگان خود هستند
2- نشان دهنده توزیع احتمال بین نود های دیگر در شبکه
در تصویری که میبینید در نگاه اول متوجه میشویم که چند تعداد از نود ها دارای تعداد زیادی ارتباط با نود های همسایه خود ندارند ( به عدد 8 تا 16 دقت کنید ) اما نود هایی دارای تعداد همسایه های 2 تا 5 هستند که نشان دهنده متمایل بودن شبکه به نوع centralized است این نوع شبکه دارای رهبر هایی هست که باقی شبکه را به هم وصل میکنند و اگر این نود ها از بین بروند میتوان شبکه را از کار انداخت.
مثال : بسیار از افرادی که با مشکلات روانی مثل افسردگی یا افکار خودکشی دست و پنجه نرم میکنند رفتار های شبکه اجتماعی به اینگونه دارند . یعنی هر دوستی که دارن از گروه مختلفی است که اطلاع چندانی از حقله دیگر دوستان فرد ندارد.
مثال تصویری یک شبکه centralized
اما وقتی به سمت جلوتر میروی و شیب نمودار متعادل تر میشود شبکه به شبکه decentralized تبدیل میشود و نود ها با اینکه شبکه های زیری خود را دارن و در گروه هایی هستند اما راه هایی به گروه های دیگر دارند
مثالی جالب : بسیاری از شبکه های تروریستی به اینگونه کار میکنند و برای از بین بردن شبکه کافی است چند رهبر کلیدی از شبکه نابود شوند تا شبکه از کار بیفتد
مثال تصویری یک شبکه decentralized
شکل شبکه هایی که تعداد degree distribution آن ثابت است و شیبی در نمودار دیده نمیشود به شبکه های distributed معروف هستند این نوع از شبکه ها centralized بسیار کمیاب هستند و کمتر در دنیای واقعی دیده میشوند
توجه داشته باشید که همیشه در این نوع گراف ها لازم نیست همه نود ها به هم وصل باشند بلکه باید تعداد ادج های هر نود بسیار نزدیک به متوسط نود های دیگر باشد برای مثال یک شش ظلعی میتواند یک گراف centralized باشد.
این نوع شبکه ها معمولا در شبکه های توضیع برق یا شبکه های کامپیوتری کوچک در یک اداره دیده میشوند.
یکی از انالیز هایی که ممکن است در اول به چشم انالیزور اماتور اهمیت نداشته باشد تراکم شبکه است که این تراکم با network density شناخته میشود و فرمولی به شکل زیر دارد
در این فرمول n تعداد نود های موجود در شبکه است و m تعداد ادج های موجود در شبکه است . اما عدد 2 در این فرمول هم متغیر جالبی است که باید به آن توجه کرد . این فرمول برای یک گراف undirected است و دلیل عدد 2 برای این است که بین هر دو گراف تعداد نوع نود میتواند دو باشد ، پس اگر گرافی دارید که انواع مختلفی ارتباط دارد باید عدد 2 را با تعداد نوع edge ها جایگزین کرد .
یکی از خواص جالب این فرمول تغییر رفتار نود ها در زمان های مختلف است .
برای مثال میتوان به تغییر رفتار حیوانات در طبیعت بین فصل زمستان و تابستان در یک پارک حفاظت شده اشاره کرد . یا بررسی رفتار دوستانه بین کارمندان شرکت قبل و بعد از مهمانی های شرکت اشاره کرد که بتوانیم بعضی از رفتار ها را بهتر انالیز بکنیم و ببینیم که اگر شرایط را برای رشد یک شبکه مهیا بکنیم شبکه چه مقدار رشد میکند که این بحث مارا به فرمول بعدی میکشاند
در این فرمول که ریز شده فرمول بالا میباشد سعی میکنیم که تراکم یک نود را به دست بیاوریم و ببینیم نسبت تعداد روابط موجود به روابط ممکن چقدر است
به عبارت دیگر میشود
در این فرمول k تعداد ادج های هر نود میباشد و (n-1) تعداد نود های ممکن برای هر نود هست چرا که خود نود را حساب نمیکنیم و دلیل اینکه در فرمول قبلی ما n را ضرب در (n-1) میکنیم همین هست، میخواهیم تعداد ماکسیمم هر نود ضرب در تعداد بیشترین عدد ارتباط با باقی نودها را بیابیم . اگر شبکه ما دارای ارتباطات جهت دار باشد یا با تلفظ درست آن که میشود directed graph باید فرمول را به زیر تغییر داد
in تعداد ادج های ورودی و out تعداد ادج های خروجی.
از این فرمول یکی از زیر ساخت های شناخت fraud در یک شبکه است. برای مثال از این فرمول میتوان برای محاسبه وضعیت هر نود در session مختلف و با افزایش ناگهانی تعداد ارتباطات با آن میتوان تصمیم گرفت که نود مورد نظر رفتاری خارج از نود های شبکه دارید یا میتوان گفت که تبدیل به موضوعی ترند شده در شبکه های اجتماعی است .
برای فهم بهتر این موضوع پیشنهاد میکنم جهت یاد اوری یا یادگیری الگوریتم dijkstra search algorithm را مطالعه بکنید .
این فرمول فرمولی دیگر جهت شناختن نود های مهم در شبکه است این الگوریتم بیشتر تلاش در پیدا کردن
نود های تنگنا یا به انگلیسی bottleneck دارد. و روش محاسبه ان به این صورت است :
که در اینجا سیگما یعنی این علامت
نشان دهنده تعداد مجموع کوتاهترین راه ها بین نود s و t است و سیگما st(v) نشان دهنده تکرار نود v در این راه ها است .
اجازه دهید با عکس توضیح بدهم : ( این عکس ها از ویدیو در این ویدیو یوتیوب تهیه شده )
این یک گراف ساده با 5 نود هست . راه های ارتباط ممکن برای این گراف با فرمول زیر محاسبه میشود :
که n تعداد نود ها میباشد .( تعداد نود ضرب در تعداد ارتباط های ممکن تقسیم بر دو چون تکرار نباید باشد)
برای فهم بهتر فرمول به جدول زیر توجه کنید :
حاصل فرمول 10 میشود . در جدول ها هم تعداد جفت های موجود عدد ده را نشان میدهد . جدول های قرمز نشان دهنده عدم ارتباط یک نود با خود یا عدم اجازه تکرار جفت بین نود ها میباشد .
وقتی همه راه های مختلف را در جدول نشان دهیم و راه ها و نود های تکرار شده در نزدیک راه بین راه های موجود در گراف را بنویسیم به جدول زید میرسیم :
حال باید جدول جمع را بر عددی تقسیم کنیم که از فرمول زیر به دست میاید :
نماد n تعداد نود های شبکه است .تعداد راه های ممکن از نود اول به بقیه شبکه یا (n-1) و تعداد راه های ممکن از نود دوم به بقیه شبکه بدون تکرار نود مبدا یا نود اول (n-2) عدد دو در این جا به همین دلیل است و تقسیم بر 2 چرا که تکرار نباید باشد در این راه ها و میرسیم به جدول زیر
این فرمول نیز در بسیاری از جاها استفاده میشود . در مثال شبکه تروریستی که در بالا زدیم، در شبکه های توضیع برق و گاز به دلیل کم کردن فشار از بعضی از شاه راه های کلیدی یا استفاده در پیاده سازی ساعت حرکت مترو ها وکم کردن تعداد مسافر های در یک ایستگاه ( مثلا ایستگاه مترو امام خمینی دارای Betweenness Centrality بسیار بالایی است )
در این روش تلاش میشود متوسط نزدیکترین نود به نود های دیگذ محاسبه شود و روش محاسبه باز هم دارای جدول های مختلف است اما من سعی میکنم که خلاصه تر بنویسم چرا که مطمئن هستم بعد از روش توضیح بالا متوجه بسیاری از محاسبات شده اید . تصویر زیر را در نظر بگیرید :
این تصویر کار رو برای من خیلی راحت کرد :)
به ماتریس راه های ارتباطی با فرض هر ادج دارای عدد یک نگاه بکنید . برای رفتن از نود A به تمام نود ها تمام راه های کوتاه را مینویسیم و حاصل جمع کل مقادر را میگیریم که میشود 6 بعد عدد را در مخرج (n-1) قرار میدهیم تا نزدیکی این نود را به نود های دیگر را حساب کنیم . هرچه عدد کوچکتر یعنی اطلاعات سخت تر از یک نود به بقیشه شبکه منتقل میشود و عدد یک که در نود B دیده میشود یعنی از B به هر نود یک راه وجود دارد و اطلاعات به راحتی منتقل میشود.
توجه : این فرمول در گیت هاب رو خودم نوشتم چون کتابخانه networkx این فرمول را ارور میدهد. توجه کنید که در پروداکشن استفاده نکنید و بیشتر قصد آموزشی دارد کد.
من نمیخواستم این موضوع رو اینجا توضیح بدم ولی موضوعی هست که خیلی به موضوع centrality مرتبط هست ولی خب خیلی فرمول طولانی داره و اگر بخوام توضیحش بدم حدود دو صفحه A4 لازم داریم و موضوع یک پست جداگانه هست اما سعی میکنم به صورت مفصل در پستی که دارم اماده میکنم درمورد page rank توضیحش بدم .
به صورت خلاصه eigenvector نشان دهنده ارتباط نود ها به نودهای مهم در شبکه است. این جمله یکم به خودی خود گیج کننده هست ولی اجازه بدین با مثال توضیح بدم .
یک شرکت رو در نظر بگیرید ، اگر نگهبان شرکت رو در نظر بگیریم ،نگهبان دارای بزرگترین closeness centrality هست اما در توضیع قدرت دارای قدرتی نیست ولی مدیر عامل مجموعه که ممکن هست همه خواص نودش کم باشه دارای قدرت بسیار بالایی هست چون با نود های بسیار مهم شبکه در ارتباط هست و معاون های مدیر عامل هستن که این قدرت رو به مدیر عامل میدن چون معاون ها دارای خواص شبکه ای بالایی هستن و این قدرت به مدیر عامل منتقل میشه و eigenvector بالایی پیدا میکنه.
اجازه بدین با عکس توضیح بدم.
شبکه زیر رو در نظر بگیرید :
بعد باید adjacency matrix ماتریکس را باید بنویسیم و عدد را در ارزش Eigenvector نود خود ضرب بکنیم بعد اصطلاحا ماتریکس حاصل را بر نرمال خود تقسیم بکنیم که عدد نرمال شده حاصل جمع توان دو همه اعداد است و بعد گرفتن ریشه دوم عدد یا همان جذر .
در عکس بالا در iteration اول adjacency matrix را ضرب در یک میکنم چون در iteration اول هستیم بعد ماتریس بعدی را در نظر بگیرید که حاصل جمع توان دو هر عدد میشود :
[9+4+9+9+4+9+4+4] که میشود عدد 52 و ریشه دوم میشود 7.211
بعد هر عدد ماتریس را تقسیم بر عدد نرمال شده میکنیم و این عملیات را چند بار تکرار میکنیم تا عدد نرمال شده k-1 یا همان دوره قبلی بسیار نزدیک به عدد فعلی باشد به اعداد پایین توجه کنید :
عدد نرمال شده از 7.21 به عدد 2.64 رسید تنها در چهار iteration اگر دوره سوم را نگاه کنیم متوجه میشویم که متوسط تغییر بسیار کم شد نسبت به دو iteration اول یعنی عدد از 2.67 به 2.64
یکی از بهترین راه های پیدا کردن ارتباطات جمعی بین یک گروه را فرمول های زیر مجموعه clustering coefficient دانست و میتوان از این فرمول ها به عنوان دروازه ای به بحث بسیار مهم community detection نگاه کرد .
در این فرمول هدف پیدا کردن fraction of possible interaction (فارسی درستش رو نمیدونم) بین نود ها همسایه هست و فرمول به این صورت کار میکند
متغییر Ni نشان دهنده تعداد ارتباط بین همسایگان نود i و Ki نشان دهنده درجه نود یا تعداد نود های در همسایه نود میباشد. در تصویر زیر میتوانید این محاسبات را بهتر دیده و انجام دهید :
برای پیدا کردن متوسط این فرمول برای کل گراف کافی است این فرمول را بر همه نود ها پیاده بکنید و نتیجه را بر تعداد نود ها تقسیم بکنید .
