An evolutionary algorithm approach to link prediction in dynamic social networks

An evolutionary algorithm approach to link prediction in dynamic social networks
Abstract
Many real world, complex phenomena have underlying structures of evolving networks where nodes and links are added and removed over time. A central scientific challenge is the description and explanation of network dynamics, with a key test being the prediction of short and long term changes. For the problem of short-term link prediction, existing methods attempt to determine neighborhood metrics that correlate with the appearance of a link in the next observation period. Recent work has suggested that the incorporation of topological features and node attributes can improve link prediction. We providean approach to predicting future links by applying the Covariance Matrix Adaptation Evolution Strategy(CMA-ES) to optimize weights which are used in a linear combination of sixteen neighborhood and node similarity indices. We examine a large dynamic social network with over 106nodes (Twitter reciprocal reply networks), both as a test of our general method and as a problem of scientific interest in itself. Our method exhibits fast convergence and high levels of precision for the top twenty predicted links. Based on our findings, we suggest possible factors which may be driving the evolution of Twitter reciprocal reply networks

.خلاصه فارسی حاصل از تجزیه و تحلیل مقاله​:

یک الگوریتم تکاملی، برای پیش بینی لینک در شبکه های اجتماعی پویا

چکیده

در موارد بسیاری از جهان واقعی، پدیده ها و ساختارهای اساسی شبکه های پیچیده درحال تحول می باشند که در آن گره ها و لینک ها در طول زمان حذف یا اضافه می شوند. چالش علمی مرکزی شرح و توضیح پویایی این شبکه ها است، که با یک آزمون کلیدی سعی در پیش بینی تغییرات کوتاه مدت و بلند مدت دارد. برای حل این مشکل از پیش بینی لینک کوتاه مدت استفاده می کنیم، روش موجود بیانگر تلاش برای تعیین معیارهای محلی که با ظهور یک لینک در دوره مشاهده بعدی ارتباط دارد. که اختلاط ویژگی های توپولوژیک و ویژگی های گره را می توان برای بهبود پیش بینی لینک پیشنهاد کرد. رویکرد پیش بینی لینک آینده با استفاده از روش کوواریانس  ماتریس سازگاری تکامل یافته (CMA-ES) این است که برای بهینه سازی وزن در یک ترکیب خطی از شانزده شاخص محلی و شباهت گره استفاده می کند. ما به بررسی یک شبکه اجتماعی پویا بزرگ با بیش از 106 گره (شبکه توییتر پاسخ متقابل)که به عنوان یک آزمون از روش کلی و به عنوان یک مشکل مورد علاقه علمی استفاده شده است. روش ما  همگرایی سریع و سطح بالایی از دقت برای بیست لینک پیش بینی کرد. تضاد مبتنی بر یافته های ما، عوامل احتمالی است که ممکن است توسط محرک های شبکه تکامل توییتر (پاسخ متقابل) نشان داده شود.

مقدمه

