النمطية (الشبكات)

تُعدّ المعيارية مقياسًا لبنية الشبكات أو الرسوم البيانية ، حيث تقيس قوة تقسيم الشبكة إلى وحدات (تُسمى أيضًا مجموعات أو عناقيد أو مجتمعات). تتميز الشبكات ذات المعيارية العالية بوجود روابط كثيفة بين العقد داخل الوحدات، بينما تكون الروابط بين العقد في الوحدات المختلفة أقل كثافة. تُستخدم المعيارية غالبًا في أساليب التحسين للكشف عن بنية المجتمعات في الشبكات. تُظهر الشبكات البيولوجية، بما في ذلك أدمغة الحيوانات، درجة عالية من المعيارية. مع ذلك، فإن تعظيم المعيارية ليس متسقًا إحصائيًا، إذ يجد المجتمعات في نموذجه الصفري، أي الرسوم البيانية العشوائية تمامًا، وبالتالي لا يمكن استخدامه لإيجاد بنى مجتمعية ذات دلالة إحصائية في الشبكات التجريبية. علاوة على ذلك، فقد ثبت أن المعيارية تعاني من حدّ في الدقة، وبالتالي فهي غير قادرة على اكتشاف المجتمعات الصغيرة.

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

المعيارية هي نسبة الحواف التي تقع ضمن مجموعات معينة مطروحًا منها النسبة المتوقعة إذا تم توزيع الحواف عشوائيًا. تقع قيمة المعيارية للرسوم البيانية غير الموزونة وغير الموجهة ضمن النطاق التالي:${\displaystyle [-1/2,1]}$[ ^{3 ]} تكون القيمة موجبة إذا تجاوز عدد الروابط داخل المجموعات العدد المتوقع عشوائيًا. بالنسبة لتقسيم معين لرؤوس الشبكة إلى وحدات، تعكس خاصية التجزئة تركيز الروابط داخل الوحدات مقارنةً بالتوزيع العشوائي للروابط بين جميع العقد بغض النظر عن الوحدات ^.

توجد طرق مختلفة لحساب معامل التجزئة. ^{[ 1 ]} في النسخة الأكثر شيوعًا لهذا المفهوم، يتم إجراء عملية عشوائية للحواف للحفاظ على درجة كل رأس. لنفترض وجود رسم بياني مع${\displaystyle n}$العقد و${\displaystyle m}$الروابط ( الحواف ) بحيث يمكن تقسيم الرسم البياني إلى مجموعتين باستخدام متغير العضوية${\displaystyle s}$إذا كانت العقدة${\displaystyle v}$ينتمي إلى المجتمع 1،${\displaystyle s_{v}=1}$أو إذا${\displaystyle v}$ينتمي إلى المجتمع 2،${\displaystyle s_{v}=-1}$لنفترض أن مصفوفة التجاور للشبكة ممثلة بـ${\displaystyle A}$، أين${\displaystyle A_{vw}=0}$هذا يعني عدم وجود حافة (لا يوجد تفاعل) بين العقد.${\displaystyle v}$و${\displaystyle w}$و${\displaystyle A_{vw}=1}$هذا يعني وجود حافة بين الاثنين. ولتبسيط الأمر، نعتبر شبكة غير موجهة.${\displaystyle A_{vw}=A_{wv}}$(قد توجد حواف متعددة بين عقدتين، ولكننا هنا نقوم بتقييم أبسط حالة).

نمطية التصميم${\displaystyle Q}$ثم يتم تعريفها على أنها نسبة الحواف التي تقع ضمن المجموعة 1 أو 2، مطروحًا منها العدد المتوقع للحواف ضمن المجموعتين 1 و 2 لرسم بياني عشوائي له نفس توزيع درجة العقدة مثل الشبكة المعطاة.

يُحسب العدد المتوقع للحواف باستخدام مفهوم نموذج التكوين . ^{[ 4 ]} نموذج التكوين هو تمثيل عشوائي لشبكة معينة. بالنظر إلى شبكة ذات${\displaystyle n}$العقد، حيث كل عقدة${\displaystyle v}$له درجة عقدة${\displaystyle k_{v}}$يقوم نموذج التكوين بتقسيم كل حافة إلى نصفين، ثم يُعاد توصيل كل نصف حافة، يُسمى جذعًا ، عشوائيًا بأي جذع آخر في الشبكة، حتى أنه يسمح بوجود حلقات ذاتية (تحدث عند إعادة توصيل جذع بجذع آخر من نفس العقدة) وحواف متعددة بين نفس العقدتين. وبالتالي، على الرغم من أن توزيع درجة العقد في الرسم البياني يبقى كما هو، فإن نموذج التكوين ينتج عنه شبكة عشوائية تمامًا.

