أحد "أكثر الموارد قيمة في أي شبكة اجتماعية هو" مخطط الصداقات "- يتم نشر المعلومات من خلال الاتصالات في هذا العمود ، ويتم إرسال محتوى مثير للاهتمام للمستخدمين ، ويتم إرسال تعليقات بناءة إلى مؤلفي المحتوى. في الوقت نفسه ، يعد الرسم البياني أيضًا مصدرًا مهمًا للمعلومات التي تساعد على فهم المستخدم بشكل أفضل وتحسين الخدمة باستمرار. ومع ذلك ، في تلك الحالات التي ينمو فيها الرسم البياني ، يكون استخراج المعلومات منه أكثر صعوبة تقنيًا. في هذه المقالة سوف نتحدث عن بعض الحيل المستخدمة لمعالجة الرسوم البيانية الكبيرة في OK.ru.
للبدء ، فكر في مهمة بسيطة من العالم الواقعي: حدد عمر المستخدم. تتيح معرفة العمر للشبكة الاجتماعية تحديد محتوى أكثر صلة والتكيف بشكل أفضل مع الشخص. يبدو أنه قد تمت الإشارة إلى العمر بالفعل عند إنشاء صفحة على الشبكات الاجتماعية ، ولكن في الواقع ، في كثير من الأحيان ، يكون المستخدمون أذكياء ويشيرون إلى عصر مختلف عن العمر الحقيقي. يمكن أن يساعد الرسم البياني الاجتماعي في تصحيح الموقف :).
لنأخذ ، على سبيل المثال ، بوب (جميع الشخصيات في المقال خيالية ، أي مصادفة مع الواقع هي نتيجة إبداع منزل عشوائي):
من ناحية ، نصف أصدقاء بوب هم من المراهقين ، مما يشير إلى أن بوب هو أيضًا مراهق. لكن لديه أيضًا أصدقاء أكبر سناً ، لذا فإن الثقة في الإجابة منخفضة. يمكن أن تساعد المعلومات الإضافية من الرسم البياني الاجتماعي في توضيح الإجابة:
مع الأخذ في الاعتبار ، ليس فقط الأقواس التي يشارك فيها بوب بشكل مباشر ، ولكن أيضًا الأقواس بين أصدقائه ، يمكننا أن نرى أن بوب جزء من مجتمع كثيف من المراهقين ، والذي يسمح لنا بالوصول إلى استنتاج حول عمره بدرجة أكبر من الثقة.
تُعرف بنية البيانات هذه باسم شبكة الأنا أو الرسم البياني الفرعي للأنا ؛ لقد تم استخدامها بنجاح منذ وقت طويل في حل العديد من المشكلات: البحث عن المجتمعات ، وتحديد برامج التتبع والبريد العشوائي ، والتوصيات المقدمة من الأصدقاء والمحتوى ، إلخ. ومع ذلك ، فإن حساب الأنا من subgraph لجميع المستخدمين في الرسم البياني مع مئات الملايين من العقد وعشرات المليارات من الأقواس محفوف بعدد من "الصعوبات التقنية الصغيرة" :).
المشكلة الرئيسية هي أنه عند النظر في معلومات حول "الخطوة الثانية" في الرسم البياني ، يحدث انفجار تربيعي لعدد الاتصالات. على سبيل المثال ، بالنسبة للمستخدم الذي يحتوي على 150 رابطًا مباشرًا من الأنا ، قد يتضمن الرسم الفرعي ما يصل إلى 
الارتباطات ، وبالنسبة للمستخدم النشط الذي لديه 5000 صديق ، يمكن أن يزيد الرسم الفرعي للأنا إلى أكثر من 12،000،000 ارتباط.
المضاعفات الإضافية هي حقيقة أن الرسم البياني يتم تخزينه في بيئة موزعة ، وليس هناك أي عقدة تحتوي على صورة كاملة للرسم البياني في الذاكرة. يتم العمل على تقسيم الرسم البياني المتوازن في كل من الأكاديمية وفي الصناعة ، ولكن حتى أفضل النتائج عند جمع الرسم البياني الأنا يؤدي إلى التواصل "الكل مع الجميع": من أجل الحصول على معلومات حول أصدقاء أصدقاء المستخدم ، سيكون عليك الانتقال إلى جميع "الأقسام" في معظم الحالات.
سيكون أحد البدائل العاملة في هذه الحالة هو تكرار البيانات القسري (على سبيل المثال ، الخوارزمية 3 في مقال من Google ) ، ولكن هذا التكرار أيضًا غير مجاني. دعنا نحاول معرفة ما يمكن تحسينه في هذه العملية.
خوارزمية ساذجة
للبدء ، فكر في الخوارزمية "الساذجة" لإنشاء رسم تخطيطي فرعي:
تفترض الخوارزمية أن الرسم البياني الأصلي مخزّن كقائمة متجاورة ، أي يتم تخزين المعلومات حول جميع أصدقاء المستخدم في سجل واحد مع معرف المستخدم في المفتاح وقائمة أصدقاء الهوية في القيمة. من أجل اتخاذ الخطوة الثانية والحصول على معلومات حول الأصدقاء تحتاج:
- قم بتحويل رسم بياني إلى قائمة الحواف ، حيث كل حافة عبارة عن إدخال منفصل.
- اجعل قائمة الحواف متصلة بنفسها ، مما سيعطي كل المسارات في رسم بياني بطول 2.
- تجميع حسب بداية المسار.
في الإخراج لكل مستخدم ، نحصل على قوائم مسارات طول 2 لكل مستخدم. تجدر الإشارة هنا إلى أن البنية الناتجة هي في الواقع حي من خطوتين للمستخدم ، في حين أن الرسم البياني الفرعي ego هو مجموعته الفرعية. لذلك ، لاستكمال العملية ، نحتاج إلى تصفية جميع الأقواس التي تخرج من الأصدقاء المباشرين.
هذه الخوارزمية جيدة لأنها تنفذ في سطرين على Scala تحت Apache Spark . ولكن المزايا تنتهي عند هذا الحد: بالنسبة للرسم البياني للحجم الصناعي ، فإن حجم اتصالات الشبكة يتجاوز الحد ويتم قياس وقت التشغيل بالأيام. يتم إنشاء الصعوبة الرئيسية من خلال عمليتين خلطيتين تحدثان عندما ننضم إلى مجموعات وتجميعها. هل من الممكن تقليل كمية البيانات المرسلة؟
الرسم البياني الأنا في خلط ورق اللعب واحد
بالنظر إلى أن الرسم البياني الخاص بنا من الصداقات متماثل ، يمكنك استخدام التحسينات التي اقترحها توماس شانك :
- يمكنك الحصول على جميع المسارات بطول 2 دون الانضمام - إذا كان لدى بوب أصدقاء أليس وهاري ، فهناك مساران أليس-بوب-هاري وهاري بوب-أليس.
- عند التجميع ، يتوافق مساران عند المدخل مع الحافة الجديدة نفسها. يحتوي المسار Bob-Alice-Dave و Bob-Dave-Alice على نفس المعلومات الخاصة بـ Bob ، مما يعني أنه لا يمكنك إرسال سوى كل مسار ثانٍ ، مع فرز المستخدمين حسب هويتهم.
بعد تطبيق التحسينات ، سيبدو مخطط العمل كما يلي:
- في المرحلة الأولى من الجيل ، نحصل على قائمة بمسارات الطول 2 مع مرشح معرف الطلب.
- في الثانية ، نجمع بواسطة المستخدم الأول في الطريق.
في هذا الإعداد ، تفي الخوارزمية بعملية خلط ورق اللعب ، ويكون حجم البيانات المرسلة عبر الشبكة إلى النصف. :)
وضع المخطط الفرعي الأنا في الذاكرة
هناك مشكلة مهمة لم نأخذها في الاعتبار بعد وهي كيفية تحليل البيانات الموجودة في الأنا من صورة فرعية في الذاكرة. لتخزين الرسم البياني ككل ، استخدمنا قائمة المجاورة. هذا الهيكل مناسب للمهام حيث يكون من الضروري إجراء الرسم البياني النهائي ككل ، لكنه مكلف إذا أردنا إنشاء رسم بياني من القطع وعمل المزيد من التحليلات الدقيقة. يجب أن يؤدي الهيكل المثالي لمهمتنا بشكل فعال العمليات التالية:
- اتحاد اثنين من الرسوم البيانية التي تم الحصول عليها من أقسام مختلفة.
- الحصول على جميع أصدقاء الإنسان.
- التحقق من اتصال شخصين.
- التخزين في الذاكرة دون الملاكمة النفقات العامة.
أحد أنساق هذه المتطلبات هو التناظرية لمصفوفة CSR المتفرقة :
يتم تخزين الرسم البياني في هذه الحالة في شكل ثلاث صفائف:
- المستخدمين - مجموعة مصنفة مع معرف جميع المستخدمين المشاركين في الرسم البياني.
- الفهرس - صفيف بنفس حجم المستخدمين ، حيث يتم تخزين مؤشر لكل مؤشر على بداية معلومات حول علاقات المستخدم في الصفيف الثالث.
- الأصدقاء - مجموعة من الحجم تساوي عدد الحواف في الرسم البياني ، حيث يتم عرض معرفات المستخدمين ذوي الصلة بالتسلسل لمعرفات المقابلة من المستخدمين. يتم فرز المصفوفة لسرعة المعالجة داخل المعلومات حول روابط مستخدم واحد.
في هذا التنسيق ، يتم تنفيذ عملية دمج اثنين من الرسوم البيانية في الوقت الخطي ، وعملية الحصول على معلومات عن مستخدم معين أو على زوج من المستخدمين لكل لوغاريتم لعدد من الرؤوس. في هذه الحالة ، لا يعتمد مقدار الحمل الموجود في الذاكرة على حجم الرسم البياني ، حيث يتم استخدام عدد ثابت من الصفائف. بإضافة صفيف بيانات رابع بالحجم مساوٍ لحجم الأصدقاء ، يمكنك حفظ معلومات إضافية مرتبطة بالعلاقات في الرسم البياني.
باستخدام خاصية تناسق الرسم البياني ، يمكنك تخزين نصف أقواس "المثلث الأعلى" فقط (عندما يتم تخزين الأقواس فقط من معرف أصغر إلى معرف أكبر) ، ولكن في هذه الحالة ، ستستغرق عملية إعادة بناء جميع اتصالات مستخدم واحد وقتًا خطيًا. قد يكون الحل الوسط الجيد في هذه الحالة هو النهج الذي يستخدم الترميز "الثلاثي العلوي" للتخزين والنقل بين العقد ، والترميز المتماثل عند تحميل غرور الرسم البياني الفرعي في الذاكرة لتحليله.
تقليل خلط ورق اللعب
ومع ذلك ، حتى بعد تنفيذ كل التحسينات المذكورة أعلاه ، لا تزال مهمة إنشاء جميع المخططات الفرعية الأنا تعمل لفترة طويلة. في حالتنا ، حوالي 6 ساعات مع الاستفادة العالية من الكتلة. تُظهر نظرة فاحصة أن المصدر الرئيسي للتعقيد لا يزال هو عملية خلط الأوراق ، في حين يتم طرح جزء كبير من البيانات المتضمنة في خلط ورق اللعب في المراحل التالية. والحقيقة هي أن النهج الموصوف يبني حيًا كاملاً مكونًا من خطوتين لكل مستخدم ، في حين أن الرسم البياني الفرعي للأنا ليس سوى مجموعة فرعية صغيرة نسبيًا من هذا الحي تحتوي على أقواس داخلية فقط.
على سبيل المثال ، إذا ، من خلال معالجة جيران بوب المباشرين - هاري وفرانك - عرفنا أنهم ليسوا أصدقاء لبعضهم البعض ، فعندئذٍ في الخطوة الأولى بالفعل ، يمكننا تصفية هذه المسارات الخارجية. ولكن من أجل معرفة ما إذا كان كل من Gary و Frenkov ما إذا كانا صديقين ، فسيتعين عليك سحب رسم الصداقة في الذاكرة في جميع عقد الحوسبة أو إجراء مكالمات عن بُعد أثناء معالجة كل سجل ، وهو أمر مستحيل ، وفقًا لشروط المهمة.
ومع ذلك ، هناك حل إذا سمحنا لأنفسنا ، في نسبة صغيرة من الحالات ، بارتكاب أخطاء عندما نجد الصداقة حيث لا وجود لها بالفعل. هناك مجموعة كاملة من هياكل البيانات الاحتمالية التي تجعل من الممكن تقليل استهلاك الذاكرة أثناء تخزين البيانات بأوامر من الحجم ، مع السماح بقدر معين من الخطأ. إن الهيكل الأكثر شهرة من هذا النوع هو مرشح Bloom ، والذي تم استخدامه بنجاح لسنوات عديدة في قواعد البيانات الصناعية للتعويض عن الأخطاء في ذاكرة التخزين المؤقت "ذات الذيل الطويل".
المهمة الرئيسية لفلتر بلوم هي الإجابة على السؤال "هل هذا العنصر مدرج في العديد من العناصر التي سبق رؤيتها؟" علاوة على ذلك ، إذا أجاب المرشح على "لا" ، فربما لم يتم تضمين العنصر في المجموعة ، ولكن إذا أجاب بـ "نعم" - هناك احتمال ضئيل بأن العنصر لا يزال غير موجود.
في حالتنا ، سيكون "العنصر" هو زوج من المستخدمين ، وستكون "مجموعة" جميع حواف الرسم البياني. ثم يمكن تطبيق مرشح Bloom بنجاح لتقليل حجم المراوغة:
بعد إعداد مرشح Bloom مقدمًا بمعلومات حول الرسم البياني ، يمكننا البحث من خلال أصدقاء Harry لمعرفة أن Bob و Ilona ليسا أصدقاء ، مما يعني أننا لسنا بحاجة لإرسال معلومات Bob حول الاتصال بين Gary و Ilona. ومع ذلك ، فإن المعلومات التي تشير إلى أن هاري وبوب صديقان بمفردهما ، لا يزال يتعين إرسالهما حتى يتمكن بوب من استعادة رسالته الودية بالكامل بعد التجميع.
إزالة خلط ورق اللعب
بعد تطبيق المرشح ، يتم تقليل كمية البيانات المرسلة بحوالي 80٪ ، وتتم المهمة في ساعة واحدة بحمل كتلة متوسط ، مما يسمح لك بأداء مهام أخرى بحرية بالتوازي. في هذا الوضع ، يمكن بالفعل تشغيله "وتشغيله" بشكل يومي ، ولكن لا تزال هناك إمكانية للتحسين.
من المفارقات أنه قد يبدو ، يمكن حل المشكلة دون اللجوء إلى خلط ورق اللعب ، إذا سمحت لنفسك بنسبة مئوية معينة من الأخطاء. ويمكن لمرشح Bloom مساعدتنا في هذا:
إذا نظرنا إلى قائمة أصدقاء بوب باستخدام فلتر ، اكتشفنا أن أليس وتشارلي صديقان بالتأكيد ، يمكننا أن نضيف على الفور القوس المقابل إلى الرسم البياني الفرعي للأنا. ستستغرق العملية برمتها في هذه الحالة أقل من 15 دقيقة ولن تتطلب نقل البيانات عبر الشبكة ، ومع ذلك ، قد تكون هناك نسبة مئوية معينة من الأقواس ، وفقًا لإعدادات المرشح ، غير موجودة في الواقع.
لا تقدم الأقواس الإضافية التي تمت إضافتها بواسطة المرشح تشوهات مهمة لبعض المهام: على سبيل المثال ، عند حساب المثلثات ، يمكننا تصحيح النتيجة بسهولة ، وعند إعداد سمات خوارزميات التعلم الآلي ، يمكن تعلم تصحيح ML نفسه في الخطوة التالية.
ولكن في بعض المهام ، تؤدي الأقواس الزائدة إلى تدهور قاتل في جودة النتيجة: على سبيل المثال ، عند البحث عن المكونات المتصلة في الرسم الفرعي للأنا باستخدام الأنا البعيد (بدون رأس المستخدم) ، يزداد احتمال "جسر فانتوم" بين المكونات بالنسبة إلى حجمها ، مما يؤدي إلى في كل مكان تقريبا نحصل على مكون واحد كبير.
هناك أيضًا منطقة متوسطة حيث يجب تقييم التأثير السلبي للأقواس الزائدة بشكل تجريبي: على سبيل المثال ، يمكن لبعض خوارزميات البحث المجتمعي التعامل بنجاح مع القليل من الضوضاء ، مع إعادة بنية مجتمع متطابقة تقريبًا.
بدلا من الاستنتاج
تعد المخططات الفرعية الخاصة بمستخدم Ego مصدرًا مهمًا للمعلومات التي يتم استخدامها بنشاط في OK لتحسين جودة التوصيات وتحسين الخصائص السكانية ومكافحة البريد العشوائي ، لكن حسابهم ينطوي على عدد من الصعوبات.
في المقال ، درسنا تطور النهج المتبع في مهمة إنشاء مخططات فرعية للأنا لجميع مستخدمي الشبكة الاجتماعية وتمكنا من تحسين وقت العمل من 20 ساعة إلى ساعة واحدة ، وفي حالة وجود نسبة مئوية صغيرة من الأخطاء ، ما يصل إلى 10-15 دقيقة.
"الركائز" الثلاثة التي يستند إليها القرار النهائي هي:
- باستخدام خاصية تناسق الرسم البياني وخوارزميات Tomas Schank .
- كفاءة تخزين الأنا السطور الفرعية باستخدام مصفوفة CSR متفرق .
- استخدم مرشح Bloom لتقليل نقل البيانات عبر الشبكة.
يمكن العثور على أمثلة حول كيفية تطور رمز الخوارزمية في دفتر ملاحظات Zeppelin .