ریاضیات

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

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

از نظر ریاضی ، شبکه های اجتماعی را می توان به صورت نمودار یا ماتریس نشان داد. در این جزوه ، ما در مورد نمودارها بحث می کنیم.

نمودار به عنوان مجموعه ای از گره ها و مجموعه ای از خطوط که گره ها را به هم متصل می کنند تعریف می شود. این گاهی اوقات به صورت ریاضی به صورت G = (V ، E) یا G (V ، E) نوشته می شود. در اینجا یکی از روش های رسم نمودار وجود دارد:

شکل 1. رسم نمودار.

مهم است که به خاطر داشته باشید که طول خطوط معمولاً معنایی ندارد. دلیل این امر آنست که تمام آنچه نمایانگر آن است وجود یا عدم وجود رابطه است. به همین ترتیب ، جهت گیری نقاشی معنایی ندارد. به عنوان مثال ، گره e می توانست در وسط نقاشی قرار گیرد - این معنای دیگری نخواهد داشت. تنها چیزی که مهم است این است که چه کسی با چه کسی در ارتباط است.

اصطلاحات مترادف بسیاری برای اصطلاحات "گره" و "خط" وجود دارد:

گره های موجود در نمودار نمایانگر اشخاص (یا حیوانات ، سازمان ها ، شهرها ، کشورها و غیره) و خطوط نمایانگر روابط بین آنها هستند. خط بین اشخاص a و b از نظر ریاضی اینگونه نشان داده می شود: (a، b). شبکه رسم شده در بالا حاوی این لبه ها است: (a، b)، (a، e)، (a، d)، (b، c)، and (d، c).

نمودارها انواع مختلفی دارند. به عنوان مثال ، نمودارهای هدایت شده و بدون جهت وجود دارد. در نمودارهای بدون جهت ، پیوندها هیچ جهتی ندارند. به عنوان مثال ، در شکل 1 بالا ، بین a و b رابطه وجود دارد و این همان چیزی است که گفته می شود بین b و a رابطه وجود دارد. می توانیم از خط به صورت (a، b) یا (b، a) یاد کنیم - تفاوتی ندارد.

در نمودارهای جهت دار (همچنین به عنوان نمودار شناخته می شود) ، پیوندها جهت دارند. در چنین مواردی ، ما معمولاً نمودار را با نوک پیکان می کشیم و از خطوط به عنوان "قوس" یاد می کنیم. به عنوان مثال ، شکل 2 را در نظر بگیرید این ممکن است رابطه اجتماعی "چه کسی چه کسی را دوست دارد" را ثبت کند. افراد b ، d و e همه می گویند که شخص a را دوست دارند. توجه داشته باشید که فرد نمی گوید که آنها d یا e را دوست دارند ، اما آنها با b پاسخ متقابل می دهند. هیچ کس نمی گوید آنها e را دوست دارند.

شکل 2. نمودار کارگردانی شده.

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

شکل 3. نمودار ارزشمند.

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

یک زیرگراف از یک نمودار زیر مجموعه ای از نقاط آن به همراه تمام خطوطی است که اعضای زیر مجموعه را به هم متصل می کند. زیر نمودار شکل 3 شامل انگلیس ، کانادا و الجزایر دارای دو خط است: (انگلستان ، الجزایر) و (الجزایر ، کانادا).

درجه یک نقطه به عنوان تعداد خطوط رخ داده روی آن گره تعریف می شود. در شکل 3 ، درجه ایالات متحده آمریکا 3 است زیرا دارای 3 گره است. اگر یک نقطه دارای درجه 0 باشد ، آن را ایزوله می نامند. اگر درجه 1 داشته باشد آویز نامیده می شود.

در یک نمودار جهت دار ، یک نقطه هم منفی است و هم منفصل. مقدار اضافه تعداد قوسها از آن نقطه به نقاط دیگر است. در شکل 2 ، میزان گره اضافی a برابر است با 1. مقدار کم تعداد تعداد قوس هایی است که از نقاط دیگر به نقطه وارد می شوند. درجه گره a در شکل 2 3 است.

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