لنفترض الآن وجود عقدتين${\displaystyle v}$و${\displaystyle w}$، بدرجات العقدة${\displaystyle k_{v}}$و${\displaystyle k_{w}}$على التوالي، من شبكة معاد توصيلها عشوائياً كما هو موضح أعلاه. نحسب العدد المتوقع للحواف الكاملة بين هذه العقد.

دعونا نتناول كل واحد من${\displaystyle k_{v}}$أجزاء من العقدة${\displaystyle v}$وإنشاء متغيرات مؤشر مرتبطة بها${\displaystyle I_{i}^{(v,w)}}$من أجلهم،${\displaystyle i=1,\ldots ,k_{v}}$، مع${\displaystyle I_{i}^{(v,w)}=1}$إذا${\displaystyle i}$يتصل الفرع الفرعي رقم -th بأحد${\displaystyle k_{w}}$أجزاء من العقدة${\displaystyle w}$في هذا الرسم البياني العشوائي المحدد. إذا لم يكن كذلك، فـ${\displaystyle I_{i}^{(v,w)}=0}$منذ${\displaystyle i}$الجزء الفرعي رقم -th من العقدة${\displaystyle v}$يمكن الاتصال بأي من${\displaystyle 2m-1}$البقايا المتبقية باحتمالية متساوية (بينما${\displaystyle m}$(عدد الحواف في الرسم البياني الأصلي)، وبما أن هناك${\displaystyle k_{w}}$الوصلات التي يمكن أن تتصل بها والمرتبطة بالعقدة${\displaystyle w}$، على ما يبدو

${\displaystyle p(I_{i}^{(v,w)}=1)=E[I_{i}^{(v,w)}]={\frac {k_{w}}{2m-1}}}$

العدد الإجمالي للحواف الكاملة${\displaystyle J_{vw}}$بين${\displaystyle v}$و${\displaystyle w}$هو مجرد${\displaystyle J_{vw}=\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}}$إذن، القيمة المتوقعة لهذه الكمية هي

${\displaystyle E[J_{vw}]=E\left[\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}\right]=\sum _{i=1}^{k_{v}}E[I_{i}^{(v,w)}]=\sum _{i=1}^{k_{v}}{\frac {k_{w}}{2m-1}}={\frac {k_{v}k_{w}}{2m-1}}}$

ثم تُجري العديد من النصوص التقريبات التالية، بالنسبة للشبكات العشوائية ذات العدد الكبير من الحواف. عندما${\displaystyle m}$إذا كانت كبيرة، فإنهم يتخلون عن طرح${\displaystyle 1}$في المقام أعلاه، واستخدم ببساطة التعبير التقريبي${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$بالنسبة للعدد المتوقع للحواف بين عقدتين. بالإضافة إلى ذلك، في شبكة عشوائية كبيرة، يكون عدد الحلقات الذاتية والحواف المتعددة ضئيلاً للغاية. ^{[ 5 ]} إن تجاهل الحلقات الذاتية والحواف المتعددة يسمح بافتراض وجود حافة واحدة على الأكثر بين أي عقدتين. في هذه الحالة،${\displaystyle J_{vw}}$يصبح متغيرًا ثنائيًا، لذا فإن قيمته المتوقعة هي أيضًا احتمال أن يساوي${\displaystyle 1}$وهذا يعني أنه يمكن تقريب احتمال وجود حافة بين العقد.${\displaystyle v}$و${\displaystyle w}$مثل${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$.

وبالتالي، فإن الفرق بين العدد الفعلي للحواف بين العقدة${\displaystyle v}$و${\displaystyle w}$وعدد الحواف المتوقع بينهما هو

${\displaystyle A_{vw}-{\frac {k_{v}k_{w}}{2m}}}$

بجمع جميع أزواج العقد نحصل على معادلة التنميط،${\displaystyle Q}$[ ^{1 ]​}

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]{\frac {s_{v}s_{w}+1}{2}}}$

3

تنطبق المعادلة 3 على التقسيم إلى مجموعتين فقط. يُعدّ التقسيم الهرمي (أي التقسيم إلى مجموعتين، ثم تقسيم المجموعتين الفرعيتين إلى مجموعتين فرعيتين أصغر لتحقيق أقصى قيمة لـ Q ) منهجًا ممكنًا لتحديد مجموعات متعددة في الشبكة. بالإضافة إلى ذلك، يمكن تعميم المعادلة (3) لتقسيم الشبكة إلى c مجموعة. ^{[ 6 ]}

${\displaystyle Q={\frac {1}{(2m)}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{(2m)}}\right]\delta (c_{v},c_{w})=\sum _{i=1}^{c}(e_{ii}-a_{i}^{2})}$

4

