علم بيانات الرسم البياني باستخدام Python / NetworkX

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

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

تمكننا بنية بيانات الرسم البياني هذه من مراقبة البيانات من زوايا فريدة ، وهذا هو سبب استخدام علم بيانات الرسم البياني في كل مجال من البيولوجيا الجزيئية إلى العلوم الاجتماعية:

إذن كيف يمكن للمطورين الاستفادة من علم بيانات الرسم البياني؟ دعنا ننتقل إلى لغة برمجة علوم البيانات الأكثر استخدامًا: Python.

الشروع في استخدام الرسوم البيانية "نظرية الرسم البياني" في بايثون

يمتلك مطورو Python العديد من مكتبات بيانات الرسم البياني المتاحة لهم ، مثل NetworkX و igraph و SNAP وأداة الرسم البياني. وبغض النظر عن الإيجابيات والسلبيات ، فإن لديهم واجهات متشابهة جدًا للتعامل مع هياكل بيانات الرسم البياني لبايثون ومعالجتها.

سنستخدم مكتبة NetworkX الشهيرة. إنه سهل التثبيت والاستخدام ، ويدعم خوارزمية اكتشاف المجتمع التي سنستخدمها.

يعد إنشاء رسم بياني جديد باستخدام NetworkX أمرًا بسيطًا:

 import networkx as nx G = nx.Graph()

لكن G ليس رسمًا بيانيًا كبيرًا حتى الآن ، حيث يخلو من العقد والحواف.

كيفية إضافة العقد إلى الرسم البياني

يمكننا إضافة عقدة إلى الشبكة عن طريق تسلسل القيمة المرجعة لـ Graph() مع .add_node() (أو .add_nodes_from() لعقد متعددة في قائمة). يمكننا أيضًا إضافة خصائص أو سمات عشوائية إلى العقد عن طريق تمرير قاموس كمعامل ، كما نوضح في node 4 node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

سينتج هذا:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

ولكن بدون حواف بين العقد ، يتم عزلها ، ومجموعة البيانات ليست أفضل من جدول بسيط.

كيفية إضافة الحواف إلى الرسم البياني

على غرار تقنية العقد ، يمكننا استخدام .add_edge() مع أسماء عقدتين كمعلمات (أو .add_edges_from() لحواف متعددة في القائمة) ، وتضمين قاموسًا للسمات اختياريًا:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

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

تسرد NetworkX جميع الحواف عند استخدام الحواف G.edges ، ولكنها لا تتضمن سماتها. إذا أردنا سمات الحافة ، فيمكننا استخدام G[node_name] للحصول على كل ما هو متصل بالعقدة أو G[node_name][connected_node_name] للحصول على سمات حافة معينة:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

سينتج هذا:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

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

كيفية إنشاء الصور من الرسوم البيانية (والرسوم البيانية الموزونة)

يعد تصور الرسم البياني أمرًا ضروريًا: فهو يتيح لنا رؤية العلاقات بين العقد وهيكل الشبكة بسرعة ووضوح.

كل ما يتطلبه الأمر هو إجراء مكالمة سريعة إلى nx.draw(G) :

لنجعل الحواف الأثقل سمكًا بالمقابل من خلال استدعاء nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

قدمنا ​​سمكًا افتراضيًا للحواف الخالية من الوزن ، كما هو موضح في النتيجة:

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

علم بيانات الرسم البياني باستخدام البيانات من فيلم Star Wars: الحلقة الرابعة

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

ملاحظة: مجموعة البيانات مأخوذة من Gabasova، E. (2016). شبكة Star Wars الاجتماعية. DOI: https://doi.org/10.5281/zenodo.1411479.

أولاً ، سوف نتخيل البيانات باستخدام nx.draw(G_starWars, with_labels = True) :

تظهر الأحرف التي تظهر معًا عادةً ، مثل R2-D2 و C-3PO ، مرتبطة بشكل وثيق. في المقابل ، يمكننا أن نرى أن دارث فيدر لا يشارك المشاهد مع أوين.

تخطيطات تصور Python NetworkX

لماذا تقع كل عقدة في مكانها في الرسم البياني السابق؟

إنها نتيجة خوارزمية spring_layout الافتراضية. إنه يحاكي قوة الزنبرك ، ويجذب العقد المتصلة ويصد العقد المنفصلة. يساعد هذا في إبراز العقد جيدة التوصيل ، والتي تنتهي في المركز.

يحتوي NetworkX على تخطيطات أخرى تستخدم معايير مختلفة لوضع العقد ، مثل circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

النتائج:

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

