Алгоритмы поиска плотных подграфов в графе, о клике. - Использование квази-клик для анализа графа рынка России

О клике.

Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17].

Пусть G=(V, E) - простой неориентированный граф, где V - множество n вершин, а E - множество ребер графа. Для u, v ? V, dG(u, v) - длина кратчайшего пути между вершинами u и v в графе G. d(G) = maxu, v?V dG(u, v) - диаметр графа G. Для множества S, S ? V, существует граф G[S] = (S, E ? S Ч S), который называется подграф графа G на множестве S. Граф G = (V, E) называется полным, если все вершины графа попарно соединены, то есть ?i, j ? V, i ? j, существует ребро (i, j) ? E. Клика C - представляет собой такое подмножество вершин из V, что подграф G[C] графа G, построенный на множестве C, является полным. Как было сказано ранее клика может быть максимальной по включению и максимальной по размеру. Клика называется максимальной по включению, если она не является подмножеством большей клики, и максимальной по размеру, если не существует большей клики в графе. Задача поиска максимальной по размеру клики (the maximum clique problem) заключается в том, чтобы найти клику максимальной мощности в графе G.

Поиск клики в графе является NP-сложной задачей и принадлежит к классу NP-полных задач [15]. Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено [23]. Точное решение требует экспоненциального времени, что сильно затрудняет вычисления для больших объемов входных данных [6].

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

Похожие статьи




Алгоритмы поиска плотных подграфов в графе, о клике. - Использование квази-клик для анализа графа рынка России

Предыдущая | Следующая