Set<Set<V>> result = new HashSet<>();

Set<V> startVCands = getStartVCands(onlyBestStartV);

int maxCliqueSize = 0;

for (V startV : startVCands) {

for (int i = 0; i < MAX_ITERATIONS; i++) {

Set<V> qc = getQuasiClique(gamma, startV);

int qcSize = qc.size();

if (qcSize >= maxCliqueSize) {

maxCliqueSize = qcSize;

result.add(qc);

}

}

}

// Filter non-maximal cliques

Collection<Set<V>> nonMaximalQCliques = new ArrayList<>();

for (Set<V> qc : result) {

if (qc.size() < maxCliqueSize) {

nonMaximalQCliques.add(qc);

}

}

result.removeAll(nonMaximalQCliques);

return result;

}

private Set<V> getQuasiClique(double gamma, V startV) {

Set<V> clique = new TreeSet<>();

int cliqueEdgesNumber = 0;

// Add starting node into result

clique.add(startV);

Set<V> cands = graph.neighbourhoodOf(startV);

// Construct clique

while (true) {

List<V> accepted = new ArrayList<>();

for (V v : cands) {

// Skip vertices that are yet in clique

if (clique.contains(v)) {

continue;

}

// Get inClique degree

int qcDeg = getInDegree(v, clique);

// Check threshold

if (cliqueEdgesNumber != 0) {

double toCompare = (2.0 * (cliqueEdgesNumber + qcDeg)) / (double) ((clique.size() + 1) * (clique.size()));

if (toCompare >= gamma) {

accepted.add(v);

}

} else {

accepted.add(v);

}

}

// If accepted is empty, break the loop

if (accepted.isEmpty()) {

break;

}

Random rand = new Random();

int randIndex = rand.nextInt(accepted.size());

V toAdd = accepted.get(randIndex);

clique.add(toAdd);

cliqueEdgesNumber += getInDegree(toAdd, clique);

for (V u : graph.neighbourhoodOf(toAdd)) {

if (!cands.contains(u)) {

cands.add(u);

}

}

}

return clique;

}

3.3.6 Сравнение времени работы реализованных алгоритмов

Разработанные алгоритмы выполнялись на компьютере с процессором Intel Core i7-6700 3.4Ghz x 8, 16GB RAM, и под управлением Linux Ubuntu 16.04.4.

Время поиска решения измерялось на следующих наборах данных:

· Случайные графы, сгенерированные с использованием Gnp модели Эрдеша - Реньи, размерами 50, 100 и 200 вершин, и заданными вероятностьями ребра 0.4, 0.5 и 0.6.

· Граф рынка, построенный по данным о торгах на Московской Бирже с 2007 по 2011 год.

· Граф рынка, построенный по данным о торгах акций, входящих в индекс S&P 500 с 4 сентября 2012 года по 19 сентября 2016 года.

При построении графов рынка использовался порог корелляции 0.5.

Для каждого алгоритма и каждого набора данных выполнялось по 100 итераций, после чего вычислялось среднее время работы алгоритма. Прочерк ставился в том случае, если решение не было найдено за 1 час.

Результаты представлены в таблице ниже (Табл.2):

Таблица 2. Время работы алгоритмов на тестовых данных

	Quick	Original г-QC	DDA	Modified DDA	GRASP
МБ (2007-2011) - 177в.	0,004 с	0,062 с	0,069 с	0,08 с	1,864 с
S&P 500 (2012 - 2016) - 505в.	-	0,699 c	0,116 с	0,398 с	23,045 с
Gnp, p = 0.4 - 50в.	0,01 с	0,15 с	0,358 с	0,331 с	0,633 с
Gnp, p = 0.5 - 50в.	0,056 с	0,331 с	0,645 с	0,896 с	1,178 с
Gnp, p = 0.6 - 50в.	1,124 с	0,972 с	0,808 с	0,828 с	2,777 с
Gnp, p = 0.4 - 100в.	0,449 с	8,494 с	5,018 с	5,162 с	4,508 с
Gnp, p = 0.5 - 100в.	9,958 с	150,926 с	64,748 с	65,961 с	11,386 с
Gnp, p = 0.6 - 100в.	-	1185,89 с	951,373 с	965,148 с	25,59 с
Gnp, p = 0.4 - 200в.	110,422 с	-	796,78 с	804,112 с	87,42 с
Gnp, p = 0.5 - 200в.	-	-	-	-	144,745 с
Gnp, p = 0.6 - 200в.	-	-	-	-	296,48 с