كلا التخطيطين اللذين رأيناهما بهما درجة من الفوضى المرئية لأن الحواف حرة في عبور الحواف الأخرى. لكن Kamada-Kawai ، وهي خوارزمية أخرى موجهة بقوة مثل spring_layout ، تضع العقد لتقليل طاقة النظام.

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

هذا واحد لديه وظيفة السحب المتخصصة:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

ينتج هذا الشكل بدلاً من ذلك:

بدون أي تدخل خاص ، وضعت الخوارزمية الشخصيات الرئيسية (مثل Luke و Leia و C-3PO) في المركز ، وأخرى أقل شهرة (مثل Camie و General Dodonna) على الحدود.

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

تحليل العقدة: الدرجة ونظام ترتيب الصفحات

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

أحد المقاييس الأساسية للعقدة هو درجتها: عدد الحواف التي تحتوي عليها. درجة عقدة شخصية حرب النجوم تقيس عدد الشخصيات الأخرى التي شاركوا المشهد معها.

يمكن أن تحسب وظيفة degree() درجة الحرف أو الشبكة بأكملها:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

إخراج كلا الأمرين:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

يمكن فرز العقد من الأعلى إلى الأدنى وفقًا للدرجة بسطر واحد من التعليمات البرمجية:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

الإخراج:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

كونها كلية فقط ، لا تأخذ الدرجة في الحسبان تفاصيل الحواف الفردية. هل تتصل حافة معينة بعقدة معزولة بطريقة أخرى أو بعقدة متصلة بالشبكة بأكملها؟ تجمع خوارزمية PageRank من Google هذه المعلومات لقياس مدى "أهمية" العقدة في الشبكة.

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

سيكون لهذه العقد ترتيب صفحات أعلى ، يمكننا حسابه باستخدام مكتبة NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

هذا يطبع رتبة لوقا وشخصياتنا مرتبة حسب الرتبة:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

أوين هو الشخصية التي حصلت على أعلى تصنيف للصفحات متجاوزةً لوك الذي حصل على أعلى درجة. التحليل: على الرغم من أن أوين ليس الشخصية التي تشارك معظم المشاهد مع الشخصيات الأخرى ، إلا أنه شخصية تشارك المشاهد مع العديد من الشخصيات المهمة مثل Luke نفسه و R2-D2 و C-3PO.

في تناقض أكبر ، فإن C-3PO ، الشخصية الحاصلة على ثالث أعلى درجة ، هي الشخصية الأقل ترتيبًا للصفحات. على الرغم من وجود العديد من الاتصالات لـ C-3PO ، إلا أن الكثير منها يحتوي على شخصيات غير مهمة.

الخلاصة: يمكن أن يوفر استخدام مقاييس متعددة نظرة أعمق للخصائص المختلفة لعقد الرسم البياني.

خوارزميات اكتشاف المجتمع

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

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

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

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

باستخدام مكتبة NetworkX ، يتطلب تشغيل هذه الخوارزمية ثلاثة أسطر فقط من Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

الإخراج:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

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

رؤى ذكية باستخدام علم بيانات الرسم البياني في بايثون

لقد رأينا أن البدء في استخدام أدوات علم بيانات الرسم البياني أكثر وضوحًا مما قد يبدو. بمجرد تمثيل البيانات كرسم بياني باستخدام مكتبة NetworkX في Python ، يمكن أن تضيء بضعة أسطر قصيرة من التعليمات البرمجية. يمكننا تصور مجموعة البيانات الخاصة بنا ، وقياس ومقارنة خصائص العقد ، والعقد العنقودية بشكل معقول عبر خوارزميات اكتشاف المجتمع.

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

يوصى بالقراءة في علم بيانات الرسم البياني

خوارزميات اكتشاف المجتمع
تشاو يانغ ورينيه ألجشايمر وكلاوديو تيسوني. "تحليل مقارن لخوارزميات اكتشاف المجتمع على الشبكات الاصطناعية." التقارير العلمية ، 6 ، لا. 30750 (2016).

التعلم العميق على الرسم البياني
توماس كيبف. "الشبكات التلافيفية للرسم البياني." 30 سبتمبر 2016.

تطبيقات علم بيانات الرسم البياني
ألبانيز وفيديريكو ولياندرو لومباردي وإستيبان فويرستين وبابلو بالينزويلا. "توقع تحول الأفراد باستخدام التنقيب عن النص والتعلم الآلي للرسم البياني على Twitter." (24 أغسطس 2020): arXiv: 2008.10749 [cs.SI].

كوهين ، إليور. "لقاء PyData Tel Aviv: Node2vec." موقع يوتيوب. 22 نوفمبر 2018. فيديو 21:09. https://www.youtube.com/watch؟v=828rZgV9t1g.