شبکه های اجتماعی در طول زمان تغییر می کنند که می توان از انها برای مدل سازی گروه های پویای متغیر استفاده کرد. افراد، بیانگر گره ها هستندکه ممکن است داخل و یا خارج از شبکه باشند، در حالی که این فعل و انفعالات، ممکن است باعث تقویت یا تضعیف مدل های رشد بسیاری از شبکه های خاص جهانی شود ولی اما پویایی در آینده مشکل این شبکه ها است. در این مقاله تمرکز اصلی بر روی  مشکل پیش بینی لینک است: با توجه به پیش زمینه از یک شبکه مانند Gt= (V, Et) با گره های V (گره موجود در تمام مراحل زمانی) و Et لینک ها، در زمان t ما به دنبال پیش بینی لینک که در زمان t + 1 رخ می دهد هستیم.روشهای پیش بینی لینک را می توان به طور گسترده به سه گروه دسته بندی کرد: استراتژی مبتنی بر شباهت، الگوریتم حداکثر احتمال، و مدل های احتمالی. همانطور که توسط لو و همکارانش اشاره شد دو روش انتهایی می تواند برای یک شبکه بزرگ بیش از 100000 گره وقت گیر باشد. با توجه به علاقه ما به شبکه های بزرگ و با تعداد گره های زیاد پراکنده ، تمرکز اصلی بر اطلاعات محلی و استفاده از شاخصهای شباهت برای توصیف احتمال تعاملات آینده است. بادر نظر گرفتن دو گروه عمده شاخص های شباهت:  شاخص شباهت توپولوژیکی و شباهت مبتنی بر ویژگی گره.به نظر نمی رسد که شاخصهای شباهت در همه حالات بهترین عملکرد را داشته باشند. بسته به شبکه و تجزیه و تحلیل اقدامات مختلف باید امیدوار به بهترین نتیجه بود.این نشان می دهد که پیش بینی بهترین لینک وابسته به ساختار ذاتی و فردی مرتبط با شبکه و نه از مجموعه کامل از بهترین روشهای پیش بینی است. علاوه بر این پیش بینی بهترین لینک ممکن است به عوامل درونی و برونی شبکه در حال  تکامل نیز بستگی داشته باشد.شاخص شباهت توپولوژیکی از رمزگذاری اطلاعات در مورد همپوشانی نسبی بین گره های همسایه استفاده می کنند. ما انتظار داریم که دو گره با بیشترین شباهت توپولوژیکی  "مشابه" هستند (به عنوان مثال، همپوشانی در دوستان به اشتراک گذاشته خود)، با احتمال زیادتر ممکن است که در آینده آنها با یک لینک به هم وصل شوند  مانند شاخص همسایگان مشترک و بسیاری از دیگر از شاخصهای شباهت توپولوژیک، که برای ارتباط یا وقوع لینک در آینده نشان داده شده است .هدف کلی در اینجا ارائه یک روش پیش بینی لینک که شامل هر دو اطلاعات توپولوژیکی و کاربری خاص باشد و سریع ترین پاسخ با کمترین پارامتر ممکن و عدم پیچیدگی محاسباتی را دارا باشد.در این مقاله، ما با رسم یک مدل خطی برای ترکیب معیارهای شباهت های محلی و داده ه ای خاص گره ها و استفاده از یک الگوریتم تکاملی پیدا کردن ضرایب سعی در بهینه سازی روش پیش بینی لینک داریم. با فرض اینکه که تمام شاخص های شباهت از اهمیت مساوی برخوردار هستند، ما اجازه می دهیم که برای تنظیم وزن ترکیب خطی از از روش کوواریانس ماتریس سازگاری تکامل (CMA-ES). استفاده کنیم.به وضوح ، مدل بهینه ای که ساختار فرضمان را با شاخص های شباهت ترکیب می کند ممکن است خطی نباشد و این یک محدودیت برای کار ما است . ولی می توان گفت ، کار ما چندین برتری نسبت به روش های دیگر پیش بینی لینک دارد و این روش آشکار می کند که یک مدل خطی ساده قابل مقایسه (توسعه پذیر) تولید می شود و دستاورد هایی قابل توجه ( اگر نه بهترتر ) برای توسعه مکانیسم هایی پیش بینی لینک در شبکه های در حال تکامل ارایه می دهد.در بسیاری از روش ها ، تلاش برای پیش بینی لینک مناسب  درهر دو حالت ساختار مدل و پارامترهای ان است. برای از میان برداشتن این چالش ، مجموعه ای از ویژگی های شبکه های بزرگ در نظر گرفته می شود، که محققان از ان برای کاهش پیچیدگی محاسباتی با انجام ازمایش و نمونه برداری استفاده می کنند. رویکرد ما استفاده از روش CMA-ES برای پیش بینی لینک که شامل چند شاخص پیش بینی لینک، صرف نظر از عملکرد فرض اصلی می باشد. مزیت این روش ان است هیچ فرضی از کلاس شبکه و نه دانش قبلی در مورد سیستم و تجزیه و تحلیل قبلی مورد نیاز نیست.اگر چه روش ما برای پیش بینی لینک در شبکه های اجتماعی پویا بزرگ متمرکز است و این روش مستقل از نوع شبکه می باشد و ممکن است به عوامل مختلف مانند بیولوژیکی، زیرساخت های اجتماعی و شبکه های مجازی بستگی داشته باشد. ما از نماد شانزده شاخص شباهت متداول در اینجا استفاده می کنیم و تاکید می کنیم که هر شاخص شباهت دیگری نیز ممکن است برای گسترش مطالعات می تواند استفاده شود. انتخاب معیارهای شباهت تا حد زیادی به داده های موجود (به عنوان مثال، ابرداده برای گره ها و شاخص های توپولوژیک مناسب در دسترس در زمینه شبکه در حال مطالعه) و اندازه شبکه تحت بررسی بستگی دارد. محدودیت دیگر چندین روش نظارت برای پیش بینی لینک است که تفسیر مدل های متفاوت هریک از انها ممکن است اطلاعات کمی یا اشتباهی در مورد عملکرد فرآیندهای تکاملی شبکه در اختیار ما قرار دهد. هدف روش ما ارائه شفافیت و تشخیص بهترین شاخص برای پیش بینی لینک در شبکه های در حال تکامل در اینده است .  در سال های اخیر موجی از علاقه برای مشاهده فعالیت توییتر از طریق تحلیل شبکه اجتماعی به راه افتاده است.. در بسیاری از مطالعات، گره ها نشان دهنده افراد و لینک ها نشان دهنده رفتار انها است (پاسخ متقابل) .برنامه ما برای پیش بینی لینک در توییتر (شبکه پاسخ متقابل)  طراحی شده واین روش برای اولین بار توسط Bliss و همکارانش ارائه شده است. ما تحولات این شبکه را در مقیاس زمانی یک هفته در نظر می گیریم که در آن گره ها نشان دهنده کاربران و لینک ها نشان دهنده شواهد (رفتارها) پاسخ های متقابل در طول مدت زمان تجزیه و تحلیل است. در حالی که بسیاری از مطالعات دیگر نیز بیانگر همین حرف ما یعنی استفاده از پاسخ متقابل به عنوان شواهدی از تعاملات اجتماعی و فعال افراد است. با توجه به اندازه بزرگ از شبکه های که ما به دنبال  مطالعه انها هستیم و این فرضیه که احتمال دوستی (ارتباط) بین دوستانی که از قبل سابقه مشارکت داشته اند بیشتر است نسبت به کسانی که اصلا با هم در ارتباط نبوده اند و از این رو این مطلب باعث ایجاد محدودیت پیش بینی لینک های جدید در زمان t + 1 که بین افراد که در طول یک مسیر  در زمان t عبور می کنند، خواهد شد. بخشهای این مقاله بدین صورت است که: در بخش اول ما داده های مورد استفاده، شانزده شاخص تشابه  و الگوریتم تکاملی مورد استفاده برای تکامل وزن در این شاخص ها را توضیح می دهیم. در بخش دوم توضیح روش در حال مطالعه و در بخش سوم بحث در مورد اهمیت این یافته ها و همچنین جهت آینده برای کار بیشتر در این زمینه صحبت خواهیم کرد.

