Мячи и корзины Ver2

Question

В дополнение к оригинальной проблеме с шарами и корзинами, о которой я упоминал: Алгоритм задачи с шарами и корзинами?

Есть немного другая проблема.

Все еще есть N человек, и у них есть неограниченное количество мячей, но на этот раз у них нет корзин.

Проблема:

N человек с неограниченным количеством шаров и M разных корзин. Люди бросают шары в корзины.

Я хочу найти группы людей, которые бросают шары в одни и те же корзины.

Человек А бросает в Корзины 1, 2, 4,, 6,7, 14, 51, 32 Человек Б бросает в Корзины 3, 4, 6, 7, 14,15, 16, 64,43 Человек С бросает в Корзины 3, 4, 6,7,5, 87, 42, 32, 52, 55 , , , и т.д.

В этом примере человек А и В могут быть хорошо связаны (скажем, друзья) (4,6,7,14 общего) и C может быть связан с ними тоже, но не так хорошо связан. (4, 6,7 общие)

Я хочу найти группы из 4-5 таких людей в очень большой базе данных.

Answer 1

Идея Джексона - это начало.

После того, как вы нашли клики, определите общий набор корзин для каждой клики путем пересечения всех корзин egdes. (где корзины ребра - это корзины, общие для людей, представленных узлами этого ребра). только если общий набор корзин больше X, тогда эта клика представляет действительно связанную группу.

например, в исходном вопросе ребра были бы:

A-B:  weight=4, baskets=[4,6,7,14]
A-C:  weight=3, baskets=[4,6,7]
B-C:  weight=4, baskets=[3,4,6,7]

если вы урежете меньше 3, вы получите клику с установленной общей корзиной = [4,6,7].

в примере, который вы дали в комментарии к ответу Джексона, набор общих корзин был бы пуст, так что вы знаете, что эти парни на самом деле не связаны.

Answer 2

Хорошо, моя первоначальная идея; смоделируйте это как взвешенный график. Сделайте людей вершинами и создайте ссылку, когда они делятся корзиной. Если они используют несколько корзин, то увеличьте вес ссылки для каждой корзины, которую они разделяют. Таким образом, в вашем примере вес ребра между A и B будет 4.

Затем вы можете решить, насколько дружелюбными должны быть все в группе, обрезать ребра, вес которых меньше этого значения, а затем искать клики в результирующем графике.