* - представлено время выполнения одной итерации

Из таблицы видно, что алгоритм Quick, являющийся точным алгоритмом и использующий метод ветвей и границ, даже не смотря на новые техники, позволяющие значительно сократить пространство поиска, все равно не справляется с поиском решения за отведенное время (1 час) для больших и плотных графов.

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

Сравнение времени работы DDA алгоритма и оригинальной формулировки задачи поиска максимальной г-квази-клики показало следующее: на маленьких графах и на графах с меньшей плотностью ребер DDA работает медленнее, но на больших графах DDA дает точное решение намного быстрее (например, на графе рынка S&P 500, который содержит 505 вершин).

3.4 Анализ полученных квази-клик

Для поиска квази-клик на графах рынка были использованы алгоритмы DDA для получения максимальной квази-клики (реализация описана в главе 3.3.2), и модифицированный алгоритм DDA, который находит все максимальные квази-клики (реализация описана в главе 3.3.4).

3.4.1 Размеры квази-клик

Ниже в таблицах 4 и 5 представлены размеры максимальных квази-клик для каждого графа рынка и для каждого рассматриваемого значения .

Таблица 4. Размер максимальных квази-клик для графа рынка России с 2007 по 2011 гг.

Период	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,75	0,8	0,85	0,9	0,95	1,0
1	44	42	39	37	34	31	26	26	24	22	21	19	19
2	45	41	39	36	35	31	28	26	24	24	22	21	19
3	44	41	39	37	35	31	28	27	26	24	24	22	19
4	44	41	39	38	35	32	28	26	26	24	23	21	19
5	47	42	39	38	36	34	31	30	28	26	24	23	22
6	48	43	40	38	38	35	32	30	27	25	24	23	22
7	31	23	23	23	21	19	18	17	17	17	17	15	15
8	33	26	24	24	23	21	20	19	18	18	17	16	16
9	34	29	27	24	24	21	19	19	18	17	16	16	16
10	33	27	24	22	19	18	17	17	17	16	15	14	14
11	39	31	27	24	22	21	19	18	18	18	17	14	14

Таблица 5. Размер максимальных квази-клик для графа рынка акций из индекса S&P500 с 2012 по 2016 гг.

Период	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,75	0,8	0,85	0,9	0,95	1,0
1	197	142	121	110	95	82	73	69	64	61	54	49	42
2	171	116	101	91	83	72	63	58	53	49	44	37	35
3	336	244	214	189	175	159	145	135	129	121	114	101	84
4	261	216	194	171	153	141	128	122	113	105	96	85	70

Для графа рынка акций из индекса S&P 500 размер максимальной клики (квази-клика при значении параметра ) в среднем составляет 11,44% от размера графа, в то время как для фондового рынка России этот показатель составляет 10,02%. Далее при уменьшении значения параметра размер максимальной квази-клики растет, и при наименьшем рассматриваемом значении составляет:

· для графа рынка акций из индекса S&P 500: 47,77%;

· для графа рынка России: 22,70%.

Такая большая разница в размере максимальной квази-клики говорит о том, граф рынка акций из индекса S&P 500 имеет большее количество связей, и при уменьшении значения размер максимальной квази-клики растет быстрее, чем размер максимальной квази-клики на графе рынка России.

3.4.2 Состав квази-клик

В статье (Vizgunov A. et al, 2014) отмечено, что для российского рынка наиболее ценные акции имеют сильные связи между их доходностями [5]. Таблица 6 содержит акции, торгующиеся в наибольшем объеме на российском рынке - 10 акций, представляющих 90,44% фондового рынка России за весь исследуемый период.

Таблица 6. Акции, торгующиеся в наибольшем объеме

Инструмент	Объем (%)
SBER	27.55
GAZP	26.33
GMKN	9.77
LKOH	8.76
ROSN	5.33
VTBR	4.90
SBERP	3.53
SNGS	2.17
HYDR	1.09
CHMF	1.01

Наибольший интерес представляет состав найденных г-квази-клик, а именно объединения всех максимальных квази-клик. Состав найденных подграфов для каждого периода времени и для заданного значения г указан в таблице ниже (Табл.7):

Таблица 7. Объединения найденных квази-клик.

