найти ВСЕ циклы в огромной разреженной матрице

Question

Прежде всего, я новичок в Java, поэтому не уверен, возможно ли это вообще! В основном у меня есть огромный (3 + миллион) источник данных реляционных данных (то есть A дружит с B + C + D, B дружит с D + G + Z (но не A - то есть не взаимно) и т. Д.), И я хочу найти каждый цикл в этом (не обязательно связанном) ориентированном графе.

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

Я быстро просмотрел код Java-реализации алгоритма Джонсона (в этом потоке), и похоже, что матрица отношений - это первый шаг, поэтому я думаю, мои вопросы:

а) Способна ли Java обрабатывать матрицу 3 + миллиона * 3 + миллиона? (планировал представлять A-friends-with-B двоичной разреженной матрицей)

b) Мне нужно найти каждый связанный подграф в качестве моей первой проблемы, или алгоритмы поиска циклов будут обрабатывать непересекающиеся данные?

в) Действительно ли это подходящее решение проблемы? Мое понимание «элементарных» циклов состоит в том, что на графике ниже вместо того, чтобы выделять A-B-C-D-E-F, он выберет A-B-F, B-C-D и т. Д., Но это не конец света, учитывая задачу.

    E
   / \
  D---F
 / \ / \
C---B---A

d) При необходимости я могу упростить проблему, навязывая взаимность в отношениях - то есть A-friends-with-B <==> B-friends-with-A, и, если это действительно необходимо, я могу сократить данные размер, но реально он всегда будет около отметки 1 мил.

z) Это задание P или NP ?! Я откусываю больше, чем могу жевать?

Спасибо всем, любая помощь приветствуется! Andy

Answer 1

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

Мы пойдем с закрытым частым майнингом наборов предметов, что он сделает, найдет все группы друзей, где все дружат друг с другом.

Я скажу прямо сейчас, что Java не может делать то, что вы хотите. Он не может загружать столько памяти и недостаточно эффективен для обработки этих данных в любое разумное время, вам нужно будет использовать C / C ++. Я бы посоветовал использовать LCM, который является закрытым майнером наборов часто используемых предметов, но вам также понадобится установить поддержку достаточно высоко из-за объема данных, которые у вас есть.

Еще одна вещь, которую вы могли бы рассмотреть, это чтение по Large Graph Mining, которая также является довольно большой областью исследований, но Java не собирается ее сокращать. Кроме того, вы не сможете найти все циклы в ваших данных (если только они невероятно редки), их будет слишком много. Они также будут дублировать друг друга и не будут иметь особого значения. Возможно, вы сможете найти несколько крупнейших циклов.

Answer 2

Поиск каждого цикла не звучит разумно. Там будет экспоненциальное количество циклов, все перекрывают друг друга.

Что касается P или NP, самая медленная часть фактически перечисляет каждый цикл (потому что их может быть очень много). Если циклов нет, существует линейный алгоритм.

Может быть, вы действительно хотите разделить график на двусвязные компоненты? Смотри http://en.wikipedia.org/wiki/Biconnected_component

Также практически НИКОГДА не разумно хранить графики в матрицах. Звучит неплохо в теории, но на практике не масштабируется. Вместо этого используйте списки смежности (http://en.wikipedia.org/wiki/Adjacency_list)

Answer 3

в) Это действительно уместно решение проблемы? мой понимание «элементарных» циклов что на графике ниже, скорее чем выбрать A-B-C-D-E-F выбрать A-B-F, B-C-D и т. д., но это не конец света, учитывая задача.

    E
   / \
  D---F
 / \ / \
C---B---A

Нет. «Элементарный» в смысле статьи Дональда Джонсона означает простой, то есть ни один узел не появляется дважды в круге. Это означает, что алгоритм не выберет AFBCDBA, но выберет ABCDEF.

d) При необходимости я могу упростить проблема путем обеспечения взаимности в отношения - то есть A-friends-with-B <==> B-друзья-с-А, и если на самом деле необходимо я могу сократить размер данных, но реально это всегда будет около 1 мил знак.

Ненаправленные графы имеют векторное пространство (непростых) циклов (что имеет хорошую основу и т. Д.), Но я не знаю, поможет ли это вам.

z) Это задание P или NP?

Это проблема перечисления, которая сама по себе не может быть ни в P, ни в NP.