بالبحث العلمي نظرية الرسم البياني ليست كافية

ايهاب محمد زايد-مصر

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

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

 ضع في اعتبارك محاولة صياغة نموذج شبكي للتربية. من الواضح أن كل والد له صلة بالطفل ، ولكن العلاقة الأبوية ليست مجرد مجموع الرابطين ، كما قد تمثلها نظرية الرسم البياني. الشيء نفسه ينطبق على محاولة نمذجة ظاهرة مثل ضغط الأقران.

 نحن نعلم الآن أن الشبكة هي مجرد ظل للشيء.

 “هناك العديد من النماذج البديهية. قالت ليوني نيوهاوسر من جامعة آر دبليو تي أتش آخن في ألمانيا: “إن تأثير ضغط الأقران على الديناميكيات الاجتماعية لا يتم تسجيله إلا إذا كان لديك بالفعل مجموعات في بياناتك”. لكن الشبكات الثنائية لا تلتقط تأثيرات المجموعة.

 يستخدم علماء الرياضيات وعلماء الكمبيوتر مصطلح “تفاعلات الرتبة العليا” لوصف هذه الطرق المعقدة التي يمكن أن تؤثر فيها ديناميكيات المجموعة ، بدلاً من الروابط الثنائية ، على السلوكيات الفردية. تظهر هذه الظواهر الرياضية في كل شيء من تفاعلات التشابك في ميكانيكا الكم إلى مسار انتشار المرض عبر السكان. إذا أراد عالم الصيدلة أن يصمم نموذجًا للتفاعلات الدوائية ، على سبيل المثال ، فقد تُظهر نظرية الرسم البياني كيف يستجيب دواءان لبعضهما البعض – ولكن ماذا عن ثلاثة؟ أم أربعة؟

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

 قال غروشو: “نحن نعلم الآن أن الشبكة هي مجرد ظل للشيء”. إذا كانت مجموعة البيانات تحتوي على بنية أساسية معقدة ، فإن نمذجةها كرسم بياني قد يكشف فقط عن إسقاط محدود للقصة بأكملها.

 تشعر إميلي بورفين من مختبر شمال غرب المحيط الهادئ الوطني بالإثارة حول قوة الأدوات مثل الرسوم البيانية الفائقة لرسم خرائط أكثر دقة بين نقاط البيانات.

 قالت عالمة الرياضيات إميلي بورفين من مختبر شمال غرب المحيط الهادئ الوطني: “لقد أدركنا أن هياكل البيانات التي استخدمناها لدراسة الأشياء ، من منظور رياضي ، ليست مناسبة تمامًا لما نراه في البيانات”.

 وهذا هو السبب في أن علماء الرياضيات وعلماء الكمبيوتر والباحثين الآخرين يركزون بشكل متزايد على طرق تعميم نظرية الرسم البياني – في أشكالها العديدة – لاستكشاف الظواهر ذات الترتيب الأعلى. جلبت السنوات القليلة الماضية سيلًا من الطرق المقترحة لوصف هذه التفاعلات ، والتحقق منها رياضيًا في مجموعات البيانات عالية الأبعاد.

 بالنسبة إلى Purvine ، فإن الاستكشاف الرياضي للتفاعلات عالية المستوى يشبه رسم خرائط لأبعاد جديدة. قالت “فكر في الرسم البياني كأساس على قطعة أرض ثنائية الأبعاد”. يمكن أن تختلف المباني ثلاثية الأبعاد التي يمكن أن ترتفع بشكل كبير. “عندما تكون في مستوى سطح الأرض ، فإنها تبدو متشابهة ، لكن ما تقوم بإنشائه في الأعلى مختلف.”

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

 هذا جيد ، ولكن لا يزال هناك الكثير الذي لا نعرفه عن كيفية ارتباط هذه الهياكل بنظيراتها التقليدية. يتعلم علماء الرياضيات حاليًا قواعد نظرية الرسم البياني التي تنطبق أيضًا على التفاعلات عالية المستوى ، مما يشير إلى مجالات جديدة للاستكشاف.

 هذا هو نوع القوة التي نراها من الرسوم البيانية العالية لتتجاوز الرسوم البيانية.

 

 لتوضيح أنواع العلاقة التي يمكن للرسم البياني التشعبي استخلاصها من مجموعة البيانات الضخمة – ولا يمكن للرسم البياني العادي – يشير Purvine إلى مثال بسيط قريب من المنزل ، وهو عالم النشر العلمي.

  تخيل مجموعتين من البيانات ، تحتوي كل منهما على أوراق بحثية شارك في تأليفها ما يصل إلى ثلاثة علماء رياضيات ؛ للتبسيط ، دعنا نسميها A و B و C. تحتوي مجموعة بيانات واحدة على ستة أوراق ، مع ورقتين من كل من الأزواج الثلاثة المتميزة (AB و AC و BC). يحتوي الآخر على ورقتين فقط ، كل منهما شارك في تأليفها علماء الرياضيات الثلاثة (ABC).

 قد يبدو تمثيل الرسم البياني للتأليف المشترك ، المأخوذ من أي من مجموعتي البيانات ، على شكل مثلث ، يوضح أن كل عالم رياضيات (ثلاث عقد) قد تعاون مع الاثنين الآخرين (ثلاثة روابط). قال بورفين إذا كان سؤالك الوحيد هو من الذي تعاون مع من ، فلن تحتاج إذن إلى رسم بياني

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

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

 قال بورفين: “هذا هو نوع القوة التي نراها من الرسم البياني الفائق ، للذهاب إلى ما هو أبعد من الرسوم البيانية”.

 ساعد أوستن بنسون من جامعة كورنيل مؤخرًا في تصميم نماذج لركوب سيارات الأجرة في مدينة نيويورك باستخدام سلاسل ماركوف وموتور عالية المستوى. كانت النتائج أفضل من سلسلة Markov التقليدية ولكن لا يزال بإمكانها استخدام التحسين.

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

 ولكن ماذا عن قطع الخط الفائق؟ قال أوستن بنسون ، عالم رياضيات في جامعة كورنيل: “هناك الكثير من الطرق لتعميم فكرة القطع إلى الرسم البياني العالي”. لكنه قال إنه لا يوجد حل واحد واضح ، لأنه يمكن قطع طرق مختلفة ، وإنشاء مجموعات جديدة من العقد.

 حاول بنسون مؤخرًا مع اثنين من زملائه إضفاء الطابع الرسمي على جميع الطرق المختلفة لتقسيم الرسم البياني. ما وجدوه يلمح إلى مجموعة متنوعة من التعقيدات الحسابية: في بعض المواقف ، تم حل المشكلة بسهولة في وقت متعدد الحدود ، مما يعني في الأساس أن الكمبيوتر يمكنه حل الحلول في وقت معقول. لكن بالنسبة للآخرين ، كانت المشكلة في الأساس غير قابلة للحل – كان من المستحيل معرفة ما إذا كان الحل موجودًا على الإطلاق.

 قال بينسون: “لا يزال هناك العديد من الأسئلة المفتوحة”. “بعض نتائج الاستحالة هذه مثيرة للاهتمام لأنه لا يمكنك اختصارها إلى الرسوم البيانية. وعلى الجانب النظري ، إذا لم تختصرها إلى شيء كان من الممكن أن تجده في الرسم البياني ، فهذا يظهر لك أن هناك شيئًا جديدًا هناك “.

 شطيرة الرياضيات

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

 يسمي الطوبولوجيون هذه الهياكل مجمعات بسيطة. هذه ، بشكل فعال ، هي hypergraphs ينظر إليها من خلال إطار عمل الطوبولوجيا. تقدم الشبكات العصبية ، التي تندرج ضمن الفئة العامة للتعلم الآلي ، مثالًا معبرًا.

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

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

 لكن هذا ليس هو الحال دائمًا. قال بورفين: “ما نراه الآن هو أن البيانات تقع في هذه الأرضية الوسطية حيث لا يكون كل تفاعل مفرط ، وليس كل تفاعل معقد ، بنفس الحجم مثل أي تفاعل آخر”. “يمكن أن يكون لديك تفاعل ثلاثي ، ولكن ليس التفاعلات المزدوجة.” أظهرت مجموعات البيانات الضخمة بوضوح أن تأثير المجموعة غالبًا ما يتجاوز تأثير الفرد ، سواء في شبكات الإشارات البيولوجية أو في السلوكيات الاجتماعية مثل ضغط الأقران.

 يصف Purvine البيانات بأنها تملأ منتصف نوع من الشطيرة الرياضية ، مرتبطة في الأعلى بهذه الأفكار من الطوبولوجيا ، وأسفلها قيود الرسوم البيانية. يواجه منظرو الشبكات الآن تحديًا للعثور على القواعد الجديدة للتفاعلات عالية المستوى. وبالنسبة لعلماء الرياضيات ، قالت ، “هناك مجال للعب”.

 مناحي ومصفوفات عشوائية

 يمتد هذا الإحساس “باللعب” الإبداعي ليشمل أدوات أخرى أيضًا. قال بنسون إن هناك كل أنواع الروابط الجميلة بين الرسوم البيانية والأدوات الأخرى لوصف البيانات. “ولكن بمجرد أن تنتقل إلى إعداد الترتيب الأعلى ، يصعب الحصول على هذه الاتصالات.”

 هذا واضح بشكل خاص عندما تحاول التفكير في نسخة ذات أبعاد أعلى من سلسلة ماركوف ، على حد قوله. تصف سلسلة ماركوف عملية متعددة المراحل تعتمد فيها المرحلة التالية فقط على الوضع الحالي للعنصر ؛ استخدم الباحثون نماذج ماركوف لوصف كيفية تدفق أشياء مثل المعلومات والطاقة وحتى الأموال عبر النظام. 

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

 ولكن كيف ترفع من مستوى شيء بسيط مثل المشي؟ يلجأ الباحثون إلى سلاسل ماركوف ذات الترتيب الأعلى ، والتي بدلاً من الاعتماد فقط على الموقع الحالي يمكنها النظر في العديد من الحالات السابقة. أثبت هذا النهج أنه مفيد لنمذجة الأنظمة مثل سلوك تصفح الويب وتدفقات حركة المرور في المطار. 

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

 استمرار الاضطراب في الرسوم البيانية الأكبر حجمًا ، اكتشافات جديدة لإثبات الرياضيات

 

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

 الموترات ليست شيئًا جديدًا بالنسبة للفيزيائيين ، الذين استخدموها منذ فترة طويلة لوصف ، على سبيل المثال ، الحالات الكمومية المختلفة الممكنة للجسيم ، لكن نظريي الشبكة اعتمدوا هذه الأداة للتوسع في قوة المصفوفات في مجموعات البيانات عالية الأبعاد. ويستخدمها علماء الرياضيات لفتح فئات جديدة من المشاكل. يستخدم Grochow الموترات لدراسة مشكلة التماثل ، والتي تسأل بشكل أساسي كيف تعرف ما إذا كان هناك شيئان متماثلان بطريقة ما. أنتج عمله الأخير مع Youming Qiao طريقة جديدة لتحديد المشكلات المعقدة التي قد يكون من الصعب أو المستحيل حلها.

 

 يطرح نموذج سيارات الأجرة غير الحاسم لبنسون سؤالاً واسع الانتشار: متى يحتاج الباحثون فعلاً إلى أدوات مثل الرسم البياني الفائق؟ في كثير من الحالات ، في ظل الظروف المناسبة ، يقدم الرسم البياني التشعبي نفس النوع من التنبؤات والتحليلات تمامًا مثل الرسم البياني. “إذا تم تغليف شيء ما بالفعل في الشبكة ، فهل من الضروري حقًا تصميم النظام [على أنه ترتيب أعلى]؟” سأل مايكل شواب من جامعة آر دبليو تي أتش آخن.

 وقال إن ذلك يعتمد على مجموعة البيانات. “الرسم البياني هو تجريد جيد لشبكة اجتماعية ، لكن الشبكات الاجتماعية أكثر من ذلك بكثير. مع أنظمة الترتيب الأعلى ، هناك المزيد من الطرق للنمذجة “. قد تُظهر نظرية الرسم البياني كيفية ارتباط الأفراد ، على سبيل المثال ، ولكنها لا توضح الطرق التي تؤثر بها مجموعات الأصدقاء على وسائل التواصل الاجتماعي على سلوك بعضهم البعض.

 لن تظهر نفس التفاعلات ذات الترتيب الأعلى في كل مجموعة بيانات ، لذا فإن النظريات الجديدة ، بشكل مثير للفضول ، مدفوعة بالبيانات – التي تتحدى الحس المنطقي الأساسي الذي جذب Purvine إلى المجال في المقام الأول. “ما أحبه في الرياضيات هو أنها تستند إلى المنطق وإذا اتبعت الاتجاه الصحيح ، فستحصل على الإجابة الصحيحة. لكن في بعض الأحيان ، عندما تحدد مجالات جديدة تمامًا للرياضيات ، تكون هناك ذاتية ما هي الطريقة الصحيحة لفعل ذلك ، “كما تقول. “وإذا لم تدرك أن هناك طرقًا متعددة للقيام بذلك ، فيمكنك ربما قيادة المجتمع في الاتجاه الخاطئ.”

 قال غروشو إن هذه الأدوات تمثل في نهاية المطاف نوعًا من الحرية ، لا تسمح فقط للباحثين بفهم بياناتهم بشكل أفضل ، بل تسمح لعلماء الرياضيات وعلماء الكمبيوتر باستكشاف عوالم جديدة من الاحتمالات. “هناك أشياء لا حصر لها لاستكشافها. إنه مثير للاهتمام وجميل ، ومصدر للكثير من الأسئلة الرائعة “.