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

Question

В дополнение к оригинальные шары и корзинки проблемы я уже упоминал здесь: Balls and Baskets Problem Algorithm?

Существует несколько другая проблема.

Все еще есть люди N, и у них есть неограниченные шары, но на этот раз у них нет корзин.

Проблема:

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

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

Люди А бросает корзину 1, 2, 4, 6,7, 14, 51, 32 Лицо B бросает корзину 3, 4, 6, 7, 14,15, 16, 64,43 Людей C бросает в корзины 3, 4, 6, 7, 5, 87, 42, 32, 52, 55 . . . и т. Д.

В этом примере человек A и B могут быть хорошо связаны (скажем, друзья) (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.

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