شبكة متفرقة

في علم الشبكات ، تحتوي الشبكة المتفرقة على عدد روابط أقل بكثير من الحد الأقصى الممكن للروابط داخلها (والعكس صحيح، أي الشبكة الكثيفة ). وتُعد دراسة الشبكات المتفرقة مجالًا حديثًا نسبيًا، وقد حفزتها في المقام الأول دراسة الشبكات الحقيقية، مثل الشبكات الاجتماعية وشبكات الحاسوب. ^{[ 1 ]}

إن مفهوم الروابط الأقل بكثير هو، بطبيعة الحال، مفهوم عامي وغير رسمي. ورغم إمكانية وضع عتبة لشبكة معينة، إلا أنه لا توجد عتبة عالمية تحدد المعنى الحقيقي لمصطلح "الروابط الأقل بكثير" . ونتيجة لذلك، لا يوجد مفهوم رسمي للتباعد في أي شبكة محدودة، على الرغم من الاتفاق الواسع على أن معظم الشبكات التجريبية متفرقة بالفعل. ومع ذلك، يوجد مفهوم رسمي للتباعد في حالة نماذج الشبكات اللانهائية، ويتحدد هذا المفهوم من خلال سلوك عدد الحواف (L) و/أو متوسط ​​الدرجة ( ⟨k⟩ ) عندما يؤول عدد العقد (N) إلى اللانهاية. ^{[ 2 ]}

شبكة بسيطة غير موزونة بحجم${\displaystyle N}$ يُطلق عليها اسم متفرقة إذا كان عدد الروابط${\displaystyle L}$وهو أصغر بكثير من الحد الأقصى الممكن لعدد الروابط${\displaystyle L_{max}}$: ^{[ 1 ]}

${\displaystyle L\ll L_{max}={N \choose 2}}$.

في أي شبكة (حقيقية) معينة، يكون عدد العقد N وعدد الروابط L مجرد رقمين، وبالتالي فإن معنى الإشارة الأصغر بكثير (${\displaystyle \ll }$العبارة المذكورة أعلاه هي عبارة عامية وغير رسمية تمامًا، وكذلك عبارات مثل "العديد من الشبكات الحقيقية متفرقة".

لكن إذا تعاملنا مع سلسلة رسوم بيانية اصطناعية${\displaystyle G_{N}}$أو نموذج شبكة محدد جيدًا للشبكات${\displaystyle G_{N}}$من أي حجم N = 1، 2، ...،${\displaystyle \infty }$ثم الـ${\displaystyle \ll }$ويكتسب معناه الرسمي المعتاد:

${\displaystyle L\ll L_{max}\iff L=o(L_{max})\iff \lim _{N\rightarrow \infty }{\frac {L}{L_{max}}}=0}$.

بمعنى آخر، تسلسل أو نموذج شبكي${\displaystyle G_{N}}$يُطلق عليها اسم كثيفة أو متفرقة اعتمادًا على ما إذا كان متوسط ​​الدرجة (المتوقع)${\displaystyle \langle k\rangle =2L/N}$في${\displaystyle G_{N}}$يتناسب خطيًا أو دون خطيًا مع N : ^{[ 2 ] [ 3 ]}

${\displaystyle G_{N}}$ كثيف إذا​${\displaystyle \langle k\rangle =O(N)}$;

${\displaystyle G_{N}}$ تكون متفرقة إذا${\displaystyle \langle k\rangle =o(N)}$.

تُعدّ الشبكات التي يكون متوسط ​​درجتها ثابتًا أو يتقارب إلى قيمة ثابتة فئة فرعية مهمة من الشبكات المتفرقة. ويُطلق بعض المؤلفين على هذه الشبكات فقط اسم الشبكات المتفرقة، بينما يُخصّص لها آخرون أسماءً خاصة: ^{[ 4 ]}

${\displaystyle G_{N}}$ تكون نادرة حقًا أو نادرة للغاية أو نادرة جدًا إذا${\displaystyle \langle k\rangle =O(1)}$.

توجد أيضًا تعريفات بديلة وأكثر صرامة لقلة كثافة الشبكة تتطلب تقارب توزيع الدرجات في${\displaystyle G_{N}}$إلى حد محدد جيدًا عند${\displaystyle N\rightarrow \infty }$[ ^{5 ]} وفقًا لهذا التعريف، فإن الرسم ^{البياني} ذو النجمة N${\displaystyle S_{N}}$على سبيل المثال، ليس متفرقًا.

يتغير توزيع درجات العقد مع ازدياد الترابط. وتختلف توزيعات درجات العقد باختلاف كثافة الروابط في الشبكات المعقدة، كما يشير تحليل شبكة فليكر. ^{[ 6 ]} تتميز الشبكات ذات الترابط المتباعد بتوزيع لا يعتمد على المقياس، ويخضع لقانون القوة . ومع ازدياد الترابط، يزداد انحراف الشبكات عن قانون القوة. ومن أهم العوامل المؤثرة على ترابط الشبكة تشابه العقد . فعلى سبيل المثال، في الشبكات الاجتماعية ، يميل الأشخاص إلى الارتباط ببعضهم البعض إذا كانوا يتشاركون خلفية اجتماعية مشتركة، أو اهتمامات، أو أذواق، أو معتقدات، وما إلى ذلك. وفي سياق الشبكات البيولوجية، ترتبط البروتينات أو الجزيئات الأخرى إذا كانت أسطحها المعقدة متطابقة تمامًا أو متكاملة. ^{[ 6 ]}

إذا لم تُوزن العقد في الشبكات، يُمكن تمثيل المكونات الهيكلية للشبكة باستخدام مصفوفة التجاور . إذا كانت أغلب عناصر المصفوفة أصفارًا، تُسمى هذه المصفوفة بالمصفوفة المتفرقة . في المقابل، إذا كانت أغلب العناصر غير صفرية، تُسمى المصفوفة بالمصفوفة الكثيفة . تُحدد كثافة أو تفرق المصفوفة بنسبة العناصر الصفرية إلى إجمالي عدد عناصرها. وبالمثل، في سياق نظرية الرسوم البيانية ، إذا كان عدد الروابط قريبًا من الحد الأقصى، يُعرف الرسم البياني بالرسم البياني الكثيف . أما إذا كان عدد الروابط أقل من الحد الأقصى، فيُسمى هذا النوع من الرسوم البيانية بالرسم البياني المتفرق . ^{[ 7 ]}

تُستخدم الشبكات المتفرقة في الشبكات الاجتماعية والحاسوبية والبيولوجية ، كما تُستخدم تطبيقاتها في النقل وشبكات نقل الطاقة وشبكات الاستشهاد، وغيرها. ونظرًا لأن معظم الشبكات الحقيقية كبيرة ومتفرقة، فقد طُوّرت نماذج عديدة لفهمها وتحليلها. ^{[ 8 ]} وقد ألهمت هذه الشبكات تصميم الشبكات المتفرقة على رقاقة في هندسة الحواسيب المدمجة متعددة المعالجات .

تُسهم الشبكات المتفرقة أيضًا في تقليل العمليات الحسابية من خلال جعل تخزين الشبكة كقائمة مجاورة أكثر كفاءة من تخزينها كمصفوفة مجاورة . على سبيل المثال، عند استخدام قائمة مجاورة، يمكن إتمام عملية المرور على جيران عقدة ما في زمن قدره O(L/N)، بينما يتم ذلك في زمن قدره O(N) باستخدام مصفوفة مجاورة. ^{[ 2 ]}