An evolutionary algorithm approach to link prediction in dynamic social networks Catherine A. Bliss∗, Morgan R. Frank, Christopher M. Danforth, Peter Sheridan Dodds

شاخص های شباهت جهانی

شاخص های شباهت جهانی

شاخص کاتز

این شاخص مبتنی بر مجموعه تمام مسیرها ی اثر گذار و بیانگر مجموعه ای از مسیرهای کامل و نمایی با طول معین  که نشان دهنده ی کوتاه ترین مسیربا  بیشترین وزن است.

در فرمول این شاخص β  باید کمتر از بزرگترین مقدار ویژه ماتریس A باشد زیرا برای اطمینان از همگرایی معادله این شاخص است.

شاخص LHN2))

 این شاخص یک نوع از شاخص کاتز است. بر اساس این مفهوم است که دو گره مشابه تنها همسایگان خود فقط خودشان هستند.

شاخص میانگین رفت و آمد زمان (ACT).

معرف (X، Y) که متوسط تعداد مراحل مورد نیاز توسط حرکت کننده تصادفی با شروع از گره x برای رسیدن به گره Y، متوسط زمان رفت و آمد بین x و y است .

شاخص کسینوس بر اساس+ L.

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

شاخص پیاده روی تصادفی با راه اندازی مجدد (RWR).