Номер периода	г = 0,75	г = 0,85	г = 0,95
1	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, KZBE, LKOH, MAGN, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR	CHMF, GAZP, GMKN, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
2	AFKS, AKRN, CHMF, DVEC, FEES, GAZP, GMKN, KZBE, LKOH, MAGN, MMBM, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	CHMF, DVEC, FEES, GAZP, KZBE, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
3	AKRN, CHMF, DVEC, FEES, GAZP, KZBE, LKOH, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	DVEC, FEES, GAZP, KZBE, LKOH, MSNG, MSSB, MTSS, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SNGS, SNGSP, TATNP, TGKE, TRNFP, VTBR
4	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, HYDR, KZBE, LKOH, MMBM, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR
5	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, HYDR, KZBE, LKOH, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR	AKRN, DVEC, FEES, GAZP, KZBE, LKOH, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
6	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, HYDR, KZBE, LKOH, MMBM, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR, YKEN	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, HYDR, KZBE, LKOH, MMBM, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR, YKEN	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TRNFP, VTBR
7	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TRNFP, VTBR	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR
8	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, TATNP, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, TATNP, VTBR
9	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, VTBR
10	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR
11	AFKS, CHMF, GAZP, GMKN, HYDR, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TRMK, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TRMK, VTBR
Пересечение объединений за все периоды	CHMF, GAZP, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR	GAZP, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SNGS, TATN, VTBR	GAZP, LKOH, MTSS, ROSN, SBER, SBERP, SNGS, VTBR

Далее рассмотрим, сколько раз доминирующие акции встречаются в найденных плотных подграфах, и сравним результаты с аналогичными результатами из статьи [5]. Данная информация описана в таблице 8.



Таблица 8. Вхождение доминирующих акций в найденные квази-клики.

Инструмент	Название компании	Количество вхождений в объединение максимальных квази-клик при г = 0,75	Количество вхождений в объединение максимальных квази-клик при г = 0,85	Количество вхождений в объединение максимальных квази-клик при г = 0,95
SBER	Сбербанк России	11	11	11
GAZP	Газпром	11	11	11
GMKN	Норильский Никель	10	7	6
LKOH	ЛУКОЙЛ	11	11	11
ROSN	Роснефть	11	11	11
VTBR	ВТБ Банк	11	11	11
SBERP	Сбербанк России, акция привилегированная	11	11	11
SNGS	Сургутнефтегаз	11	11	11
HYDR	РусГидро	4	1	0
CHMF	Северсталь	11	10	10

Из таблицы видно, что многие доминирующие акции по несколько раз входят в найденные квази-клики и максимальные клики, что подтверждает гипотезу, выдвинутую в статье [5] о том, что наиболее торгуемые акции на фондовом рынке России образуют коррелируемые связанные множества. Более того, данное исследование показывает, что для получения аналогичных выводов можно использовать результаты поиска квази-клик в графе рынка.

Таким же образом был проведен эксперимент с графами рынка, построенными на данных о торгах акций, входящих в индекс S&P 500, с 4 сентября 2012 года по 19 сентября 2016 года. Этот набор данных был разделен на 4 равных непересекающихся периода, каждый из которых составляет 369 дней. Граф рынка построен с пороговым значением корреляции равным 0,5. В таблице ниже (Табл.9) представлены 15 акций, торгующиеся в наибольшем объеме:



Таблица 9. Акции индекса S&P 500, торгующиеся в наибольшем объеме

Инструмент	Объем (%)
BAC	4.46
AAPL	3.12
FB	1.85
GE	1.74
MSFT	1.69
F	1.50
INTC	1.43
CSCO	1.39
HPQ	1.36
PFE	1.33
MU	1.28
CMCSA	1.10
T	1.09
C	1.02
FCX	0.99

Далее в таблице 10 указан состав найденных квази-клик:

Таблица 10. Найденные квази-клики.

