علاقات صداقة تتبع خوارزمية

Question

أنا أفكر تطبيق من شأنها أن محاولة إثبات "ست درجات من الانفصال"نظرية مع مجموعة من المستخدمين التي هي جزء من الشبكة الاجتماعية.

وأود أن تلك العناصر:

1. اثنين من المستخدمين التي أود أن يثبت ست درجات نظرية
2. لكل مستخدم أعرف قائمة الأصدقاء في الشبكات الاجتماعية

الذي هو أفضل خوارزمية لمعرفة ما إذا كان اثنين من المستخدمين على اتصال مع أي درجة وتبين في نهاية المطاف الخطوات في الرابط ؟

Answer 1

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

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

Answer 2

إضافة بعض المواد الخلفية:

لحل هذه المشكلة عموما كنت ترغب في تجنب ويب إلغاء وغيرها المخصص التقنيات التي تخص شبكة اجتماعية واحدة.بدلا من ذلك, ربما كنت سوف ترغب في النظر في XHTML أصدقاء الشبكة (XFN) الذي هو وسيلة إلى استخدام rel="" السمة ارتباط تشعبي إلى بيان العلاقة بين الهدف من هذا الارتباط التشعبي و لك.وهناك أيضا المتنافسة المعايير FOAF والذي يستخدم قوات الدفاع الرواندية.

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

بسبب هذا, جوجل قد حصلت يرغبون في ذلك ، بدأت الألغام هذه البيانات.لديهم الاجتماعية الرسم البياني API التي يمكن أن الألغام سواء XFN و FOAF البيانات أن تفعل بالضبط بعض الأشياء التي تريد القيام به.أقترح عليك أن تبدأ هناك.الشيء الجميل في جوجل API لأنها التعدين في جميع أنحاء شبكة الإنترنت, يمكنك توسيع خارج البحث خارج شبكة اجتماعية محددة كان لديك في الاعتبار.