حيث يمثل e _ij نسبة الحواف التي يكون أحد طرفيها في المجموعة i والآخر في المجموعة j :

${\displaystyle e_{ij}=\sum _{vw}{\frac {A_{vw}}{2m}}1_{v\in c_{i}}1_{w\in c_{j}}}$

و a _i هي نسبة نهايات الحواف المتصلة بالرؤوس في المجموعة i :

${\displaystyle a_{i}={\frac {k_{i}}{2m}}=\sum _{j}e_{ij}}$

نحن نعتبر شبكة غير موجهة تحتوي على 10 عقد و 12 حافة ومصفوفة التجاور التالية.

يتم تمثيل المجتمعات في الرسم البياني بواسطة مجموعات العقد الحمراء والخضراء والزرقاء في الشكل 1. يتم تصوير تقسيمات المجتمع المثلى في الشكل 2.

يُمكن صياغة مفهوم النمطية بشكل بديل، وهو مفيد بشكل خاص في خوارزميات التحسين الطيفي، كما يلي: ^{[ 1 ]} تعريف${\displaystyle S_{vr}}$يكون${\displaystyle 1}$إذا كان الرأس${\displaystyle v}$ينتمي إلى المجموعة${\displaystyle r}$و${\displaystyle 0}$وإلا.

${\displaystyle \delta (c_{v},c_{w})=\sum _{r}S_{vr}S_{wr}}$

وبالتالي

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\sum _{r}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]S_{vr}S_{wr}={\frac {1}{2m}}\mathrm {Tr} (\mathbf {S} ^{\mathrm {T} }\mathbf {BS} ),}$

أين${\displaystyle S}$هي المصفوفة (غير المربعة) التي تحتوي على عناصر${\displaystyle S_{v}}$و${\displaystyle B}$هي ما يسمى بمصفوفة النمطية، والتي تحتوي على عناصر

${\displaystyle B_{vw}=A_{vw}-{\frac {k_{v}k_{w}}{2m}}.}$

مجموع جميع صفوف وأعمدة مصفوفة التجزئة يساوي صفرًا، مما يعني أن تجزئة الشبكة غير المقسمة تكون دائمًا كذلك.${\displaystyle 0}$.

بالنسبة للشبكات المقسمة إلى مجتمعين فقط، يمكن تعريفها بشكل بديل على النحو التالي:${\displaystyle s_{v}=\pm 1}$للإشارة إلى المجتمع الذي تنتمي إليه العقدة${\displaystyle v}$ينتمي، مما يؤدي بعد ذلك إلى

${\displaystyle Q={1 \over 4m}\sum _{vw}B_{vw}s_{v}s_{w}={1 \over 4m}\mathbf {s} ^{\mathrm {T} }\mathbf {Bs} ,}$

أين${\displaystyle s}$هو متجه عمودي ذو عناصر${\displaystyle s_{v}}$[ ^{1 ]​}

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

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

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

هناك منهجان رئيسيان لمحاولة حل مشكلة حد الدقة ضمن سياق النمطية: الأول هو إضافة مقاومة r لكل عقدة، على شكل حلقة ذاتية ، مما يزيد ( r > 0 ) أو يقلل ( r < 0 ) من نفور العقد من تكوين مجتمعات؛ ^{[ 12 ]} أو إضافة مُعامل γ > 0 أمام حد الحالة الصفرية في تعريف النمطية، والذي يتحكم في الأهمية النسبية بين الروابط الداخلية للمجتمعات والنموذج الصفري. ^{[ 7 ]} من خلال تحسين النمطية لقيم هذه المُعاملات في نطاقاتها المناسبة، يُمكن استعادة النطاق المتوسط ​​الكامل للشبكة، من النطاق الكلي الذي تنتمي فيه جميع العقد إلى نفس المجتمع، إلى النطاق الجزئي الذي تُشكّل فيه كل عقدة مجتمعها الخاص، ومن هنا جاء اسم طرق الدقة المتعددة . ومع ذلك، فقد تبيّن أن لهذه الطرق قيودًا عندما تكون المجتمعات غير متجانسة الحجم للغاية. ^{[ 13 ]}

هناك عدد من أدوات البرمجيات المتاحة القادرة على حساب التجميعات في الرسوم البيانية ذات نمطية جيدة.

• التنفيذ الأصلي لطريقة لوفان متعددة المستويات . ^{[ 14 ]}
• خوارزمية ليدن التي تتجنب أيضًا المجتمعات غير المتصلة. ^{[ 15 ]}
• خوارزمية فيينا لتجميع الرسوم البيانية (VieClus)، وهي خوارزمية ميمية متوازية. ^{[ 16 ]}

• شبكة معقدة
• بنية المجتمع
• نموذج فارغ
• نظرية الترشيح