Номер периода	г = 0,75	г = 0,85	г = 0,95
1	ADI, ADP, AME, AMG, AMP, APC, BK, BLK, BWA, C, CB, CINF, CMA, CMI, COL, CVX, DOV, EMR, ETN, FITB, FLR, FMC, GS, HIG, HON, IFF, IR, ITW, IVZ, JEC, JPM, KEY, KSU, L, LEG, LLTC, LNC, LUK, MAR, MET, MMC, MMM, MRO, MS, MTD, NTRS, NUE, PCAR, PFG, PH, PRU, PXD, ROK, ROP, SCHW, SLB, SNA, STI, STT, SWK, SYK, TEL, TMK, TROW, TXN, UNM, UNP, UTX, WAT, WFC, XL, XOM, XRAY, ZBH	ADI, AMG, AMP, APC, BK, BLK, BWA, C, CINF, CMA, CMI, COL, CVX, DOV, EMR, ETN, FITB, FLR, GS, HIG, HON, IFF, IR, ITW, IVZ, JEC, JPM, KEY, KSU, L, LLTC, LNC, MAR, MET, MMC, MMM, MRO, MS, MTD, NTRS, NUE, PCAR, PFG, PH, PRU, ROK, ROP, SCHW, SNA, STI, STT, SWK, TEL, TMK, TROW, UNM, UNP, UTX, XL, XOM, XRAY	ADI, AMG, AMP, APC, BK, BLK, BWA, C, CB, CINF, CVX, DOV, EMR, ETN, FLR, GS, HIG, HON, IFF, IR, ITW, IVZ, JEC, JPM, KEY, KSU, L, LLTC, LNC, MAR, MET, MMC, MMM, MRO, MTD, NTRS, NUE, PCAR, PFG, PH, PRU, ROP, SCHW, SNA, STT, TEL, TMK, TROW, UNM, UNP, UTX, XOM, XRAY
2	ADP, AFL, AIG, AME, AMG, AMP, APH, AXP, BDX, BEN, BLK, CB, CMI, COF, DFS, DHR, DIS, ECL, EMR, FIS, FLR, GE, GPC, HBAN, HIG, HON, HSIC, IFF, ITW, IVZ, KEY, L, LEG, LNC, MAR, MCO, MET, MMC, MMM, NTRS, PCAR, PFG, PH, PKI, PNC, PNR, PRU, PX, R, SNA, SPGI, STT, TMO, TROW, TSS, UNM, UPS, URI, USB, UTX, WFC, WYN, XL	ADP, AFL, AIG, AME, AMG, AMP, APH, AXP, BDX, BEN, BK, BLK, COF, DFS, DHR, DIS, EMR, FIS, FLR, GPC, HBAN, HIG, HON, HSIC, IFF, ITW, IVZ, KEY, L, LNC, MCO, MET, MMC, MMM, NTRS, PCAR, PFG, PH, PKI, PNC, PNR, PRU, R, SCHW, SNA, SPGI, STT, TMO, TROW, UNM, UPS, URI, USB, UTX, WFC	ADP, AFL, AME, AMG, AMP, APH, AXP, BEN, BLK, COF, DHR, DIS, EMR, FIS, FLR, GPC, HIG, HON, ITW, IVZ, KEY, L, LNC, MCO, MET, MMC, PFG, PH, PKI, PNC, PNR, PRU, R, SPGI, STT, TMO, TROW, UNM, USB, UTX, WFC
3	ABT, ACN, ADP, ADS, AFL, AIG, AIZ, AJG, AKAM, ALLE, AME, AMG, AMP, AON, APD, AVY, BA, BAC, BBT, BEN, BK, BLK, C, CA, CAH, CB, CBG, CCL, CHD, CINF, CL, CMCSA, COL, CSCO, CTAS, CTSH, CVS, DFS, DHR, DLPH, DNB, DOW, ECL, EFX, EMR, ETFC, ETN, FDX, FIS, FISV, FITB, GD, GE, GLW, GPC, GPN, GS, HBAN, HD, HIG, HON, HSIC, IFF, INTU, IP, IPG, IR, ITW, IVZ, JCI, JNJ, JPM, KEY, L, LLTC, LMT, LNC, LUK, MA, MAR, MCK, MCO, MDT, MET, MKC, MMC, MMM, MS, MTB, MTD, NDAQ, NKE, NLSN, NOC, NSC, NTRS, NWL, OMC, PAYX, PBCT, PCAR, PFE, PFG, PGR, PH, PKI, PNC, PRU, PX, R, RF, RHI, ROK, ROP, SCHW, SNA, SPGI, STI, STT, SWK, SYK, TEL, TMK, TMO, TROW, TRV, TSS, TXN, TXT, UNH, UNM, UNP, USB, UTX, VAR, VFC, VRSN, WAT, WFC, XRAY, XRX, XYL, ZBH	ABT, ACN, ADP, AFL, AIG, AJG, AKAM, ALLE, AME, AMG, AMP, AON, AVY, BA, BAC, BBT, BEN, BK, BLK, C, CA, CB, CBG, CHD, CINF, CL, COL, CSCO, CTAS, CTSH, CVS, DHR, DNB, DOW, ECL, EFX, ETN, FDX, FIS, FISV, FITB, GD, GLW, GPC, GPN, GS, HBAN, HD, HIG, HON, HSIC, IFF, INTU, IPG, IR, ITW, IVZ, JCI, JNJ, JPM, KEY, L, LLTC, LMT, LNC, LUK, MA, MAR, MCK, MCO, MDT, MET, MKC, MMC, MMM, MS, MTB, MTD, NDAQ, NOC, NTRS, NWL, OMC, PAYX, PBCT, PCAR, PFE, PFG, PGR, PH, PKI, PNC, PRU, PX, R, RHI, ROK, ROP, SCHW, SNA, SPGI, STI, STT, SWK, SYK, TEL, TMK, TMO, TROW, TRV, TSS, TXN, TXT, UNH, UNM, UNP, USB, UTX, VFC, VRSN, WAT, WFC, XRAY, XRX, XYL, ZBH	ABT, ACN, ADP, AFL, AIG, AJG, ALLE, AME, AMG, AMP, AON, BA, BAC, BBT, BEN, BK, BLK, C, CA, CB, CBG, CHD, CINF, CL, COL, CTAS, CTSH, CVS, DHR, DNB, DOW, ECL, EFX, ETN, FDX, FIS, FISV, FITB, GD, GLW, GPC, GPN, GS, HBAN, HD, HIG, HON, HSIC, INTU, IPG, ITW, IVZ, JNJ, JPM, KEY, L, LMT, LNC, LUK, MA, MAR, MCO, MDT, MET, MKC, MMC, MMM, MS, MTB, MTD, NDAQ, NOC, NTRS, NWL, OMC, PAYX, PCAR, PFE, PFG, PGR, PH, PKI, PNC, PRU, PX, R, RHI, ROP, SCHW, SNA, SPGI, STI, STT, SWK, SYK, TEL, TMK, TMO, TROW, TRV, TSS, TXT, UNH, USB, UTX, VRSN, WAT, WFC, XRAY
4	A, ACN, ADP, AFL, AIG, AJG, ALLE, AME, AMG, AMP, AON, APD, APH, AVY, BA, BAC, BBT, BEN, BK, BLK, BWA, C, CA, CAT, CB, CBG, CINF, CMA, COF, COL, CSX, CTSH, DFS, DHI, DLPH, DNB, DOV, ECL, EFX, EMR, ETFC, ETN, F, FDX, FITB, FLR, FLS, FOX, GD, GE, GPC, GS, HAR, HBAN, HIG, HON, INTC, IPG, IR, ITW, IVZ, JEC, JPM, KEY, L, LEG, LEN, LKQ, LNC, LRCX, LVLT, MA, MAR, MAS, MCHP, MCO, MET, MHK, MMC, MS, MTB, MTD, NTRS, NWS, NWSA, OMC, ORCL, PAYX, PBCT, PCAR, PFG, PH, PNC, PNR, PPG, PRU, PSX, PX, R, RF, ROK, ROP, SCHW, SNA, SPGI, STI, STT, SWK, TEL, TMK, TMO, TROW, TRV, UNM, UPS, USB, UTX, V, WFC, WU, WY, XYL, ZION	A, ACN, ADP, AFL, AIG, AJG, ALLE, AME, AMG, AMP, AON, APD, APH, BAC, BBT, BEN, BK, BLK, BWA, C, CA, CB, CBG, CMA, COF, COL, CSX, CTSH, DFS, DHI, DLPH, DOV, ECL, EFX, EMR, ETFC, ETN, F, FDX, FITB, FLR, FLS, GE, GPC, GS, HAR, HIG, HON, INTC, IR, ITW, IVZ, JEC, JPM, KEY, L, LEG, LEN, LKQ, LNC, LVLT, MA, MCHP, MCO, MET, MHK, MMC, MS, MTB, NTRS, NWS, NWSA, OMC, ORCL, PBCT, PCAR, PFG, PH, PNC, PNR, PPG, PRU, PSX, PX, R, RF, ROK, SCHW, SNA, SPGI, STI, STT, SWK, TEL, TMK, TMO, TROW, UNM, UPS, USB, UTX, WFC, WU, WY, XYL, ZION	A, ACN, ADP, AFL, AIG, AJG, ALLE, AME, AMG, AMP, APD, APH, AVY, BAC, BBT, BEN, BK, BLK, C, CA, CB, CBG, CINF, CMA, COF, CTSH, DFS, DHI, DLPH, DNB, ECL, EFX, ETFC, FDX, FITB, GE, GS, HON, IR, ITW, IVZ, JEC, JPM, KEY, L, LEG, LEN, LKQ, LNC, LVLT, MA, MCO, MHK, MMC, MS, MTB, MTD, NTRS, OMC, ORCL, PBCT, PCAR, PFG, PNC, PPG, PRU, RF, ROK, SCHW, SNA, SPGI, STI, STT, SWK, TEL, TMK, TMO, TROW, UNM, USB, V, WFC, WU, XYL, ZION
Пересечение объединений за все периоды	ADP, AME, AMG, AMP, BLK, CB, EMR, HIG, HON, ITW, IVZ, KEY, L, LNC, MAR, MET, MMC, NTRS, PCAR, PFG, PH, PRU, SNA, STT, TROW, UNM, UTX, WFC	AMG, AMP, BK, BLK, HIG, HON, ITW, IVZ, KEY, L, LNC, MET, MMC, NTRS, PCAR, PFG, PH, PRU, SCHW, SNA, STT, TROW, UNM, UTX	AMG, AMP, BLK, HON, ITW, IVZ, KEY, L, LNC, MMC, PFG, PRU, STT, TROW

