Как предложить списки друзей для пользователя Facebook на основе общих друзей?

Question

Я создаю приложение, чтобы предлагать списки друзей для пользователя Facebook на основе его / ее общих друзей с каждым другом.Моя идея выглядит так:

http://i219.photobucket.com/albums/cc213/DoSvn/example03.png

Я могу найти всех общих друзей А с каждым его / ее другом (b1, b2 ...).Это пересечение между b1, b2 ... (c1, c2 ...) Я хочу разделить друзей на несколько групп, таких как:

b1, b2, b3 в группе;b1, b4 в группе;b5, b6 в группе;b7, b8 в группе

Может быть, выбрана только группа из b1, b2, b3, потому что она больше, чем через b1, также в другой группе.Я попробовал идею:

1. Создайте много групп (я пробовал 200), каждая группа содержит несколько списков общих друзей (это «c», я пробовал 5).
2. С помощьюгруппу, найдите пересечение и поместите его в другой список.
3. После шага 2 у меня есть список, содержащий пересечения.Я упорядочиваю его по размеру каждого пересечения и получаю самые большие пересечения (я пробовал 3 и 5).
4. С каждым выбранным пересечением я обнаруживаю, что у друга, у которого есть общие друзья, есть пересечение и толкаю вгруппа.

Это как я.Но я выбрал «с» случайно, поэтому результат не является точным.Потому что мой элементарный список друзей самый большой, поэтому они всегда появляются в 3 или 4 группах результата.Есть ли у вас какие-либо идеи ?Спасибо :) и извините за мое плохое объяснение:)

Answer 1

В кластеризации графов много работы, которая может оказаться полезной.Вы могли бы смоделировать каждого человека как вершину, с гранью между друзьями (возможно, с учетом веса, насколько «близки» они, например, как часто они обмениваются сообщениями).Затем разбейте множество вершин, используя кластеризацию графа для получения групп.(Ut не обязательно должен быть разделом, например, вы могли бы искать подмножества вершин, у которых есть ребра с большим весом.)

Система hMetis от U Minn реализует много стратегий разделения.графики.