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

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

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

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

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

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

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

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

г) Если нужно, я могу упростить задачу, обеспечив взаимность в отношениях, т.е. А-друзья-с-Б ‹==> Б-друзья-с-А, а если очень нужно, я, может быть, и урежу объем данных, но на самом деле он всегда будет около отметки в 1 мил.

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

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


java graph math sparse-matrix discrete-mathematics
person Andy    schedule 30.05.2010    source источник
comment
Если вы хотите найти каждый цикл, то это точно не P, так как для полного графа их больше, чем n! циклы. С другой стороны, если вы просто хотите посчитать циклы (без их вывода), то это P (и, следовательно, также NP - P является подмножеством NP).   -  person Tomer Vromen    schedule 30.05.2010
comment
Итак, вы хотите найти каждое подмножество вершин, где все в подмножестве дружат со всеми остальными в этом подмножестве? Поскольку эта проблема называется Максимальной кликой: en.wikipedia.org/wiki/Maximal_clique#Definitions   -  person j_random_hacker    schedule 30.05.2010
comment
@Tomer: ты уверен, что проблема подсчета элементарных окружностей в неориентированных графах находится в P?   -  person jpalecek    schedule 30.05.2010
comment
@jpalecek: Нет, на самом деле. Возможно, меня смутило подсчет всех циклов длиной не более k.   -  person Tomer Vromen    schedule 30.05.2010
comment
@Andy: С вашей точки зрения c) в вопросе кажется, что вы можете жить, фактически не находя все циклы. Таким образом, обнаружение всех циклов кажется решением вашей фактической основной проблемы, а не самой проблемой. Может быть, вы можете описать, в чем проблема (если это вообще возможно). Возможно, люди здесь смогут найти альтернативы, которые вы не рассматривали...   -  person    schedule 30.05.2010
comment
@Moron: Полный контекст проблемы является частью решения банковского мошенничества. У меня есть доступ к записям транзакций, и я ищу группы людей, переводящих деньги друг другу. Уже составили подмножество тех пар счетов, которые осуществляют интересные/значительные переводы (пороги которых можно ужесточить, отсюда пункт D). Я не беспокоился о точке C, потому что элементарные циклы всегда можно было снова запустить по тому же алгоритму, чтобы получить «родительские» циклы...   -  person Andy    schedule 30.05.2010
comment
@Andy: Учитывая контекст, возможно, вы могли бы рассмотреть вместо этого просмотр тиражей: courses.csail.mit.edu/6.854/06/scribe/s12-minCostFlowAlg.pdf   -  person jpalecek    schedule 30.05.2010

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

person JSchlather    schedule 30.05.2010

arrow_upward
0
arrow_downward

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

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

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

г) Если нужно, я могу упростить задачу, обеспечив взаимность в отношениях, т. е. А-друзья-с-Б ‹==> Б-друзья-с-А, а если очень нужно, я, может быть, и урежу объем данных, но на самом деле он всегда будет около отметки в 1 мил.

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

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

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

person jpalecek    schedule 30.05.2010

arrow_upward
0
arrow_downward

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

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

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

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

person Viesturs    schedule 30.05.2010