Рассмотрим вхождение доминирующих акций в найденные плотные подграфы (Табл.11):

Таблица 11. Вхождение доминирующих акций в найденные квази-клики

Инструмент	Количество вхождений в объединение максимальных квази-клик при г = 0,75	Количество вхождений в объединение максимальных квази-клик при г = 0,85	Количество вхождений в объединение максимальных квази-клик при г = 0,95
BAC	2	2	2
AAPL	0	0	0
FB	0	0	0
GE	3	1	1
MSFT	0	0	0
F	1	1	0
INTC	1	1	0
CSCO	1	1	0
HPQ	0	0	0
PFE	1	1	1
MU	0	0	0
CMCSA	0	0	0
T	0	0	0
C	3	3	3
FCX	0	0	0

Как видно из Таблицы 11, большинство доминирующих акций из индекса S&P 500 не входит в найденные плотные подграфы, что может быть связано с тем, что среди рассматриваемых акций нет таких доминирующих акций, как SBER и GAZP, представленные на фондовом рынке России.

Таким образом, феномен, имеющий место на фондовом рынке России, когда доминирующие акции имеют связь в изменении доходности, не наблюдается на фондовом рынке США.



Заключение

Данная курсовая работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку и сравнение алгоритмов поиска плотных подграфов в графе рынка и проверка работы алгоритмов на анализе данных фондового рынка России и США. Была достигнута основная цель работы: получены качественные и количественные характеристики работы алгоритмов, проведено сравнение, и выявлено, что Degree Decomposition Algorithm поиска максимальной г-квази-клики в графе работает значительно быстрее, чем алгоритм Quick и решение задачи поиска максимальной г-квази-клики, сформулированной в виде задачи целочисленного программирования, а модифицированная версия Degree Decomposition Algorithm не показала ожидаемого прироста в скорости работы.