این شاخص یک برنامه مستقیم از الگوریتم PageRank است. وبیانگر یک واکر تصادفی با شروع از گره xکه به طور مکرر به همسایه تصادفی با احتمال C رفت و برگشت خواهد کرد که احتمال بازگشت به گره x برابر با احتمال 1 - C است.

شاخص SimRank شبیه به LHN2

وبدین گونه تعریف می شود با فرض اینکه که اگر دو گره مشابه با هم متصل به دوگره مشابه دیگر باشند.

شاخص ماتریس جنگل (MFI)

که در آن شباهت بین x و y می تواند به عنوان نسبت تعداد ماتریسهای جنگل پوشا متعلق به ریشه یک درخت ازگره x و y است  نسبت به یک عضو از ماتریس جنگل ریشه مربوط به گره x است.

شاخص مسیر محلی (LP)

 به ارائه یک راه حل مناسب و خوب از لحاظ دقت و پیچیدگی محاسباتی می پردازدویک شاخص با در نظر گرفتن راههای محلی با افق گسترده تر از CNاست .

شاخص تصادفی پیاده روی محلی (LRW)

 برای اندازه گیری شباهت بین گره x و y، واکر تصادفی در ابتدا در گره x قرار داده و در نتیجه تراکم اولیه با هر مرحله tافزایش می یابد.

شاخص تصادفی منطبق بر پیاده رویSRW))

مشابه به شاخص RWR ، که در آن واکر تصادفی است به طور مداوم از نقطه شروع اغاز می کند، و در نتیجه بالاترین شباهت برابربا  بین شباهت گره هدف و نزدیکترین گره به ان هست.

شاخص شباهت شمار توییت (T)

T(u) تعداد توییت‌هایی را که برای گره‌ی u در یک هفته جمع شده‌اند، اندازه‌گیری می‌کند. این شاخص، کمیت شباهت شمارش توییت‌های دو فرد را اندازه‌گیری می‌کنند، که 1 نشان دهنده‌ی شمار‌های توییت یکسان و 0 نشان دهنده‌ی شمارهای توییت غیر مشابه می‌باشد.

شاخص شباهت شادی (H)

در پژوهش قبلی امتیازهای(H)به عنوان میانگین امتیازهایHبرای کلمات تالیفی کاربران u وv  در طول هفته‌ی تجزیه و تحلیل، محاسبه شدند.

شاخص شباهت کلمه (w) 

برای یک مجموعه‌ی متشکل از 50000 کلمه‌ی به کار رفته در توییتر از 2008 تا 2011، شباهت کلمات به کار رفته توسط u و v با فاصله‌ی همینگ اصلاح شده، محاسبه می‌شود. که در آن   نشان دهنده‌ی فراوانی نرمال کاربرد کلمه‌ی nام با کاربر u می‌باشد. مقدارw(u,v) از 0 ( کاربرد کلمات غیر مشابه ) تا1(کاربرد کلمات مشابه)می‌باشد

شاخص های شباهت محلی

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

شاخص های شباهت محلی

