О квази-клике. - Использование квази-клик для анализа графа рынка России

Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный момент известно несколько формальных способов определения понятия квази-клики. Согласно статьи On the maximum quasi-clique problem первый и самый распространенный определяется следующим образом [17].

Представим граф G=(V, E), определенный в предыдущем параграфе, и некоторое фиксированное вещественное число г, удовлетворяющее условию 0 < г < 1. Подмножество вершин Q называется г-квази-кликой или просто г-кликой, если плотность ребер графа G[Q], расcчитанная как отношение числа ребер, вошедших в граф, к числу всех возможных ребер на подмножестве Q, по меньшей мере равна г. Для случая г=1 задача поиска квази-клики сводится к задаче поиска максимальной клики. Плотность ребер в графе можно вычислить следующим образом:

Где E - количество существующих ребер в графе, V - количество вершин графа.

Согласно другим работам, квази-клику можно определить по-другому [13] [20].

Пусть S подмножество k - вершин графа G, S?V(G), представляющее искомый граф G(S). Подмножество S называется г-квази-кликой для 0<г?1, если для любой вершины v, v?S, degG(S) (v)? [г?(k-1)], где deg(v) - степень вершины v, то есть подграф удовлетворяет условию ограничения минимальной степени вершины [г?(k-1)], заданному исследователем.

Также встречается третий вариант определения квази-клики [9]. Он объединяет первый и второй подходы, а клика называется (л, г)-квази-клика. Таким образом, группа вершин будет являться (л, г)-квази-кликой, если выполняются оба условия - плотность ребер в графе и минимальная степень вершины в группе. Где л, г - соответствующие пороговые значения для плотности ребер и минимально степени вершины, 0 ? л ? г ? 1. Формально условия можно определить следующим образом:

? v ? V': degV'(v) ? л - (|V'| ? 1)(1)

|E'| ? г - ( |V'| / 2),(2)

Где V' - множество вершин подграфа, а E' - множество ребер подграфа.

В данной работе в дальнейшем будет использоваться первое определение, ориентированное только на плотность ребер в графе.

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




О квази-клике. - Использование квази-клик для анализа графа рынка России

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