Для этого была изучена необходимая теоретическая база, рассмотрены алгоритмы поиска плотных подграфов в графе, реализованы алгоритмы: GRASP для поиска квази-клик в графе, Quick для поиска квази-клик в графе, решение задачи поиска максимальной г-квази-клики, сформулированной в виде задачи целочисленного программирования, Degree Decomposition Algorithm и его модифицированная версия для поиска всех максимальных квази-клик. Degree Decomposition Algorithm поиска максимальной г-квази-клики продемонстрировал хорошие результаты работы и был применен к данным о фондовых рынках России и США. Была разработана программа на языке Java, позволяющая обрабатывать входные данные в виде CSV-файла и получать выходные данные в структурированном виде. Анализ сравнения алгоритмов показал целесообразность применения Degree Decomposition Algorithm в графах рынков, содержащих 177 и 505 вершин.

Поставленная в работе цель была выполнена, все задачи решены. Degree Decomposition Algorithm поиска максимальной г-квази-клики в неориентированных графах может быть применен для других исследовательских задач изучения сетевых структур.



Список литературы

1. Применение рыночных графов к анализу фондового рынка России / А. Н. Визгунов, Б. И. Гольденгорин, В. А. Замараев, В. А. Калягин, А. П. Колданов, П. А. Колданов, П. М. Пардалос // Журнал исследований социальной политики. - 2015. - № 3 (15). - С. 66-81.