همسایه مشترک (CN)

 برای گره x، معرف مجموعه ای از همسایگان x است. در حالت مشترک، دو گره، x و y، به احتمال زیاد با یک لینک در ارتباطند چون  همسایگان مشترک زیادی دارند. Q  ساده ترین روش اندازه گیری این همپوشانی است، یعنی مجموعه اعداد اساسی از گروه Q که در آن است. درSXY = (A2) XY مشخص است که در آن A ماتریس مجاورت است: اگر x و y به طور مستقیم متصل شده 1= Axy  ودر غیر این صورت 0= Axy. همچنین توجه داشته باشید که، XY (A2) بیانگر تعدادی از مسیرهای مختلف با طول 2 متصل بین دو گره x و yاست. شاخص نیومن برای بررسی مقدار همکاری بین شبکه ها استفاده می شود و بیانگر یک رابطه مثبت بین تعداد همسایگان مشترک و احتمال این که در آینده دو دانشمند همکاری خواهند کردیا خیر. وات بر این عقیده است که تجزیه و تحلیل یک شبکه اجتماعی مقیاس ازاد، نشان می دهد که دو دانشجویی دوستان زیاد مشترکی دارند بسیار محتمل است که در آینده با هم دوست شوند.

شاخص جاکارد(J)

احتمال این که یک مجاور از u یاv مجاور، مجاور هر دوی آنهاست را اندازه‌گیری می‌کند.این سنجش روشی است برای شناسایی محتوای مشترک که در بازیابی اطلاعات معنی دار است.

شاخص سالتون

به صورت فرمول زیر که KX در ان درجه گره x است تعریف شده است. نیز شباهت کسینوسی نامیده می شود.

تعداد مجاورهای مشترک مربوط میانگین هندسی را اندازه‌گیری می‌کند.

شاخص Sørensen

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

شاخص ترویج هاب (HPI)

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

شاخص منزوی هاب (HDI).

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

شاخص نیومن ( LHN1)

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

شاخص پیوست ترجیحی (PA).

شاخص پیوست ترجیحی می تواند برای تولید شبکه های قابل گسترش (مقیاس ازاد) مورد استفاده قرار گیرد، که در آن احتمال ایجاد یک لینک جدید به گره x برابر با kx است. یک مکانیسم مشابه نیز می توان برای شبکه های قابل گسترش بدون رشد در نظر گرفت که در آن در هر مرحله زمان منجر به اینکه یک لینک قدیمی حذف می شود و یک لینک جدید تولید می شود .احتمال ایجاد یک لینک جدید بین x و y برابر باKX × KY است. هدف این مکانیزم، به طور کلی برای تعیین کمیت و اهمیت کارکردی لینک های پویای مختلف مبتنی بر شبکه است ، مانند نفوذ ، هماهنگ سازی  و حمل و نقل میباشد . توجه داشته باشید که این شاخص به همه اطلاعات از گره های همسایه خود نیاز ندارد، و نتیجه آن حداقل پیچیدگی محاسباتی است.

شاخص آدم-ادار (AA)

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

شاخص تخصیص منابع RA

این شاخص با هدف تخصیص منابع پویا در شبکه های پیچیده کار میکند بدین گونه که یک جفت از گره ها مانند X,Y که به طور مستقیم متصل نیستد را در نظر بگیرید. گره X می تواند برخی از منابع را به y و یا همسایگان مشترک خود که نقش فرستنده را دارند، ارسال کند. در ساده ترین حالت، فرض کنیم که هر فرستنده دارای یک واحد از منابع، و به همان اندازه آن را بین تمام همسایگان خود توزیع میکند. شباهت بین x و y را می توان به صورت مقدار منابع دریافت شدهY از X تعریف کرد. مقدار منبع ارائه شده برای یک گره را در نظر می‌گیرد و فرض می‌کند که هر گره منبع خود را در میان مجاورها به طور برابر توزیع می‌کند.

دیتاست مقاله پیش بینی لینک با در نظر گرفتن خوشه بندی

 

