تئوری شبکه
یک شبکه نمونه کوچک با هشت راس و ده لبه
| علم شبکه | ||||
|---|---|---|---|---|
| ||||
| ||||
| انواع شبکه | ||||
| نمودارها | ||||
| ||||
| مدل ها | ||||
| ||||
| ||||
نظریه شبکه ، مطالعه نمودارها به عنوان بازنمایی از روابط متقارن یا روابط نامتقارن بین اشیاء گسسته است. در علوم رایانه و علوم شبکه ، نظریه شبکه بخشی از تئوری نمودار است : یک شبکه را می توان به عنوان گرافی تعریف کرد که گره ها و / یا لبه ها دارای صفاتی هستند (به عنوان مثال نام).
نظریه شبکه در بسیاری از رشته ها از جمله فیزیک آماری ، فیزیک ذرات ، علوم کامپیوتر ، مهندسی برق [1] [2] ، زیست شناسی ، [3] اقتصاد ، دارایی ، تحقیقات عملیاتی ، اقلیم شناسی ، اکولوژی ، بهداشت عمومی کاربردهای زیادی دارد. [4] [5 ] ] و جامعه شناسی . برنامه های نظریه شبکه شامل شبکه های لجستیکی ، شبکه جهانی وب ، اینترنت ، شبکه های تنظیم کننده ژن ، شبکه های متابولیک ، شبکه های اجتماعی، شبکه های معرفت شناختی و غیره؛ برای مثالهای بیشتر به لیست مباحث تئوری شبکه مراجعه کنید .
راه حل اویلر از هفت پل از مشکل كنیگسببرگ اولین اثبات واقعی در تئوری شبکه ها است.
فهرست
بهینه سازی شبکه [ ویرایش ]
با کنار گذاشتن مهمترین فعل و انفعالات بی ربط در شبکه ، کار بهینه سازی شبکه سخت NP را به زیرشاخه ها تجزیه کنید. [6]
مشکلات شبکه که شامل یافتن یک روش بهینه برای انجام کاری است ، تحت عنوان بهینه سازی ترکیبی مورد مطالعه قرار می گیرند . مثالها عبارتند از شبکه جریان ، مسئله یافتن کوتاهترین مسیر ، مشکل حمل و نقل ، مشکل انتقال ، مشکل مکان ، مشکل تطبیق ، مشکل انتساب ، بسته بندی مشکل ، مسیریابی مشکل ، تجزیه و تحلیل مسیر بحرانی و PERT (برنامه ارزیابی و نقد و بررسی تکنیک). به منظور شکستن یک NP-سختوظیفه بهینه سازی شبکه به زیرشاخه ها تبدیل می شود و شبکه به زیر شبکه های نسبتاً مستقل تجزیه می شود. [6]
تجزیه و تحلیل شبکه [ ویرایش ]
تجزیه و تحلیل شبکه الکتریکی [ ویرایش ]
تجزیه و تحلیل سیستم های برق می تواند با استفاده از تئوری شبکه از دو دیدگاه اصلی انجام شود:
(1) چشم انداز انتزاعی (به عنوان مثال ، همانطور که یک نمودار از گره ها و لبه ها تشکیل شده است) ، صرف نظر از جنبه های قدرت الکتریکی (به عنوان مثال ، امپدانس های خط انتقال). بیشتر این مطالعات فقط بر ساختار انتزاعی شبکه برق با استفاده از توزیع درجه گره و توزیع فاصله ، تمرکز دارند که بینش قابل توجهی در مورد ارزیابی آسیب پذیری شبکه ارائه می دهد. از طریق این نوع مطالعات ، می توان دسته ساختار شبکه را از منظر شبکه پیچیده (به عنوان مثال ، تک مقیاس ، بدون مقیاس) شناسایی کرد. این طبقه بندی ممکن است به مهندسان سیستم برق در مرحله برنامه ریزی یا هنگام ارتقاء زیرساخت (به عنوان مثال اضافه کردن یک خط انتقال جدید) کمک کند تا سطح افزایشی مناسب در سیستم انتقال را حفظ کند. [7]
(2) نمودارهای وزنی که درک انتزاعی از تئوریهای شبکه پیچیده و خصوصیات سیستمهای الکتریکی را در هم می آمیزند. [8]
تجزیه و تحلیل شبکه های اجتماعی [ ویرایش ]
تجسم تجزیه و تحلیل شبکه های اجتماعی [9]
تجزیه و تحلیل شبکه های اجتماعی به بررسی ساختار روابط موجودات اجتماعی می پردازد. [10] این نهادها اغلب افراد هستند ، اما ممکن است گروه ها ، سازمان ها ، ایالت های کشور ، وب سایت ها یا نشریات علمی باشند .
از دهه 1970 ، مطالعه تجربی شبکه ها نقش اساسی در علوم اجتماعی داشته است و بسیاری از ابزارهای ریاضی و آماری مورد استفاده برای مطالعه شبکه ها برای اولین بار در جامعه شناسی توسعه یافته اند . [11] در میان بسیاری از برنامه های دیگر ، از تحلیل شبکه های اجتماعی برای درک انتشار نوآوری ها ، اخبار و شایعات استفاده شده است. به طور مشابه ، از آن برای بررسی شیوع بیماریها و رفتارهای مرتبط با سلامتی استفاده شده است . همچنین برای مطالعه بازارها ، از آنجا كه برای بررسی نقش اعتماد [ استناد مورد نیاز ] در آن استفاده شده است ، نیز استفاده شده استروابط مبادله و سازوکارهای اجتماعی در تعیین قیمت. به همین ترتیب ، از آن برای مطالعه استخدام در جنبشهای سیاسی و سازمانهای اجتماعی استفاده شده است. همچنین برای مفهوم سازی اختلافات علمی و همچنین اعتبار علمی از آن استفاده شده است. اخیراً ، تجزیه و تحلیل شبکه (و تحلیل ترافیک پسر عموی نزدیک آن ) برای کشف شبکه های شورشی با ماهیت سلسله مراتبی و بدون رهبری ، کاربرد چشمگیری در اطلاعات نظامی داشته است. [ نیاز به استناد ]
تجزیه و تحلیل شبکه بیولوژیکی [ ویرایش ]
همچنین ببینید: شبکه متابولیک ، پروتئوم ، متابولوم و اومیک
با انفجار اخیر داده های بیولوژیکی توان بالا در دسترس عموم ، تجزیه و تحلیل شبکه های مولکولی مورد توجه زیادی قرار گرفته است. [12] نوع تجزیه و تحلیل در این زمینه ارتباط نزدیکی با آنالیز شبکه های اجتماعی دارد ، اما غالباً روی الگوهای محلی در شبکه تمرکز می شود. به عنوان مثال ، نقوش شبکه زیرگراف های کوچکی هستند که بیش از حد در شبکه نمایان می شوند. به همین ترتیب ، نقوش فعالیت الگویی در ویژگی های گره ها و لبه های موجود در شبکه هستند که با توجه به ساختار شبکه بیش از حد نمایان می شوند. استفاده از شبکه ها برای تجزیه و تحلیل الگوهای در سیستم های بیولوژیکی ، مانند شبکه های مواد غذایی ، به ما امکان می دهد تا ماهیت و قدرت تعامل بین گونه ها را تجسم کنیم. تجزیه و تحلیل شبکه های بیولوژیکیبا توجه به بیماری ها منجر به توسعه زمینه پزشکی شبکه شده است . [13] نمونه های اخیر کاربرد تئوری شبکه در زیست شناسی شامل برنامه هایی برای درک چرخه سلولی است [14] و همچنین یک چارچوب کمی برای فرآیندهای توسعه. [15] تعامل بین سیستم های فیزیولوژیکی مانند مغز ، قلب ، چشم ها و غیره می تواند به عنوان یک شبکه فیزیولوژیکی در نظر گرفته شود. [16]
تجزیه و تحلیل شبکه روایت [ ویرایش ]
شبکه روایتگر انتخابات ایالات متحده 2012 [17]
تجزیه خودکار شرکتهای متنی استخراج بازیگران و شبکه های ارتباطی آنها را در مقیاس وسیع امکان پذیر کرده است. شبکه های روایی حاصل ، که می توانند هزاران گره داشته باشند ، سپس با استفاده از ابزارهایی از تئوری شبکه برای شناسایی بازیگران اصلی ، جوامع یا احزاب اصلی و خصوصیات عمومی مانند استحکام یا پایداری ساختاری شبکه کلی یا مرکزیت آنالیز می شوند. گره های خاص [18] این رویکرد معرفی شده توسط تجزیه و تحلیل کمی روایت را اتوماسیون می کند ، [19] که به موجب آن سه قطعه موضوع-فعل- جسم با جفت بازیگران مرتبط با یک عمل یا جفت های ایجاد شده توسط بازیگر مشخص می شوند. [17]
تجزیه و تحلیل پیوند [ ویرایش ]
تجزیه و تحلیل پیوند زیر مجموعه ای از تجزیه و تحلیل شبکه است و به بررسی روابط بین اشیاء می پردازد. یک مثال ممکن است بررسی آدرس افراد مظنون و قربانیان ، شماره تلفنهایی که آنها شماره گیری کرده اند و معاملات مالی است که در طی یک بازه زمانی معین در آنها شرکت کرده اند و روابط خانوادگی بین این افراد به عنوان بخشی از تحقیقات پلیس است. تجزیه و تحلیل پیوند در اینجا روابط و ارتباطات بسیار مهم بین اشیاء بسیار زیادی از انواع مختلف را ارائه می دهد که از اطلاعات جداگانه اطلاعات آشکار نیست. تجزیه و تحلیل پیوند مبتنی بر رایانه یا کاملاً خودکار مبتنی بر رایانه به طور فزاینده ای توسط بانک ها و سازمان های بیمه در کلاهبرداری به کار می رودتشخیص، توسط اپراتورهای مخابراتی در تجزیه و تحلیل شبکه های مخابراتی، توسط بخش پزشکی در اپیدمیولوژی و فارماکولوژی ، در اجرای قانون تحقیقات ، توسط موتورهای جستجو برای ارتباط امتیاز (و برعکس توسط اسپم برای هرز آگهیها و توسط صاحبان کسب و کار برای بهینه سازی موتور جستجو) و هرجای دیگر که روابط بین بسیاری از اشیاء باید تجزیه و تحلیل شود. پیوندها همچنین از شباهت رفتار زمان در هر دو گره حاصل می شوند. به عنوان مثال شبکه های آب و هوایی وجود دارد که پیوندها بین دو مکان (گره) به عنوان مثال توسط شباهت بارندگی یا نوسانات دما در هر دو سایت مشخص می شود. [20] [21] [22]
استحکام شبکه [ ویرایش ]
استحکام ساختاری شبکه ها با استفاده از تئوری نفوذ انجام می شود . [23] هنگامی که بخش مهمی از گره ها (یا پیوندها) به طور تصادفی برداشته می شوند (خرابی های تصادفی) ، شبکه در خوشه های جدا شده کوچک خرد می شود. این پدیده نفوذ نامیده می شود ، [24] و آن را یک نوع اختلال نظم از انتقال فاز با عوامل بحرانی نشان می دهد. نظریه انباشتگی می تواند اندازه بزرگترین مؤلفه (به نام مؤلفه غول پیکر) ، آستانه نفوذ بحرانی و مأمورین مهم را پیش بینی کند. شکستهای مورد بحث در بالا تصادفی هستند ، همانطور که معمولاً در تئوری نفوذ تصور می شود. با این حال ، هنگام تعمیم نفوذ به حملات غیر تصادفی اما هدفمند ، به عنوان مثال ، در گره های بالاترین درجه ، نتایج ، مانند p_c ، به طور قابل توجهی تغییر می کنند [25] [26]. اخیراً ، نوع جدیدی از خرابی ها در شبکه ها ایجاد شده است ، حملات موضعی نامیده می شود [27]. در این حالت یکی گره را به طور تصادفی انتخاب کرده و همسایگان خود و نزدیکترین همسایگان خود را تا زمانی که کسری از گره های 1-پ حذف شود حذف می کند. یکی از نمونه های واقع بینانه از نفوذ تصادفی استفاده از تئوری نفوذ برای پیش بینی تکه تکه شدن پوسته های ویروس بیولوژیکی (کپسیدها) است ، با آستانه نفوذ کپسید ویروس هپاتیت B پیش بینی و کشف شده به صورت آزمایشی: یک بازی مولکولی ، به طور تصادفی از Jenga در یک راماتیک. کره کاشی [28] [29]
تجزیه و تحلیل پیوند وب [ ویرایش ]
چند جستجو در وب بندی رتبه الگوریتم استفاده از معیارهای مبتنی بر مرکزیت لینک، از جمله گوگل را رتبه ، کلینبرگ است الگوریتم HITS از CheiRank و TrustRank الگوریتم باشد. تجزیه و تحلیل پیوند نیز به منظور درک و استخراج اطلاعات از ساختار مجموعه صفحات وب در علوم اطلاعات و علوم ارتباطات انجام می شود. به عنوان مثال ، تجزیه و تحلیل ممکن است بین وب سایتها یا وبلاگهای سیاستمداران در هم تنیده باشد. استفاده دیگر برای طبقه بندی صفحات با توجه به ذکر آنها در سایر صفحات است. [30]
اقدامات مرکزیت [ ویرایش ]
اطلاعات مربوط به اهمیت نسبی گره ها و لبه ها در یک نمودار را می توان از طریق اقدامات مرکزیت بدست آورد ، که به طور گسترده در رشته هایی مانند جامعه شناسی استفاده می شود . به عنوان مثال، بردار ویژه مرکزیت با استفاده از بردارهای ویژه از ماتریس مجاورت مربوط به یک شبکه، به منظور تعیین گره های که تمایل دارند که اغلب بازدید. اقدامات به طور رسمی تاسیس مرکزیت هستند مرکزیت درجه ، مرکزیت متراکم ، مرکزیت betweenness ، بردار ویژه مرکزیت ، مرکزیت گراف و مرکزیت کاتز. هدف یا هدف تجزیه و تحلیل به طور کلی نوع اندازه گیری مرکزیت مورد استفاده را تعیین می کند. به عنوان مثال ، اگر کسی به دینامیک شبکه ها یا استحکام شبکه به حذف گره / پیوند علاقه دارد ، اغلب اهمیت دینامیکی [31] یک گره مناسب ترین اندازه مرکزیت است. برای اندازه گیری مرکزیت مبتنی بر آنالیز k-core رفس کنید. [32]
مخلوط جمع آوري و جداسازي [ ويرايش ]
اطلاعات بیشتر: مخلوط کردن مجموعه ای
این مفاهیم برای توصیف ترجیحات پیوند دهنده هابها در یک شبکه استفاده می شوند. هاب ها گره هایی هستند که تعداد زیادی پیوند دارند. برخی از مراکز متمایل به سایر مراکز ارتباطی نیستند ، در حالی که برخی دیگر از اتصال به هابها جلوگیری می کنند و ترجیح می دهند به گره هایی با اتصال کم وصل شوند. ما می گویم وقتی تمایل به اتصال به سایر مراکز دیگر وجود دارد ، یک مرکز هنجارنده است. یک مرکز تفریحی از اتصال به مراکز دیگر جلوگیری می کند. اگر هابها با احتمال تصادفی پیش بینی شده ارتباط داشته باشند ، به آنها خنثی گفته می شود. سه روش برای تعیین کمیت همبستگی درجه وجود دارد.
شبکه های عود [ ویرایش ]
ماتریس عود از یک طرح عود می تواند به عنوان ماتریس مجاور یک شبکه غیرمستقیم و بدون وزنه در نظر گرفته شود. این امر می تواند تجزیه و تحلیل سری های زمانی را با اقدامات شبکه انجام دهد. برنامه ها از تشخیص تغییرات رژیم نسبت به توصیف پویایی تا تجزیه و تحلیل همگام سازی متغیر است. [33] [34] [35]
پخش [ ویرایش ]
محتوای در یک شبکه پیچیده می تواند از طریق دو روش اصلی گسترش یابد: گسترش حفاظت شده و گسترش بدون حفاظت. [36] در گسترش حفاظت شده ، مقدار کل محتوا که وارد یک شبکه پیچیده می شود با گذر از آن ثابت می ماند. مدل پخش کنسرو شده به بهترین وجه می تواند توسط یک پارچ حاوی مقدار مشخصی از آب که در یک سری قیف های وصل شده توسط لوله ها ریخته می شود ، نشان داده شود. در اینجا پارچ نشان دهنده منبع اصلی است و آب محتوا در حال پخش است. قیف ها و لوله های اتصال به ترتیب گره ها و اتصالات بین گره ها را نشان می دهند. با عبور آب از یک قیف به دیگری ، آب فوراً از قیف که قبلاً در معرض آب قرار داشت ، ناپدید می شود. در گسترش غیر محافظت شده ، مقدار محتوا با ورود و از طریق شبکه پیچیده تغییر می کند. مدل پخش بدون محافظت به بهترین وجه می تواند توسط یك شیر آب در حال اجرا كه از طریق یك سری قیف های متصل به لوله ها نشان داده می شود ، نشان داده شود. در اینجا ، مقدار آب از منبع اصلی نامتناهی است. همچنین ، هر قیف هایی که در معرض آب قرار گرفته اند ، حتی با گذر از قیف های پی در پی ، همچنان آب را تجربه می کنند. مدل بدون محافظت مناسب ترین برای توضیح انتقال بیشتر استبیماری های عفونی ، تحریک عصبی ، اطلاعات و شایعات و غیره
ایمن سازی شبکه [ ویرایش ]
مسئله چگونگی ایمن سازی شبکه های آزاد در مقیاس کارآمد که نمایانگر شبکه های واقع گرایانه مانند اینترنت و شبکه های اجتماعی هستند ، به طور گسترده مورد بررسی قرار گرفته است. یکی از این راهکارها ایمن سازی بزرگترین گره های درجه ، یعنی حملات هدفمند (عمدی) ^ [24a ، 24b] است زیرا برای این مورد p_c نسبتاً زیاد است و گره های کمتری برای ایمن سازی لازم است. اما در اکثر گره های واقع گرایانه ساختار جهانی در دسترس نیست و بزرگترین گره های درجه شناخته شده نیستند. برای این مورد ، روش ایمن سازی آشنایی تدوین شده است [37] . در این حالت ، که کاملاً کارآمد است ، گره ها را به طور تصادفی انتخاب می کنند اما همسایگان خود را ایمن می کنند. روش دیگر و حتی کارآمدتر مبتنی بر روش پارتیشن گراف است [38] .
شبکه های وابسته به وابستگی [ ویرایش ]
یک شبکه وابسته به هم وابسته ، سیستمی از شبکه های همراه است که گره های یک یا چند شبکه به گره های شبکه های دیگر وابسته هستند. این وابستگی ها با تحولات فن آوری مدرن تقویت می شود. وابستگی ممکن است به خرابی آبشار بین شبکه ها منجر شود و یک شکست نسبتاً کوچک می تواند منجر به خرابی فاجعه بار سیستم شود. خاموشی نمایش مهمی از نقش مهمی است که وابستگی بین شبکه ها ایفا می کند. یک مطالعه اخیر چارچوبی را برای بررسی شکستهای آبشار در یک سیستم شبکه وابسته به یکدیگر ایجاد کرده است. [39] [40]
منبع