2. Boginski, V. On structural properties of the market graph / V. Boginski, S. Butenko, P. M. Pardalos // Innovations in financial and economic networks. - 2003. - С. 29-45.

3. Huang, W. Q. Network analysis of the Chinese stock market / W. Q. Huang, X. T. Zhuang, S. Yao // Physica A: Statistical Mechanics and its Applications. - 2009. - Т. 388. - № 14. - С. 2956-2964.

4. Network analysis of a financial market based on genuine correlation and threshold method / A. Namaki, A. H. Shirazi, R. Raei, G. R. Jafari // Physica A: Statistical Mechanics and its Applications. - 2011. - Т. 390. - № 21. - С. 3835-3841.

5. Vizgunov, А. Network approach for the Russian stock market / A. Vizgunov, A. Glotov, Р. М. Pardalos // Computational Management Science. - 2014. - Т. 11. - № 1-2. - С. 45-55.

6. Network-based representation of stock market dynamics: an application to American and Swedish stock markets / D. Jallo, D. Budai, V. Boginski, В. Goldengorin, Р. М. Pardalos // Models, Algorithms, and Technologies for Network Analysis. - 2013. - С. 93-106.

7. Newman, M. E. J. The structure and function of complex networks / M. E. J. Newman // SIAM review. - 2003. - Т. 45. - № 2. - С. 167-256.

8. Review of statistical network analysis: models, algorithms, and software / Т. В. Murphy, I. Gollini, А. White, М. Salter-Townshend // Statistical Analysis and Data Mining. - 2012. - Т. 5. - № 4. - С. 243-264.

9. Grimmett, G. What is Percolation? / G. Grimmett // Percolation. - Berlin, 1999. - С. 1-31.

10. Abello, J. Massive quasi-clique detection / J. Abello, M. G. C. Resende, S. Sudarsky // LATIN 2002: Theoretical Informatics. - 2002. - С. 598-612.

11. Maximal quasi-bicliques with balanced noise tolerance: Concepts and co-clustering applications / J. Li, К. Sim, L. Guimei, W. Limsoon // Proceedings of the 2008 SIAM International Conference on Data Mining / Society for Industrial and Applied Mathematics. - West Philadelphia, 2008. - С. 72-83.

12. Liu, G. Effective pruning techniques for mining quasi-cliques / G. Liu, L. Wong // Machine Learning and Knowledge Discovery in Databases. - 2008. - С. 33-49.

13. Matsuda, H. Classifying molecular sequences using a linkage graph with their pairwise similarities / Н. Matsuda, Т. Ishihara, А. Hashimoto // Theoretical Computer Science. - 1999. - Т. 210. - № 2. - С. 305-325.

14. Karp, R. M. Reducibility among combinatorial problems / R. M. Karp // Complexity of computer computations. - US, 1972. - С. 85-103.

15. Moon, J. W. On cliques in graphs / J. W. Moon, L. Moser // Israel journal of Mathematics. - 1965. - Т. 3. - №. 1. - С. 23-28.

16. Bron, C. Algorithm 457: finding all cliques of an undirected graph / С. Bron, J. Kerbosch // Communications of the ACM. - 1973. - Т. 16. - № 9. - С. 575-577.

17. Makino, K. New algorithms for enumerating all maximal cliques / К. Makino, Т. Uno // Scandinavian Workshop on Algorithm Theory. - Berlin, 2004. - С. 260-272.

18. Batagelj, V. Fast algorithms for determining (generalized) core groups in social networks / V. Batagelj, М. Zaverљnik //Advances in Data Analysis and Classification. - 2011. - Т. 5. - № 2. - С. 129-145.

19. Abello, J. On maximum clique problems in very large graphs / J. Abello, P. M. Pardalos, M. G. C. Resende // AT&T labs Reserrch Technical Report: TR98. - 1998. - Т. 32.

20. Mantegna, R. N. Hierarchical structure in financial markets / R. N. Mantegna // The European Physical Journal B-Condensed Matter and Complex Systems. - 1999. - Т. 11. - №. 1. - С. 193-197.

21. Rosario, N. An Introduction to Econophysics: Correlations and Complexity in Finance / N. Rosario, Н. Mantegna, Е. Stanley. - Cambridge : Cambridge University Press, 2000. - 148 р.

