On connection between bicliques of hypergraph and all maximally complete submatrices of adjacency matrix.pdf Гиперграфы являются расширением классической теории графов на случай, когда ребро графа может содержать число вершин, отличное от двух. Изначально гиперграфы нашли практическое применение в моделировании реляционных баз данных и комбинаторной химии [1, 2]. Возможность объединения нескольких вершин одним ребром дает мощный инструмент для моделирования различных сетей и систем. В настоящее время гиперграфовые модели активно применяются при построении и исследовании дорожных и телекоммуникационных сетей [3, 4], для построения семантических сетей и представления лингвистических знаний [5, 6], при решении задач управления большими системами [7]. Значительная часть задач исследований указанных моделей сводится к проблемам определения различных конфигураций. Под конфигурацией понимается любая система подмножеств конечного множества [8]. Особый интерес вызывают задачи перечислительного типа [8], в которых существование интересующих исследователя конфигураций не вызывает сомнения, вопрос - лишь в количестве и способе их представления. Большинство задач, связанных с поиском различных конфигураций в данных, имеет высокую сложность, с которой ничего нельзя сделать, однако поиск новых моделей и алгоритмов может повысить производительность вычислений. При этом использование асимптотически более медленных алгоритмов может быть оправдано тем, что для наборов данных, организованных определенным образом, они будут эффективнее [9]. Задача может быть сложной в общем случае, но иметь эффективный алгоритм для некоторого частного случая или класса объектов. Если сети и системы представить гиперграфами, то интересующие конфигурации удобно описывать на языке (0, 1)-матриц [10]. Например, задача выделения всех максимальных биклик гиперграфа сводится к задаче построения следующих конфигураций - полных единичных подматриц (0, 1)-матрицы [11]. В настоящей работе рассматривается задача нахождения всех максимально полных подматриц (0, 1)-матрицы и схожая с ней задача поиска максимальных биклик гиперграфа. Поиск максимально полных единичных подматриц востребован в задаче нахождения всех формальных понятий, которая возникает при поиске скрытых взаимосвязей и построении онтологий предметных областей [5]. Поиск максимальных биклик связан с задачей адресации внутри коммуникационной сети [3]. В сетях, представленных графами и гиперграфами, выделение биклик способно повысить эффективность решения задачи адресации и маршрутизации [3, 12, 13]. Также максимальные биклики востребованы 90 О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности в анализе данных и при кластеризации, имеют широкое применение при исследовании генных структур и социальных сетей [14-16]. Заметим, что задачи поиска таких конфигураций являются ftP-полными [17]. В работе предлагаются новый алгоритм выделения максимально полных подматриц (0, 1)-мат-рицы, основанный на теории гиперграфов, и процедура выделения всех максимальных биклик на основе всех максимально полных подматриц. В первом разделе статьи приводятся необходимые понятия и определения (0, 1)-матриц и теории гиперграфов. Второй раздел содержит описание предлагаемого алгоритма, доказательство его корректности и теоретический анализ вычислительной сложности. В третьем разделе представлены результаты вычислительных экспериментов. 1. Основные понятия и определения Пусть задана (0, 1)-матрица I размера n х т, где n > 1, т > 1 [8, 10]. Определение 1. Полной подматрицей (0, 1)-матрицы называется подматрица, все без исключения элементы которой равны 1 [18]. Определение 2. Максимально полной подматрицей называется полная подматрица, не содержащая никакой другой максимально полной матрицы [18]. Последнее можно трактовать следующим образом: максимально полной подматрицей называется полная подматрица, не входящая ни в какую другую полную подматрицу. Матрица I по своей сути может представлять множество всевозможных комбинаторных объектов, примерами которых являются: матрицы инцидентности и смежности графов и гиперграфов, контекст в анализе формальных понятий, реализация конечного случайного множества и др. [1, 5, 8, 10]. Пусть задан (n, т)-гиперграф H = (X, U), где X - конечное множество вершин, U - конечное семейство гиперребер гиперграфа, при этом X - 1, IU - 1 и всякое гиперребро гиперграфа - некоторое подмножество множества X. Пусть X(u) - множество всех вершин, инцидентных гиперребру u е U, а U(x) - множество гиперребер, инцидентных вершине x е X. Двойственным к гиперграфу H = (X, U) называют гиперграф H* = (X*, U*), где X* = U - множество вершин двойственного гиперграфа, U* = U(x) - семейство гиперребер двойственного гиперграфа для всякого x е X. Одним из способов задания гиперграфа является (0, 1)-матрица инцидентности I, где 1 ставится в случае, когда гиперребро содержит вершину, и 0 в противном случае. Будем называть степенью гиперребра и е U мощность множества |X(u)|. Приведем необходимые для дальнейшего изложения определения [19]. Определение 3. Подгиперграфом, индуцированным множеством вершин X, называется гиперграф H = (X, U), где U = {u': X(u') = X(u) n X Ф 0, и е U}. Заметим, что в рамках определения 3 для U всегда справедливо высказывание: X(u) n X| > 2, или \\u'\\ = 1. Известно определение двудольности гиперграфа [20], которое аналогично 2-раскраске: гиперграф H = (X, U) называется двудольным, когда множество вершин X может быть разделено на два множества So и S таким образом, что So u S = X, So nS\\ =0, и для всякого гиперребра u е U выполнено X(u) n So| = 1. В работе используется следующее определение двудольности подгиперафа. Определение 4. Подгиперграф H' = (X, U) является двудольным, если существует разбиение So u S1 = X такое, что So n S1 = 0 и неравенства \\So n X(u ')| < 1, IS1 n X(u')| < 1 выполняются для любого гиперребра u е U . Приведем определение реализации гиперграфа в виде вершинного графа L2(H) [21]. Определение 5. Вершинным графом гиперграфа H = (X, U) называется граф L2(H) = (X, E), множество вершин которого совпадает с множеством вершин X гиперграфа H, при этом две вершины графа L2(H) смежны тогда и только тогда, когда смежны соответствующие им вершины гиперграфа H. 91 А.А. Солдатенко, Д.В. Семенова Нетрудно показать, что подгиперграф H' = (X, U) является двудольным тогда и только тогда, когда в вершинном графе L2H) гиперграфа H существует двудольный подграф, индуцированный множеством вершин X. Определение 6. Двудольный граф называется полным двудольным графом (бикликой), если всякая вершина одной доли соединена со всеми вершинами второй доли [22]. Данное определение можно сформулировать иначе: если двудольный граф содержит все возможные ребра, не нарушающие условия двудольности, то такой граф называется полным двудольным графом. К поиску биклик сводится ряд теоретико-графовых задач [17], которые относятся к классу #Р-полных или NP-полных задач, поскольку в общем случае число максимальных биклик экспоненциально зависит от размера графа [23]. Определение 7. Будем говорить, что подгиперграф H' = (X, U), где So u Si = X , So n Si = 0 и U = {u : so, si e X(u), so e So, si e Si}, называется полным двудольным подгиперграфом (бикликой) исходного гиперграфа H. Определение 8. Максимальная биклика - это биклика, которая не может быть расширена путем включения дополнительных смежных вершин, или, что эквивалентно, для максимальной биклики не существует другой биклики, которая полностью включает данную. Определение 8 справедливо как для графов, так и для гиперграфов. Задача поиска максимальной биклики хорошо известна в теории графов. При этом выделяют два варианта: задача поиска максимальной биклики с наибольшим числом вершин и задача поиска максимальной биклики с наибольшим числом ребер. Данные задачи возникают при обнаружении аномалий, анализе генных структур, анализе социальных структур [24]. Любой из вариантов данной задачи для связного графа произвольного вида является NP-трудной [25]. Помимо поиска одной максимальной биклики, не ослабевает интерес к задаче MBGP (Maximal Biclique Generation Problem), которая состоит в поиске всех возможных максимальных биклик для любого заданного графа. Известно, что MBGP не может быть решена за полиномиальное время относительно размера ввода, поскольку размер вывода может быть экспоненциально большим по n [25]. Сложность данной задачи не меньше, чем сложность задачи поиска одной максимальной биклики, которая является NP-трудной задачей [24]. Задача MBGP для графов может быть расширена на гиперграфы. В частности, для бигипергра-фов задача MBGP исследована в [20]. Под бигиперграфом понимается гиперграф вида H = (H0, H1), где всякое гиперребро гиперграфов Ho и Hi содержится в H. При этом вводится определение двудольного гиперграфа согласно устойчивости множества вершин. Множество вершин S с Vустойчиво в H, если S не содержит гиперребер из H, i = o, 1. Гиперграф H = (H°, H1) называется двудольным, если существует разбиение S° u S1 = V, где Si устойчиво в Hi, i = o, i. В данной работе исследуется задача поиска всех возможных максимальных биклик для любого заданного гиперграфа. Задача 1 (MBGP for Hypergraphs). Дан гиперграф H = (X, U) без кратных гиперребер, требуется найти множество всех максимальных биклик. Заметим, что задача нахождения биклик в графе тесно связана с поиском подматриц специального вида [11]. Проведем связь между задачей нахождения максимальных биклик в гиперграфе и задачей поиска максимально полных подматриц (0, ^-матрицы. Для двудольного подгиперграфа H = (X , U ) запишем его эквивалентное представление в виде (o, ^-матрицы смежности вершинного графа L2(H'). Обозначим So, Si - доли подгиперграфа H', мощности которых равны c и d соответственно. Поскольку вершинный граф L2H) тоже является двудольным, его матрица смежности представима в виде: A' = fO B' Л B'T O, (i) d У где Oc, Od - нулевые матрицы порядка c и d соответственно, а B' - матрица размера c х d, которая отражает смежность вершин между долями So и Si [11]. Очевидно, что в случае, когда подгиперграф H' 92 О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности является бикликой, матрица B является полной подматрицей матрицы A. Нетрудно показать, что проверка всякой подматрицы из множества всех максимально полных подматриц выполнима за линейное время относительно размера подматрицы. Таким образом, для поиска биклик в гиперграфе H = (X, U) требуется найти такие полные подматрицы B' матрицы смежности A вершинного графа Li(H), для которых будет существовать подматрица вида (1), что приводит к задаче поиска всех максимально полных подматриц (maximally complete submatrices) исходной (0, 1)-матрицы. Задача 2 (Maximally Complete Submatrices Problem, MCSP). Дана (0, 1)-матрица I, требуется найти множество всех максимально полных подматриц. Заметим, что максимально полные подматрицы могут представлять различные комбинаторные объекты [8], а задача их поиска носит перечислительный характер и принадлежит классу сложности #.Р-полных задач [5, 8]. Применение алгоритмов решения задачи выделения максимально полных подматриц ограничивается высокой трудоемкостью на матрицах большой размерности. 2. Алгоритм нахожцения всех максимально полных подматриц для заданной (0, 1)-матрицы Основываясь на определениях теории гиперграфов и (0, 1)-матриц, опишем алгоритм для нахождения максимально полных подматриц исходной (0, 1)-матрицы. Для этого понадобится понятие /-уровня (0, 1)-матрицы. Определение. Полным /-уровнем (0, 1)-матрицы будем называть все ее полные подматрицы с числом строк, равным /. Всякую полную подматрицу инцидентности гиперграфа H = (X, U) с числом строк, равным /, можно описывать как подгиперграф H' = (X, U(X)), где X с X- множество вершин, при этом \\Х\\ = /, а U(X) с U - множество гиперребер. Следовательно, /-уровень в терминах гиперграфов описывается следующей системой множеств: P/ = {H' = (X, U(X)) : X\\ = /, X с X}. Также отметим, что гиперграфу H соответствует (0, 1)-матрица инцидентности I с заданным лексикографическим порядком как для строк, так и для столбцов. Заметим, что в общем случае всякую (0, 1)-матрицу можно представить в виде гиперграфа независимо от ее семантики, и наоборот. Обозначим множество всех максимально полных подматриц как MCS. Идея алгоритма заключается в генерации всех возможных /-уровней (0, 1)-матрицы и последующем выделении максимально полных подматриц. Иерархия уровней позволяет с легкостью проверять. является ли полная подматрица максимальной. Данная идея хорошо реализуется на языке гиперграфов. Приведем описание алгоритма HFindMCS и его вспомогательной функции Generate-Combinations(H, /) на псевдокоде. Алгоритм HFindMCS Вход: гиперграф H = (X, U) Выход: множество MCS Для / := 1, ..., А выполнять Pi := GenerateCombinations(H, /) Конец цикла P := и pt 1 = Л,...Д 5. MCS := {0} 6. Для (Y, U(Y)) е P выполнять 7. Если U(Y) * U(Y) : V(Y', U(Y)) е MCS тогда 8. MCS := MCS и (Y, U(Y)) 9. Конец условия 10. Конец цикла 11. Возвратить MCS Функция GenerateCombinations (H, /) 1. Pi := {0} 2. Для u е U выполнять 3. Clu := {X : X сX(u), X\\ = /} 4. Для X е Clu выполнять 5. Pi[X ] := Pi[X ] и u 6. Конец цикла 7. Конец цикла 8. Возвратить Pi 93 А.А. Солдатенко, Д.В. Семенова Теорема 1. Алгоритм HFindMCS корректно решает задачу MCSP для (0, 1)-матрицы инцидентности I гиперграфа H = (X, U) со степенью А за время, не превышающее O log (IMCS\\)\\U\\2 А2а log (2а |U|) Доказательство. Алгоритм HFindMCS принимает на вход гиперграф H = (X, U) без кратных гиперребер и вершин. Для простоты изложения будем считать, что максимальная степень гиперребра меньше максимальной степени вершины, т.е. max|X(u)| < max|U(x)|. Это условие необходимо для и е U x е X быстродействия алгоритма, в общем случае алгоритм можно применять к любому гиперграфу без кратных гиперребер. Если условие не выполнено, то алгоритм HFindMCS применяется к двойственному гиперграфу H* = (X*, U*). Далее будем обозначать максимальную степень гиперребра как А = max| X (и) и называть степенью гиперграфа [19]. и е U На шагах 1-3 последовательно формируются множества Pi, соответствующие полным /-уровням, где I = 1, ..., А. Для каждого значения /, соответствующего требуемому уровню (0, 1)-матрицы, на шаге 2 вызывается функция GenerateCombinations(H, /). Вызываемая функция для каждого гиперребра и е U выполняет генерацию всех возможных подмножеств вершин X с X(u) таких, что XI = і. Множество всех возможных подмножеств /-уровня обозначим как Clu . Каждое сгенерированное множество X индуцирует исходный гиперграф H в подгиперграф H' = (X, U). Построение множества U происходит последовательно путем просмотра всех гиперребер и е U. Исходя из этого, множество U индуцированного подгиперграфа формируется в лексикографическом порядке. Полученный подгиперграф H' однозначно сопоставим с полной подматрицей матрицы I, а множество всех таких подги-перграфов образует полный /-уровень (0, 1)-матрицы, т.е. множество Pi. Выполняя данную процедуру для каждого уровня i = 1, ..., А, получим набор множеств Pi, содержащих подгиперграфы, матрицы инцидентности которых соответствуют всем полным подматрицам матрицы инцидентности I гиперграфа. Очевидно, что полные подматрицы с наибольшим количеством строк, равным А, будут являться максимально полными, поскольку они гарантированно не вложены ни в какие другие полные подматрицы. При формировании набора множеств Pi процесс генерации сочетаний для всех уровней не превосходит І1 = O(|U|2A). Действительно, поскольку на каждом уровне необходимо генерировать сочетания для каждого гиперребра и количество уровней / = 1, ., А, то \\U\\Clu+...+ \\и\\Сц =\\U\\{clu + ... + Сц ) = | t/| (2Л -і) = о(|/У|2л). Отметим, что всякое множество X е с[ является лексикографически упорядоченным, и любые X, X2 из сі являются сравнимым. Эти два факта позволяют для хранения и обновления множеств Pi использовать древовидные структуры данных, в частности красно-черные деревья. Очевидно, что сравнение X[ и X2 выполнимо за О(А), так как мощность всякого X не превосходит А. А поиск и добавление элементов в красно-черном дереве не превосходят і2 = O(Alog(|U|2A)) [26]. Следовательно, выполнение шагов 1-3 алгоритма HFindMCS требует не более T1 = *1*2 = O |U| А2а log (IU| 2а)" На шаге 4 алгоритма HFindMCS полученный на шагах 1-3 набор множеств Pi объединяется в упорядоченное множество P следующим образом: объединение осуществляется в порядке убывания значения уровня / с сохранением у каждого подгипреграфа лексикографического порядка на множестве вершин и на множестве гиперребер. Следовательно, формирование множества P выполнимо за время равное T2 = О(1). Множество P является допустимым множеством решений задачи поиска всех максимально полных подматриц и соответствующих им гиперграфов. Формирование множества MCS осуществляется на шагах 5-10 путем просматривания множества P от подгиперграфов с наибольшей мощностью 94 О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности множества вершин до обладающих наименьшей мощностью. Изначально в MCS добавляются подгиперграфы с числом вершин, равным А, из множества P. Такие подгиперграфы всегда будут соответствовать максимально полным подматрицам. Далее последовательно просматриваются остальные элементы множества P, и в множество MCS добавляются только такие подгиперграфы, множества гиперребер которых еще не встречались. После этого множество MCS будет содержать все подгиперграфы, соответствующие максимально полным подматрицам матрицы инцидентности I. Следовательно, алгоритм корректно решает задачу MCSP. Заметим, что сравнение подгиперграфов по множеству гиперребер требует не более O(|U|) времени. Это следует из того, что максимальная мощность множества гиперребер подгиперграфа не превосходит |U|. Поскольку по построению все комбинации вершин для подгиперграфов в множестве P различны, то соответствующие им полные подматрицы могут содержаться в других только в случае, когда множество гиперребер совпадает. Это соответствует тому, что полная подматрица содержится в полной подматрице с большим числом строк. Для хранения и обработки множества MCS в работе используются красно-черные деревья, что облегчает поиск и добавление новых элементов. Последовательно просматривая множество P, для каждого элемента выполняется поиск в множестве MCS за время T3 =O [[ log (IMCS\\ )] , аналогичное время требуется для добавления нового элемента. Таким образом построение множества MCS требует времени не более чем ТТТЗ = O [log (|MCS|)[2 A2a log (Ад АА)]. Теорема доказана. Искомому множеству MCS будет соответствовать множество подгипреграфов, матрицы инцидентности которых максимально полные. Отметим, что время работы алгоритма HFindMCS существенно зависит от параметра А, который соответствует максимальной степени гиперребра или вершины. Существует множество алгоритмов для нахождения максимально полных подматриц [6]. Всем известным алгоритмам нахождения комбинаторных объектов, связанных с максимально полными подматрицами, присущ комбинаторный взрыв на выходе в виде множества |MCS|. Наиболее универсальным является широко известный алгоритм нахождения всех формальных понятий формального контекста Close-by-One (CbO) [6]. Асимптотическая сложность данного алгоритма оценивается как O(MCS||U||X|2). В общем случае предложенный алгоритм HFindMCS асимптотически медленнее алгоритма CbO, однако для наборов данных, организованных определенным образом [9], он будет эффективнее алгоритма CbO. В частности, для квадратных матриц алгоритм HFindMCS будет асимптотически быстрее алгоритма CbO при выполнении условия A2Alog(2A|X|) < |X|. Решением задачи MBGP for Hypergraphs является множество максимальных биклик гиперграфа H = (X, U). Обозначим множество максимальных биклик как BC. Применение алгоритма HFindMCS к матрице смежности вершинного графа L2(H) дает на выходе множество всех максимально полных подматриц MCS в виде подгиперграфов. Поскольку алгоритм HFindMCS применяется к матрице смежности, то всякий подгиперграф H' = (X, U) из множества MCS фактически отражает пару множеств вершин X и U. Кратко опишем процедуру нахождения множества BC на основе множества MCS. Если элемент множества MCS удовлетворяет условию (1), то он является бикликой, в противном случае происходит расщепление элемента на два по тем вершинам, которые смежны внутри доли X или U, чтобы убрать смежность. После этого необходимо выбрать максимальные биклики из полученного множества биклик. 3. Вычислительные эксперименты и сравнение алгоритмов В работе проводились две серии экспериментов. Первая серия экспериментов направлена на оценку результативности предложенного алгоритма HFindMCS решения задачи MCSP. Вторая серия экспериментов призвана оценить эффективность процедуры перехода от решения задачи MCSP 95 А.А. Солдатенко, Д.В. Семенова к решению задачи MBGP for Hypergraphs. Вычислительные эксперименты проводились на ПК с процессором AMD Ryzen 5 3600 6-Core Processor 3,60 ГГц и ОЗУ объемом 16 Гбайт. Эксперименты первой серии проводились на гиперграфах с различным числом вершин \\Х\\ и гиперребер |U\\, а также различной степенью гиперграфа А. Результаты вычислительных экспериментов представлены в табл. 1. Таблица 1 Результаты вычислительных экспериментов алгоритма HFindMCS А m |U| |MCS| t, с 5 100 100 276 0,002 1 000 1 000 2 055 0,012 10 000 9 904 19 609 0,145 25 000 24 540 48 220 0,421 10 100 100 1 199 0,041 1 000 1 000 3 786 0,422 10 000 9 999 22 037 4,938 25 000 24 989 52 501 13,571 13 100 100 2 570 0,339 1 000 1 000 7 056 3,521 10 000 10 000 26 102 38,091 25 000 24 999 57 420 497,621 Таблица 1 хорошо демонстрирует сложность задачи поиска всех максимально полных подматриц. Число максимально полных подматриц соответствует столбцу \\МСУ| и, как видно, даже при малом значении степени гиперграфа А оно достаточно велико. Учитывая, что все алгоритмы точного решения задачи поиска всех максимально полных подматриц зависят от мощности выходного множества MCS, алгоритм HFindMCS обладает приемлемым временем работы относительно размера исходного гиперграфа. Для второй серии экспериментов были сгенерированы гиперграфы H = (X, U) с фиксированной степенью вершин. Для гиперграфов строились вершинные графы L2H). К матрицам смежности вершинного графа L2H) применялся алгоритм HFindMCS для нахождения множества MCS. Далее к множеству MCS применялась процедура нахождения всех максимальных биклик. В табл. 2 приводятся параметры гиперграфа H, включая максимальную степень вершины А', а также время нахождения множества BC. Т аблица 2 Результаты вычислительных экспериментов расщепления множества MCS А' m |U| |MCS| |BC| t, с 3 100 90 202 191 0,040 500 439 2 055 961 0,863 5 100 76 476 453 1,366 500 362 2 506 2 208 40,848 7 100 73 1 234 757 30,132 500 317 5 738 4 343 653,944 Из табл. 2 видно, что процедура нахождения всех максимальных биклик из множества MCS требует значительных временных затрат. Это связано с тем, что подгиперграфы, соответствующие максимально полным подматрицам, не обязательно являются бикликами. Из-за этого процедура расщепления может вызвать геометрический рост количества проверяемых подгиперграфов. Заключение В работе исследуются две задачи: поиск всех максимально полных подматриц (0, 1)-матрицы (MCSP) и поиск всех максимальных биклик гиперграфов (MBGP for Hypergraphs). Для решения задачи MCSP разработан гиперграфовый алгоритм HFindMCS. Установлено, что время формирования 96 О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности множества MCS алгоритмом HFindMCS существенно зависит от входного гиперграфа и составляет O^log(|ЖС^|)|t/|2 А2Д log(2Д |^|. Разработанный алгоритм имеет высокую вычислительную сложность относительно известных алгоритмов. Однако использование данного алгоритма может быть оправдано тем, что для гиперграфов, обладающих малой степенью, он будет значительно эффективнее, что подтверждено вычислительными экспериментами для специального вида гиперграфов. Предложена процедура перехода от решения задачи MCSP к решению задачи MBGP for Hypergraphs, идея которой заключается в расщеплении элементов множества MCS и проверке их на соответствие специальному виду. Вычислительные эксперименты показали высокую трудоемкость перехода от решения задачи MCSP к решению задачи MBGP for Hypergraphs. Для повышения производительности процедуры построения решения задачи MBGP for Hypergraphs предполагается применение описанной процедуры перехода к промежуточным множествам Pi, формируемым в процессе работы алгоритма HFindMCS. Такая модификация позволит сократить необходимое число расщеплений и тем самым повысить производительность алгоритма. Также стоить отметить, что для алгоритма HFindMCS перспективны исследования по применению технологий параллельных вычислений для улучшения времени его работы.

Скачать электронную версию публикации