О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный момент известно несколько формальных способов определения понятия квази-клики. Согласно статьи 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' - множество ребер подграфа.
В данной работе в дальнейшем будет использоваться первое определение, ориентированное только на плотность ребер в графе.
Похожие статьи
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Введение - Использование квази-клик для анализа графа рынка России
Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей,...
-
В статье Network approach for the Russian stock market авторы анализируют данные фондового рынка для России, в том числе используют поиск максимальной...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России
Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...
-
Заключение - Использование квази-клик для анализа графа рынка России
Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска...
-
Построение графа рынка России - Использование квази-клик для анализа графа рынка России
Для начала работы с алгоритмической частью требуется построить граф рынка. Для того, чтобы проанализировать правильность подхода с применением...
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
Анализ полученных квази-клик - Использование квази-клик для анализа графа рынка России
Как было замечено в статье Network approach for the Russian stock market, для российского рынка наиболее ценные акции имеют сильные связи между их...
-
Понятие и применение графа рынка - Использование квази-клик для анализа графа рынка России
Динамика характеристик отражающих тенденцию поведения фондового рынка может быть интересна многим участникам фондовой биржи и, в особенности, инвесторам....
-
Экономические и финансовые сети На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства,...
-
Знаменитая теория полимолекулярной адсорбции Брунауэра, Эммета и Теллера, получившая название теории БЭТ (по первым буквам фамилий ученых), основана на...
-
Данные о Российском рынке - Использование квази-клик для анализа графа рынка России
История рынка ценных бумаг берет свое начало еще в XV веке, когда государства для привлечения дополнительных денежных средств начали выпускать и...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
В нашем анализе данных показателей рынков под "самородками" понимаются зависимости, отражающие степень эффективности рекламных кампаний. Эксперты часами...
-
Адсорбция активированный уголь Развитие теории адсорбционных сил еще не достигло такой стадии, когда по известным физико-химическим свойствам газа и...
-
Адсорбционные методы исследования свойств поверхности позволяют количественно охарактеризовать происходящие при адсорбции межмолекулярные взаимодействия,...
-
Топологический элементный анализ - Системная революция и принцип дуального управления
Независимые от системы элементы формально выглядят как изолированные вершины графа структуры (ее симплекса). Если некоторый элемент на всех структурах...
-
Возьмем данные об инвестициях в основной капитал (млрд. руб.) Год Квартал Номер квартала Значение 2003 I 1 330 II 2 470,4 III 3 608,8 IV 4 773,7 2004 I 5...
-
Попытаемся дать общее представление о свойствах и применении адсорбентов на примере весьма распространенных углеродных материалов. Углеродные адсорбенты...
-
Описание процессов, происходящих на поверхности, изобилует специальными терминами, и при рассмотрении адсорбционных явлений приходится говорить на языке,...
-
Адсорбционные явления чрезвычайно широко распространены в живой и неживой природе. Толщи горных пород и почвы являются огромными колоннами с...
-
Гамильтоновы циклы, Основные понятия и определения - Гамильтоновы циклы
Название "гамильтонов цикл" произошло от задачи "Кругосветное путешествие" предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно...
-
Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода Пусть необходимо вычислить линейный функционал , Где, причем для...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Экспериментальная установка В работе используется прибор для текстурных измерений "Термосорб" серии М, фирмы "КАТАКОН" Серийный №017 Дата выпуска...
-
Данная глава будет посвящена анализу кассовых сборов фильмов. В начале главы приводится краткая методическая справка об основном статистическом методе,...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Следует отметить, что не существует особых сил, вызывающих адсорбцию. Адсорбция молекул на поверхности твердого тела происходит за счет сил притяжения со...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
Пусть необходимо подобрать оптимальные настройки для объекта с передаточной функцией (9). Степень затухания, к примеру, ш= 0.75. Ниже даются рекомендации...
-
Основные характеристики нечетких множеств, Примеры нечетких множеств - Нечеткая логика
Пусть M = [0,1] и A - нечеткое множество с элементами из универсального множества E и множеством принадлежностей M - Величина ?A(x) называется...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
Определение. Примеры - Формационные основы универсальных алгебр
1. Пусть А - непустое множество (АШ), n -- натуральное число, - декартова (прямая) n-ая степень множества А. В частности, если n=0, то под будем понимать...
О квази-клике. - Использование квази-клик для анализа графа рынка России