22. Universal and nonuniversal properties of cross correlations in financial time series / V. Plerou, Р. Gopikrishnan, В. Rosenow, L. Amaral, Н. Е. Stanley // Physical Review Letters. - 1999. - Т. 83. - №. 7. - С. 1471.

23. Noise dressing of financial correlation matrices / L. Laloux, P Cizeau, J. P. Bouchaud, M. Potters // Physical review letters. - 1999. - Т. 83. - № 7. - С. 1467.

24. Simple measure of similarity for the market graph construction / V. A. Kalyagin, А. Р. Koldanov, Р. А. Koldanov, Р. М. Pardalos, G. A. Bautin // Computational Management Science. - 2013. - Т. 10. - №. 2-3. - С. 105-124.

25. Batsyn, M. V. Models, Algorithms and Technologies for Network Analysis / M. V. Batsyn, V. А. Kalyagin, Р. М. Pardalos // Proceedings of Third International Conference on Network Analysis : Springer Proceedings in Mathematics and Statistics. - 2014. - Т. 104.

26. jGraphT [Electronic resource]. - Режим доступа : http://jgrapht.org//.

27. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees / C. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, M. A. Tsiarli // Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. - 2013. - С. 104-112.

28. Pattillo, J. On clique relaxation models in network analysis / J. Pattillo, N. Youssef, S. Butenko // European Journal of Operational Research. - 2013. - Т. 226. - № 1. - С. 9-18.

29. On maximum degree based quasi clique problem : Complexity and exact approaches / G. Pastukhov, А. Veremyev, V. Boginski, О. Prokopyev // Networks. - 2018. - Т. 71. - № 2. - С. 136-152.

30. Quick Algorithm [Electronic resource]. - Режим доступа : https://www.comp.nus.edu.sg/~wongls/projects/pattern-spaces/quick-v1/

31. IBM ILOG CPLEX [Electronic resource]. - Режим доступа : https://www.ibm.com/support/knowledgecenter/ru/SSSA5P_12.8.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html

32. Carraghan, R. An exact algorithm for the maximum clique problem / R. Carraghan, Р. М. Pardalos // Operations Research Letters. - 1990. - Т. 9. - № 6. - С. 375-382.

33. San Segundo, P. A new exact maximum clique algorithm for large and massive sparse graphs / Р. San Segundo, А. Lopez, Р. М. Pardalos // Computers & Operations Research. - 2016. - Т. 66. - С. 81-94.



Приложение 1

Парсер данных с Yahoo Finance

import csv

import pickle

import os

import ystockquote

def load_securities(filename='securities.csv', pickle_obj_filename='securities.pickle', skip_header=False):

if os.path.exists(pickle_obj_filename):

with open(pickle_obj_filename, 'rb') as f:

return pickle.load(f)

else:

res = []

with open(filename) as csvfile:

securities_reader = csv.reader(csvfile)

first_row = True

for row in securities_reader:

if skip_header and first_row:

first_row = False

continue

res.append(row[0])

with open(pickle_obj_filename, 'wb') as f:

pickle.dump(res, f)

return res

def get_yahoo_data():

# Settings

output_dir = 'results_yahoo_10' # Where the results will be placed

output_filename = 'data.csv' # Output filename

date_from = '2016-01-01' # Date format: YYYY-MM-DD

date_till = '2016-12-31' # Date format: YYYY-MM-DD

securities = load_securities('s&p_500_constituents.csv', pickle_obj_filename='s&500_secs.pickle', skip_header=True)

# securities = load_securities('securities_mcx.csv', pickle_obj_filename='securities_mcx.pickle', skip_header=False)

zip_results = True # Create archive of output directory

verbose = True # Print debug info

# Parsing

from urllib.error import HTTPError

if not os.path.exists(output_dir):

os.makedirs(output_dir)

with open(os.path.join(output_dir, output_filename), 'w') as f:

writer = csv.writer(f, delimiter=',')

for symbol in securities:

print('Process stock {}...'.format(symbol))

try:

res = ystockquote.get_historical_prices(symbol, date_from, date_till)

print('Get data. Save it.')

security_data = []

for date, info in res.items():

to_add = []

to_add.append(date)

to_add.append(symbol)

to_add.append(info['Close'])

to_add.append(info['Volume'])

security_data.append(to_add)

security_data = sorted(security_data, key=lambda row: row[0])

writer.writerows(security_data)

except HTTPError:

print('Info for stock {} not found'.format(symbol))

print('Finish.')

if __name__ == '__main__':

get_yahoo_data()

Размещено на Allbest.ru

...