مجموعه داده ها (DATA SET)ممکن است برای اشاره به داده ها در یک مجموعه ای از جداول نزدیک ومرتبط ، مربوط به یک آزمایش یا رویداد خاص مورد استفاده قرار گیرد. توضیحات زیرمربوط به یک نمونه از این نوع مجموعه داده ه ای  جمع آوری شده توسطXu Feng, Jichang Zhao and، KeXua  برای پیش بینی لینک در شبکه های پیچیده با در نظر گرفتن خوشه بندی است.

مطالعه شبکه های پیچیده فراگیر موجود در دنیای واقعی و تجربی نشان می دهد که بسیاری از این شبکه اکثرا از نوع  "مقیاس ازاد"، (مدل بارباسی البرت)  هستند که این مدل شبکه ای قابل گسترش، برای توضیح مکانیسم  "قانون قدرت توزیع"، شناخته شده است .به عنوان مثال مدل BAرا در نظر بگیرید.ما از این مدل برای تولید شبکه های مصنوعی استفاده می کنیم. شبکه تولید شده توسط مدل BA را به عنوان(BA (N M در نظر می گیریم که در آن N اندازه شبکه تولید شده، m تعداد لینک هایی که با اضافه شدن گره های جدید ایجاد خواهند شد و همچنین درجه متوسط شبکه 2mاست. ما پنج شبکه را دراین DATA SET تولید میکنیم.

ما همچنین از سه شبکه پیچیده از رشته های مختلف در دنیای واقعی استفاده کرده ایم که به شرح زیر است:

 شبکه دانش، شبکه ای از دانشمندان که جدیدترین تالیفات خودشان را در موضوعات مختلف باهم به اشتراک می گذارند. در این شبکه 1589 دانشمند وجود دارد و  128 نفر از آنها از شبکه جدا شده اند که ما از انها در این آزمایش استفاده نمی کنیم.

شبکه برق یک شبکه برق به خوبی نشان دهنده شبکه پیچیده است، که در آن گره ها را ژنراتورها، ترانسفورماتور ها و پستها تشکیل می دهند و لبه (لینک ها ) خطوط انتقال بین آنها است

شبکه وبلاگ سیاسی که متشکل از سیاستمداران است که  در اینجا ما پیوندهای بین انها را بدون جهت در نظر می گیریم و ارتباطات بین خودشان حذف گردیده است. شرح مفصلی از این مجموعه داده ها در جدول 1 ذکر شده است.

شبکه	| V |	| E |	k	C	fGCC
BA(1000,2)	1000	1997	4	0.027	1
BA(1000,5)	1000	4985	10	0.039	1
BA(1000,10)	1000	9945	20	0.064	1
BA(2000,5)	2000	9985	10	0.024	1
BA(4000,5)	4000	19985	10	0.017	1
شبکه دانش	1461	2742	3.75	0.878	0.26
توزیع برق	4941	6594	2.67	0.107	1
وبلاگ سیاسی	1224	16715	27.31	0.36	0.998

جدول 1. مجموعه داده های مصنوعی و دنیای واقعی

شبکه های پیچیده

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

نمایی از یک شبکه ی پیچیده، رنگ های مختلف گره ها نشان دهنده ی بخشی است که هر گره متعلق به آن است

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

مثالهایی از شبکه های پیچیده

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

شبکه های اجتماعی

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

شبکه های حمل و نقل

شبکه های حمل و نقل مانند راه های جاده ای، ریلی و هوایی نقش مهمی در زندگی امروز دارند. در این شبکه ها می توان گره ها را ترمینال ها و فرودگاه ها فرض کرد و یال ها را راه های زمینی و هوایی بین این گره ها در نظر گرفت. یکی از اهداف اصلی بررسی این شبکه ها کاهش هزینه ی ایجاد راه های جدید یا حذف راه های قدیمی در حین حفظ کارآیی شبکه است.