Как оптимально найти подмножества в наборе данных многие-ко-многим?

Question

[Сергей Соколов]

Есть два класса с отношением многие-ко-многим: напр. юзеры (U) и сообщества (C), в которых они состоят. Один юзер может состоять в нескольких сообществах, и в сообществе может быть несколько юзеров.

Мы знаем, кто в каком состоит. Можно представить данные в любом удобном виде. Пока остановился на таком:

c1: [u1, u2, u3],
c2: [u1, u2, u4],
c3: [u2, u3, u5, u6],
...

«Ядрами» называю отношения с, как минимум, двумя участниками с каждой стороны. В этом примере – два «ядра»:

[u1, u2] => [c1, c2],
[u2, u3] => [c1, c3],

Как найти все ядра среди довольно крупных данных?

Кроме перебора всех возможных комбинаций пока ничего не пришло в голову. Очень неэффективно на больших наборах (десятки тысяч с каждой стороны).

Answer 1

[Mrrl]

Есть простое решение за (число сообществ)*(число связей "пользователь-сообщество").

Для каждого сообщества Y:
- заводим массив R[C], где C - число сообществ
- для каждого пользователя X из сообщества Y:
- - для каждого сообщества M, в которое входит пользователь X: R[M]=R[M]+1
- для каждого сообщества M: если M!=Y и R[M] > 1, то пара (Y,M) - ядро.

Быстрее пока не получается.

Answer 2

[Армянское Радио]

Храните сами "ядра" в классической реляционной базе "многие ко многим". Три таблицы - пользователи, группы, связи.
строки в таблице связи: ид пользователя, ид группы.

Comments

[Сергей Соколов]

Я хотел это решать на клиенте, на JS.

[Сергей Соколов]

p.s. задача динамическая, наборы всякие раз новые, получаются вживую с API стороннего сервиса.

[Армянское Радио]

Вы будете тащить на клиента несколько десятков тысяч строк вместо маленького запросика в базу?

[Сергей Соколов]

Армянское Радио: да, их в любом случае тащить со стороннего сервиса. Каждый раз заново.

[Армянское Радио]

Сергей Соколов: обрабатывать это на клиенте будет накладнее, чем на сервере - например, если клиент сидит на 2G, он сочтет ваше приложение чрезвычайным тормозом, а все потому, что вы используете клиента вместо прокси. А так вам ничто не мешает поступить аналогично классике строительства БД - сразу записывайте значения в коллекцию вида [ид первого, ид второго]

[Сергей Соколов]

уходим в детали архитектуры, а не алгоритма. У меня задача именно без серверных БД, уже имея на руках исходные данные, найти наиболее «тяжёлые» подгруппы, масса считается как (число юзеров * 2 + число сообществ). При этом хочется сократить вложенность циклов.

Задача представляется относительно типовой, но не знаю как называется, где искать алгоритм.

[Армянское Радио]

Сергей Соколов: То, что вы обозвали "ядром", в теории графов называется "кликой". Алгоритмов поиска клик достаточно много.

[Армянское Радио]

Сергей Соколов: Статья о кликах

[Сергей Соколов]

Армянское Радио: о спасибо за «клику»! Возможно, то, что надо.

Answer 3

[Сергей Протько]

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

Comments

[Сергей Соколов]

Смешивать их в граф некруто, потому, что нет смысла в соединениях юзер-юзер или сообщество-сообщество. Вот как бы выглядел граф для приведённого примера:

Answer 4

[SeptiM]

Для начала рассмотрим произвольный граф. Каждая вершина будет сообществом, а на каждое ребро посадим по два юзера. Юзер принадлежит сообществу, если его ребро касается соответствующей вершины. Для такого примера будет Omega(C^2) ядер, все различные. Это накладывает некоторые нижние оценки на алгоритм.

Тривиальный способ будет работать за O(C^2 U) + сортировка юзеров в каждом сообществе. Понятно, что сравниваем сообщества попарно, и ищем пересечение за линию по отсортированным спискам.

Можно улучшить алгоритм через минхэш (en.wikipedia.org/wiki/MinHash) заплатив точностью. Минхэш позволяет считать символ Жаккара -- размер пересечения двух множеств делить на размер объединения. Можно отсеять только крупные пересечения.