پیاده روی مانند یک مسیر است با این تفاوت که در تعداد دفعات بازدید از یک نقطه محدودیتی وجود ندارد. مسیر نوعی پیاده روی است.

چرخه دقیقاً مانند یک مسیر است با این تفاوت که در همان نقطه شروع و پایان می یابد.

طول یک مسیر یا پیاده روی (یا چرخه) به عنوان تعداد لبه های آن تعریف می شود.

کوتاهترین مسیر بین دو نقطه را ژئودزیک می نامند. همیشه منحصر به فرد نیست (یعنی ممکن است چندین مسیر بین همان دو نقطه وجود داشته باشد که به همان اندازه کوتاه هستند). فاصله تئوری نمودار بین دو نقطه به عنوان طول کوتاهترین مسیر بین آنها تعریف شده است.

[اگر چیزی از طریق شبکه ای جریان دارد (مانند شایعات یا بیماری) ، زمانی که برای رسیدن از یک نقطه به نقطه دیگر طول می کشد تا حدی تابعی از فاصله نظری نمودار بین آنها است. گره هایی که به طور متوسط ​​از همه گره های دیگر دور نیستند ، تمایل دارند آنچه را که در شبکه جریان دارد زودتر از گره های دیگر دریافت کنند. ]

اگر مسیر از هر گره به هر گره دیگر وجود داشته باشد ، نمودار متصل می شود. طولانی ترین مسیر ممکن بین هر دو نقطه در یک نمودار متصل n-1 است ، جایی که n تعداد گره های نمودار است.

اگر یک گره از هر گره دیگر وجود داشته باشد ، از یک گره دیگر قابل دسترسی است.

یک جز connected متصل حداکثر زیرنویس است که در آن همه گره ها از یکدیگر قابل دسترسی هستند. حداکثر به این معنی است که بزرگترین زیرگراف ممکن است: شما نمی توانید گره دیگری را در هیچ کجای نمودار پیدا کنید به گونه ای که بتواند به زیرگراف اضافه شود و همه گره های موجود در زیرگراف همچنان متصل باشند.

برای نمودارهای جهت دار ، اجزای قوی و م componentsلفه های ضعیف وجود دارد. یک م strongلفه قوی یک زیرگراف حداکثر است که در آن مسیری از هر نقطه به هر نقطه وجود دارد که به دنبال همه قوس ها در جهتی است که آنها نشان می دهند. یک جز weak ضعیف یک زیرگراف حداکثر است که اگر جهت قوس ها را نادیده بگیریم متصل می شود.

برش نقطه ای است که حذف آن از نمودار باعث افزایش تعداد اجزا می شود. یعنی بعضی از نکات را از بعضی دیگر غیرقابل دسترسی می کند. نمودار را قطع می کند.

cutset مجموعه نقاطی است که حذف آنها باعث افزایش تعداد اجزای نمودار می شود. حداقل برش وزن شامل کوچکترین مجموعه نقاط است که برای جدا کردن نمودار باید حذف شود. به تعداد نقاط در برش حداقل وزن ، اتصال نقطه ای یک نمودار گفته می شود. اگر یک نمودار دارای یک برش باشد ، اتصال نمودار 1 است. حداقل تعداد نقاط جدا کننده دو نقطه غیرهمجوار s و t نیز حداکثر تعداد مسیرهای جدا از همدیگر بین s و t است.

پل لبه ای است که حذف آن از نمودار باعث افزایش تعداد اجزا می شود (نمودار را قطع می کند). برش لبه به مجموعه ای از لبه ها گفته می شود که با جدا شدن آنها نمودار جدا می شود. پل محلی از درجه k لبه ای است که حذف آن باعث می شود فاصله بین نقاط انتهایی لبه حداقل k باشد. اتصال لبه ای نمودار حداقل تعداد خطوطی است که با حذف آن نمودار قطع می شود. حداقل تعداد لبه های جدا کننده دو نقطه غیرهمجوار s و t همچنین حداکثر تعداد مسیرهای جدا از لبه بین s و t است.

منبع

http://www.analytictech.com/networks/graphtheory.htm