علم شبکه
علم شبکه (انگلیسی: Network science) یک زمینه ی دانشگاهی است که شبکههای پیچیده از قبیل شبکههای ارتباط تلفنی، شبکههای رایانهای، شبکههای زیستی، شبکههای معنایی و شناختی و شبکههای اجتماعی را با در نظر داشتن تعداد عناصر مجزا و عوامل نمایش داده شده توسط گرهها (یا راسها) و ارتباط بین عناصر یا عوامل به شکل پیوندها (لینکها)، بررسی میکند. در این زمینه آکادمیک تئوریها و روشهایی مانند نظریه گراف از ریاضیات، مکانیک آماری از فیزیک، داده کاوی و تصویر سازی اطلاعات از علوم کامپیوتر، استنباط آماری از آمار، و ساختار اجتماعی از جامعهشناسی مورد استفاده قرار میگیرد. شورای ملی پژوهش ایالات متحده علم شبکه را به عنوان «مطالعه بازنمایی شبکه ای از پدیدههای فیزیکی، بیولوژیکی و اجتماعی که منجر به مدلهای پیشبینی از این پدیده را تعریف میکند.»
پیش زمینه و تاریخ
مطالعه شبکه در رشتههای گوناگون به عنوان روشی جهت تجزیه و تحلیل دادههای پیچیده ارتباطی به وجود آمدهاست. اولین مقاله شناخته شده در این زمینه، مسئله مشهور پلهای کونیگسبرگ نوشته شده توسط لئونار اویلر در سال ۱۷۳۶ است. شرح ریاضی اویلر از راسها و یالها، پایههای نظریه گراف را بنا نهاد. شاخه ای از ریاضیات که خواص روابط زوجها در یک ساختار شبکه را بررسی میکند. بعد از این زمینه نظریه گراف هم چنان توسعه یافت و کاربردهایی در شیمی پیدا کرد. (Sylvester, 1878)
در سال ۱۹۳۶، دینش کونیگ (یک ریاضیدان و استاد مجارستانی)، اولین کتاب در نظریه گراف را با عنوان «نظریه گرافهای محدود و بینهایت» نوشت.
در دهه جیکوب ال. مورنو، روانشناس سنت گشتالت وارد ایالات متحده شد. او جامعهشناسی گرافی را توسعه داد و در آوریل ۱۹۳۳ در یک کنوانسیون محققان پزشکی به عموم مردم ارائه داد. مورنو ادعا کرد که "قبل از ظهور جامعهشناسی مبتنی بر گرافها هیچکس نمیدانست ساختار روابط فردی در گروهها دقیقاً به چه شکل هستند .(Moreno, 1953) جامعهشناسی گرافی، نشان دهنده ساختار اجتماعی گروهی از دانش آموزان ابتدایی بود. پسران با پسرهای دیگر دوست بودند و دختران با دختران دیگر، به جز یک پسر که گفت که یک دختر را دوست دارد. این احساس،
متقابل نبود. این نمایش شبکه ای از ساختار اجتماعی به قدری جذاب بود که در نیویورک تایمز چاپ شد. (۳ آوریل۱۹۳۳، صفحه۱۷) جامعهشناسی گرافی کاربرد فراوانی پیداکرده و در زمینه تحلیل شبکههای اجتماعی رشد کردهاست.
نظریه احتمالات در شبکه به عنوان یک بخش از نظریه گراف با پال اردوش و هشت مقاله معروف آلفرد رنیی دربارهٔ گراف تصادفی توسعه یافت. برای شبکههای اجتماعی مدل نمایی گراف تصادفی یا *p یک چارچوب نمادین برای نشان دادن فضای احتمالی یک رابطه در یک شبکه اجتماعی استفاده میشود. یک رویکرد دیگر به ساختار شبکه احتمالی، ماتریس احتمالی شبکه است که احتمال وقوع راسها در یک شبکه را بر اساس حضور تاریخی یا عدم وجود یال در یک نمونه از شبکهها مدل میکند.
در سال ۱۹۹۸، دیوید کرچارت (به انگلیسی: David Krackhardt) و کاتلین کارلی (به انگلیسی: Kathleen Carley) ایده یک متاشبکه با مدل PCANS را معرفی کردند. آنها نشان دادند که «تمام تشکیلات در راستای این سه حوزه ساخته شدهاند، افراد، وظایف و منابع.» مقاله آنها مفهومی را ارائه میدهد که شبکهها در سراسر حوزههای مختلف رخ میدهد و همگی مرتبط هستند. این بحث در یک زیر بخش علم شبکه قرار میگیرد که آن را تجزیه و تحلیل شبکه پویا میدانند.
اخیراً تلاشهای علمی دیگر شبکه، بر روی ریاضیات توصیف توپولوژیهای شبکههای مختلف تمرکز پیدا کردهاست. دانکن واتس (به انگلیسی: Duncan Watts) با ریاضیات، دادههای تجربی را بر روی شبکه وفق میدهد و بر اساس آن شبکه جهان کوچک را توصیف میکند. آلبرت لاسبلو باراباسی (به انگلیسی: Albert-László Barabási) و رکا آلبرت (به انگلیسی: Reka Albert) شبکه مستقل از مقیاس را توسعه دادند که یک توپولوژی شبکه ای تعریف نشدهای است که شامل راسها و اتصالات بسیار است که یک عدد رشد شبکه دارد که از نسبت ثابت تعداد اتصالات نسبت به راسها بدست میآید. اگرچه بسیاری از شبکهها مانند اینترنت، به نظر میرسد که این جنبه را حفظ میکنند، شبکههای دیگر توزیع راسهای طولانی دارند که فقط فقط نسبت به مقیاس آزاد را تقریباً تقریبی میدانند.
ابتکارات وزارت دفاع ایالات متحده
در ابتدا ارتش ایالات متحده آمریکا در سال ۱۹۹۶ به جنگافزارهای شبکه محور به عنوان مفهومی عملیاتی مبتنی بر علم شبکه علاقهمند شد. جان پارمنتولا ریاست مدیریت تحقیقات و آزمایشگاه ارتش ایالات متحده آمریکا در ۱ دسامبر ۲۰۰۳ به شورای علم و فناوری ارتش(به انگلیسی: (Army’s Board on Science and Technology (BAST) پیشنهاد داد که علم شبکه به یک حوزه جدید تحقیقات ارتش تبدیل شود. شورای علم و فناوری ارتش یک مطالعه انجام داد تا ببیند آیا شناسایی و تأمین مالی یک حوزه جدید تحقیق در تحقیقات پایه علم شبکه میتواند شکاف بین آنچه برای انجام عملیاتهای شبکه محور نیاز است و دانش ابتدایی کنونی در مورد شبکهها را ببندد.
نتیجه این تحقیقات تعریف حوزهٔ جدید تحقیقات پایه علم شبکه برای ارتش بود. بر اساس یافتهها و توصیههای این مطالعه منابع تحقیقاتی ارتش به منظور ایجاد یک برنامه تحقیقاتی جدید در حوزه علم شبکه، اختصاص داده شدند. برای ایجاد یک مبنای نظری جدید برای شبکههای پیچیده، برخی از تحقیقات کلیدی که در حال حاضر در آزمایشگاههای ارتش انجام میشود، عبارتند از:
- مدلهای ریاضی مربوط به رفتار شبکه که برای پیشبینی عملکرد، با استفاده از اندازه شبکه، پیچیدگی و محیط مربوطه، به کار میروند.
- بهینهسازی عملکرد انسان برای استفاده از جنگافزارهای تحت شبکه.
- شبکه سازی داخل اکوسیستمها و همینطور در سطح مولکولی درون سلولها.
مشخصات شبکه
اغلب شبکهها ویژگیهای خاصی دارند که میتواند برای تجزیه و تحلیل خواص و ویژگیهای شبکه محاسبه شود. این ویژگیهای شبکه اغلب مدلهای مختلف شبکه را توصیف میکند و میتواند برای تجزیه و تحلیل شبکهها و مقایسهٔ آنها با یکدیگر استفاده شود.
اندازه
اندازه شبکه میتواند به تعداد راسها
چگالی
چگالی
تراکم شبکه مسطح (به انگلیسی: Planar Network Density)
چگالی
میانگین درجهها
درجه
میانگین طول مسیر (یا مشخصه طول مسیر)
میانگین طول مسیر با یافتن کوتاهترین مسیر بین تمام جفت راسها، اضافه کردن آنها و سپس تقسیم بر تعداد کل جفتها محاسبه میشود. این مشخصه به ما نشان میدهد که برای رفتن از یک راس به راس دیگر در شبکه، بهطور متوسط چند قدم لازم است.
قطر شبکه
به عنوان یکی دیگر از ابزار اندازهگیری نمودار شبکه، ما میتوانیم قطر یک شبکه را به عنوان طولانیترین از تمام کوتاهترین مسیرهای محاسبه شده در شبکه تعریف کنیم. . این کوتاهترین فاصله بین دو راس دورتر در شبکه است. به عبارت دیگر، زمانی که کوتاهترین طول مسیر از هر راس به تمام راسهای دیگر محاسبه میشود، قطر طولانیترین طول مسیر محاسبه شدهاست. قطر نشان دهنده اندازه خطی یک شبکه است.
ضریب خوشگی
ضریب خوشگی معیاری است برای نشان دادن این ویژگی که «همهٔ دوستان من یکدیگر را میشناسند». گاهی اوقات ضریب خوشگی به صورت دوستان دوست من، دوست من هم هستند توصیف میشود. بهطور دقیقتر ضریب خوشگی یک راس به نسبت یالهای موجود بین همسایهها به بیشینه یالهای ممکن بین همسایههای یک راس گفته میشود. ضریب خوشگی بالا در یک شبکه، نشانه دیگری از یک شبکه دنیای کوچک است.
ضریب خوشگی راس
که
همبندی
نحوه اتصال راسهای یک شبکه به یکدیگر نقش مهمی در تحلیل و تفسیر شبکهها دارد. شبکهها در چهار دسته مختلف طبقهبندی میشوند:
- گراف کامل: یک شبکه کاملاً متصل که همهٔ راسهای آن به هم متصلاند. این شبکهها از این جهت که همهٔ راسها یالهایی از دیگر راسها و یالهایی به دیگر راسها دارند متقارن هستند.
- جزء غول پیکر: یک جزء متصل که حاوی بسیاری از راسها در شبکه است.
- جزء متصل ضعیف: مجموعه ای از راسها است که در آن حداقل یک مسیر، بدون در نظر گرفتن جهت یالها بین دو راس وجود دارد.
- جزء کاملاً متصل: مجموعه ای از راسها است که در آن مسیری جهتدار بین همه راسها وجود دارد.
مرکزیت راس
شاخصهای مرکزیت، رتبهبندی را به وجود میآورند که به دنبال شناسایی مهمترین راسها در یک مدل شبکه هستند. شاخصهای مختلف مرکزیت مفاهیم مختلفی را برای کلمه «اهمیت» تعریف میکنند. به عنوان مثال مرکزیت بینابینی راسی را مهم در نظر میگیرد که بین راسهای زیاد دیگری پل به وجود بیاورد. مرکزیت ویژه مقداری بهطور خلاصه راسی که راسهای مهم دیگری به آن متصل باشند را مهم قلمداد میکند. صدها معیار اینچنینی در ادبیات علم شبکه پیشنهاد شدهاست.
شاخصهای مرکزیت برای شناسایی مرکزیترین راسها دقت دارند. این معیارها به ندرت برای دیگر راسهای شبکه با معنی هستند. همچنین این شاخصها فقط در همان تعریفی که از مفهوم اهمیت دارند دقیق هستند و در تعاریف دیگر اشتباهات زیادی دارند. به عنوان مثال دو جامعه جدا از هم را در نظر بگیرید که تنها ارتباط آنها ارتباط جوانترین عضو این دو جامعه با یکدیگر است از آنجایی که هرگونه انتقال از یک جامعه به جامعه دیگر باید از این اتصال بگذرد پس دو عضو جوان مرکزیت بینابینی بالایی خواهند داشت اما از آنجایی که آنها جوان هستند احتمالاً ارتباطات کمی با راسهای مهم در جامعه خودشان دارند یعنی مرکزیت ویژه مقداری آنها بسیار کم خواهد بود.
مفهوم مرکزیت در زمینه شبکههای ایستا بر پایه پژوهشهای عددی و تئوری به مرکزیت پویا، در زمینه شبکههای وابسته به زمان و شبکههای موقت، تأمین داده شدهاست.
تأثیر راس
محدودیتهای معیارهای مرکزیت منجر به توسعه معیارهای کلیتری شدهاست دو مثال از تاثیر راس یکی دسترسی است که برای اندازهگیری میزان دسترسی یک راس به بقیه شبکه از تنوع ولگشتهای تصادفی استفاده میکند. مثال دیگر نیروی چشمداشتی است که از چشمداشتی نیروی سرایت تولید شده توسط یک راس، به دست میآید. هر دوی این مؤلفهها میتوانند از ساختار شبکه به تنهایی بهطور معنی دار محاسبه شوند.
مدلهای مختلف شبکه
مدلهای شبکه به عنوان یک پایه برای درک فعل و انفعالات در شبکهٔ پیچیده تجربی استفاده میشوند. انواع روشهای تولید گراف تصادفی، مدلها و ساختارهای مختلف گراف را تولید میکنند که میتوان از آنها در مقایسه با شبکههای پیچیده دنیای واقعی استفاده کرد.
مدل تصادفی اردوش-رنیی
مدل اردوش-رنیی که به نام پال اردوش و آلفرد رنیی نامگذاری شدهاست، برای تولید گرافهای تصادفی استفاده میشود که در آن یالها بین راسها با احتمال یکسان توزیع میشود. این نوع گراف را میتوان در روش احتمالاتی برای اثبات وجود گرافهایی که خواصهای مختلف را رعایت میکنند، یا برای تعریف دقیق معنای یک ویژگی برای تقریباً تمام گرافها استفاده میشود.
برای ساختن مدل اردوش-رنیی
در این مدل ضریب خوشهبندی صفر 0 است(قریب به یقین!). رفتار گراف
پیشبحرانی
بحرانی
فرابحرانی
بزرگترین مؤلفه متصل دارای پیچیدگی بالایی است. همه اجزای دیگر ساده و کوچک هستند
مدل پیکربندی
مدل پیکربندی یک دنباله ای از درجهها یا توزیعی از درجهها را به عنوان ورودی میگیرد، و در همه موارد به غیر از توزیع درجه، گراف به صورت تصادفی متصل میشود. این به این معنی است که برای یک انتخاب داده شده از توزیع درجهها، گراف بهطور یکنواخت و به صورت تصادفی از مجموعه ای از تمام گرافها که با این توزیع سازگار است انتخاب میشود. درجه
زمانی که
به طوری که
در مدل پیکربندی جهت دار، درجه یک راس با دو عدد داده میشود، درجه ورودی
برای مؤلفه ای که جهت آن به سمت داخل است و
برای مؤلفه ای که جهت آن به سمت خارج راس است.
مدل دنیای کوچک و واتس-استروگاتز
مدل واتس و استروگاتز یک مدل تولید گراف تصادفی است که گرافهایی را با خواص مدل دنیای کوچک تولید میکند. یک ساختار اولیه شبکه برای تولید مدل واتس-استروگاتر استفاده میشود. هر راس در شبکه ابتدا به
همانطور که مدل واتس-استروگاتز به عنوان یک ساختار غیر تصادفی شبکه ساخته میشود، دارای ضریب خوشهگی بسیار بالا همراه با طول متوسط مسیر بالاست. هر بازنشانی احتمال دارد یک میانبر میانبر میان خوشههای بسیار متصل ایجاد میکند. زمانی که احتمال بازنشانی افزایش پیدا میکند، ضریب خوشهگی از میانگین طول مسیر با سرعت کمتری کاهش پیدا میکند. در واقع، به این شکل اجازه میدهد تا میانگین طول مسیر شبکه بهطور قابل توجهی کاهش یابد در صورتی که ضریب خوشهگی کمی کاهش یافتهاست. مقدار بالاتر
مدل اتصال ترجیحی باراباشی-آلبرت
مدل باراباشی-آلبرت یک مدل شبکه تصادفی است که برای نشان دادن اثر اتصال ترجیحی یا «ثروتمند ثروتمند تر میشود» استفاده شدهاست. در این مدل یک یال به احتمال بیشتری به یک راس با درجه بالاتر متصل میشود. این شبکه با یک شبکه اولیه با m0 راس که m0 ≥ ۲، شروع میشود و درجه هر راس در شبکه اولیه حداقل باید ۱ باشد، در غیر اینصورت آن راس همیشه بدون اتصال به شبکه باقی میماند.
در مدل باراباشی-آلبرت راسهای جدید به صورت هر راس در یک واحد زمان به شبکه اضافه میشوند هر راس جدید به
که ki درجه راس i است. راسهایی که یالهای زیادی دارند (قطب (به انگلیسی: Hub)) تمایل دارند تا به سرعت یالهای بیشتری را جمعآوری کنند. در حالی که راسهایی که تنها تعداد کمی یال دارند، بعید است که به عنوان مقصد یک یال جدید انتخاب شوند. راسهای جدید یک ترجیح برای اتصال خودشان به راسهای با یالهای زیاد دارند.
توزیع درجاتی که از یک مدل باراباشی-آلبرت نتیجه میشود بی مقیاس است. بهطور خاص این توزیع قانون توانی(به انگلیسی: Power law) به شکل زیر است:
قطبها مرکزیت بینابینی بالایی را از خود نشان میدهند که اجازه میدهد مسیرهای کوتاه بین راسها وجود داشته باشد. به عنوان یک نتیجه مدل باراباشی-آلبرت تمایل دارد تا میانگین کوتاهترین طول مسیرهای پایینی داشته باشد. ضریب خوشگی این مدل هم به صفر میل میکند. در حالیکه قطر بسیاری از مدلها شامل مدل گراف تصادفی اردوش-رنیی و چندین مدل دنیای کوچک دیگر با لگاریتم N متناسب است، مدل باراباشی-آلبرت D~loglogN (دنیای فوقالعاده کوچک) را نشان میدهد. توجه داشته باشید که میانگین طول مسیر با N، به عنوان قطر مقیاس میشود.
مدل اتصال با واسطه
در مدل اتصال با واسطه یک راس جدید با
عامل
مطالعات گسترده عددی نشان میدهد که برای تقریباً
از این رو میتوان دید که شبکه MDA به صورت مبدل از قانون اتصال ترجیحی پیروی میکند.
با این حال
مدل سازگاری
مدل دیگری است که عنصر کلیدی آن ماهیت راس است و توسط کالدارلی و همکاران معرفی شدهاست. در این مدل با احتمالی که با تابع اتصال
اگر
بنابراین اگر سازگاری
با یک توزیع احتمال به شکل
با
این نوع مدل برای توصیف تجارت بین کشورها و استفاده از GDP به عنوان سازگاری راسهای
با موفقیت مورد استفاده قرار گرفتهاست.
تجزیه و تحلیل شبکه
تحلیل شبکههای اجتماعی
تحلیل شبکههای اجتماعی (به انگلیسی: Social network analysis)، ساختار روابط بین نهادهای اجتماعی را بررسی میکند. این نهادها اغلب افراد هستند، اما ممکن است گروهها، سازمانها، ایالتهایملی، وبسایتها، نشریات علمی نیز باشند.
از دههٔ ۱۹۷۰ مطالعه تجربی شبکهها نقش مهمی در علوم اجتماعی ایفا کردهاست، و بسیاری از ابزارهای ریاضی و آمار مورد استفاده در مطالعهٔ شبکهها ابتدا در حوضهٔ جامعهشناسی توسعه یافتند. از جمله کاربردهای فراوان، از تحلیل شبکههای اجتماعی برای درک نحوهٔ انتشار نوآوریها، اخبار و شایعهها، بررسی نحوهٔ شیوع بیماریها و درمان متناظر با آنها، مطالعهٔ بازارها در تبادل روابط و مکانیسمهای اجتماعی در تنظیم قیمتها، مطالعه استخدامها در جنبشهای سیاسی و سازمانهای اجتماعی، تفهیم اختلافات علمی در کنار اعتبار دانشگاهی استفاده شدهاست. اخیراً تحلیل شبکه در کنار تحلیل ترافیک استفاده قابل توجهی در اطلاعات نظامی برای کشف شبکههای شورشی، چه نظاممند و چه بدون رهبر کسب کردهاست.
تحلیل شبکههای پویا
تحلیل شبکههای پویا (به انگلیسی: Dynamic network analysis) ساختار متغیر روابط بین طبقات مختلف نهادها را در خواص سامانههای پیچیده اجتماعی_فنی بررسی میکند و عواملی مانند ثبات اجتماعی و تغییراتی مانند ظهور گروهها، موضوعات و رهبران جدید را نشان میدهد.
تحلیل شبکههای پویا بر روی متا شبکهها متشکل از انواع مختلف راسها (نهادها) و انواع مختلف پیوندها (یالها) متمرکز است. این راسها (نهادها) میتوانند بسیار متنوع باشند همچون افراد، سازمانها، موضوعات، منابع، وظایف، حوادث، مکانها و باورها.
تکنیکهای تحلیل شبکه پویا بخصوص برای ارزیابی روند و تغییرات شبکهها در طول زمان، شناسایی رهبران پیشرو و بررسی هماهنگی مردم و ایدهها مفید هستند.
تحلیل شبکههای زیستی
اخیراً با زیاد شدن دادههای بیولوژیکی، تحلیل شبکههای مولکولی توجه زیادی را بهخود جلب کردهاست. نوع تحلیل در این شبکهها بسیار شبیه تحلیل شبکههای اجتماعی است به نحوی که در این نوع تحلیل، الگوهای محلی شبکهها اغلب مورد تمرکز است. برای مثال شکل عمدهٔ شبکه (موتیف شبکه)، زیرگرافهای کوچکی هستند که در شبکه بیش از حد نمایان میشوند. موتیفهای فعال الگوهای شبیه بههم هستند که خواص یکسانی از راسها و یالها را در ساختار شبکه دارند. این تحلیل شبکههای بیولوژیکی منجر به توسعهٔ شبکههای دارویی شدهاست که به بررسی تأثیرات بیماریها در تعامل میپردازد.
تحلیل پیوند (یال)
تحلیل پیوند (یال) (به انگلیسی: Link analysis) یک زیرگروه از تحلیل شبکه است که ارتباط بین اشیا (راسها) را مورد بررسی قرار میدهد. برای مثال برای پیدا کردن آدرسهای مظنونین و قربانیان، شماره تلفنهایی که این اشخاص با آنها تماس گرفتهاند و معاملات مالیای که طی یک دوره زمانی معین انجام دادهاند و همچنین روابط خانوادگی بین این افراد بهعنوان بخشی از تحقیقات پلیس در نظر گرفته میشود. تحلیل پیوند (یال) روابط حساس و ارتباطات بسیار مهمی بین اشیا (راسها) مختلف پیدا میکند که بهطور آشکار در اطلاعات مجرد اولیه موجود نیست.
تحلیل پیوند (یال) با استفاده از کامپیوتر بهطور اتوماتیک بهطور فرایندهای توسط بانکها و آژانسهای بیمه برای تشخیص تقلب، اپراتورهای مخابراتی درتحلیل شبکه مخابراتی، بخش پزشکی در اپیدمیولوژی و فارماکولوژی، موتورهای جستجو برای رتبهبندی مربوط به تحقیقات اجرای قانون، برعکس توسط اسپمها و صاحبان کسب و کار برای بهینهسازی موتورهای جستجو، و در هر جای دیگر که در آن روابط بین اشیا (راسها) باید تجزیه و تحلیل شوند، استفاده میشود.
مقاومت شبکه
مقاومت ساختاری شبکه (به انگلیسی: Network robustness) با استفاده از نظریه تراوش انجام میشود. هنگامی که یک بخش بحرانی از راسها حذف شود، شبکه به خوشههای کوچک تقسیم میشود. این فرایند تراوش نام دارد و انواع گذار فاز از نظر منظم-غیرمنظم را با نمای بحرانی مربوطه توصیف میکند.
تحلیل همهگیری
مدل SIR یکی از شناختهشدهترین الگوریتمهای پیشبینی گسترش همهگیریهای جهانی داخل یک جامعه عفونی است.
مستعد به آلودهشدن
فرمول بالا مقدار نیروی عفونت را برای هر واحد حساس در یک جامعه عفونی توصیف میکند، که در آن β برابر میزان انتقال بیماری است.
برای پیدا کردن تغییر تعداد واحدهای حساس در یک جامعه عفونی از رابطه زیر استفاده میشود:
از آلوده به بهبودیافته
در طول زمان، تعداد کسانی که آلوده شدند توسط نرخ بهبود µ تغییر میکند ولی به اندازه میانگین زمانی آلودگی کاهش مییابد، همچنین تعداد افراد آلوده
دوره زمانی آلودگی
با توجه به مدل SIR اینکه یک جامعه از یک بیماری فراگیر بهبود یابد وابسته به مقدار
تحلیل یال وب (به انگلیسی: Web link analysis)
بسیاری از الگوریتمهای رتبهبندی وبسایتها از معیارهای مرکزیت پیوند (یال)ها استفاده میکنند. از جمله (به ترتیب) موتور جستجو مارجوری، رتبهبندی گوگل، الگوریتم HITS کلینبرگ، الگوریتمهای CheiRank و TrustRank.
تحلیل یال در علوم اطلاعات و ارتباطات نیز به منظور درک و استخراج اطلاعات از ساختار مجموعه ای از صفحات وب انجام میشود. برای مثال تحلیل روابط بین وبسایتها و وبلاگهای سیاستمداران مختلف.
رتبهصفحه
رتبهصفحه (به انگلیسی: PageRank) به این صورت است که راسها یا وبسایتهایی به صورت تصادفی انتخاب میشوند و با یک احتمال مشخص به صورت تصادفی به راس (وبسایت)های دیگر میرود. این انتخاب تصادفی به رتبهصفحه کمک میکند که از همه مسیرهای شبکه عبور کند و وبسایتهایی که به آسانی قابل دیدن نیستند را پیدا کند.
هر راس مانند
پرش تصادفی
همانطور که در بالا توضیح داده شد، رتبهصفحه در حال تلاش برای اختصاص یک رتبهٔ رتبهصفحه به هر وبسایت در اینترنت است. این پرشهای تصادفی وبسایتهایی را پیدا میکند که ممکن است با روشهای جستجوی عادی مانند Breadth-First Search و Depth-First Searchپیدا نشوند.
برای بهبود فرمول فوق برای مشخص کردن رتبهصفحه، اجزا پرش تصادفی را باهم جمع میکنند. بدون این پرشهای تصادفی بعضی از صفحهها دارای رتبهصفحه صفر میشوند که این اصلاً خوب نیست.
در فرمول زیر آلفا احتمال رخ دادن پرش تصادفی است.
سنجههای مرکزیت
اطلاعات مربوط به اهمیت نسبی راسها و پیوندها در یک گراف میتواند از طریق سنجشهای مرکزیت که بسیار مورد استفاده در رشتههای جامعهشناسی است، حاصل شود. سنجشهای مرکزیت زمانی مهم میشوند که میخواهیم به سوالاتی مانند: "کدام راس در شبکه باید مورد هدف قرار گیرد تا اطلاعی یا خبری از طریق این راس بتواند به تمام یا بیشتر راسهای شبکه برسد؟" پاسخ دهیم. یا برعکس " کدام راس مورد هدف قرار گیرد تا از گسترش یک بیماری جلوگیری شود؟".
از جمله معیارهای اصلی سنجشهای مرکزیت: درجه راس (به انگلیسی: Degree centrality)، نزدیکی (به انگلیسی: Closeness centrality)، بینابینی (به انگلیسی: Betweenness centrality)، ویژهبردار مرکزی (به انگلیسی: Eigenvector centrality) و مرکزیت کاتز (به انگلیسی: Katz centrality). معمولاً هدف و مقصد از تحلیل شبکه استفاده از انواع سنجشهای مرکزیت را مشخص میکند.
درجه راس تعداد یالهایی است که وارد آن راس شدهاند.
نزدیکی یک راس از جمع کوتاهترین فاصله این راس با تمام دیگر راسها بدست میآید.
بینابینی اهمیت نسبی یک راس را با استفاده از ترافیکی که آن راس بین بقیه راسها ایجاد کردهاست بیان میکند. این مقدار برابر است با تقسیم تعداد مسیرها بین تمام جفت راسها بر تمام مسیرها بین جفت راسهایی که راس مورد نظر را دربردارند.
ویژهبردار مرکزی مفهومی مانند درجه راس دارد با این تفاوت که مرکزیت یک راس نه تنها وابسته به تعداد یالهایی است که به آن راس وارد میشوند، بلکه به کیفیت آن یالها نیز وابسته است. مقدار آن با استفاده از ماتریس مجاورت شبکه بدست میآید.
مرکزیت کاتز از جمع تمام مسیرهای ژئودسی بین آن راس و تمام راسهای قابل دسترس به آن راس بدست میآید. این مسیرها وزندار میباشند به طوری که وزن مسیرهایی که همسایه مجاور را به آن راس وصل میکنند بزرگتر از وزن مسیرهایی است که همسایههای دورتر را به آن راس وصل میکنند.
جستارهای وابسته
منابع
- کتاب آنلاین علم شبکه تألیف آلبرت باراباشی، ترجمه علی کمندی، http://dsc.ut.ac.ir/dm-bok/publications/