قياس زمن الخلط للرسوم البيانية الاجتماعية

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