О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности

doi:10.17223/19988605/56/10

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности	731 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/19988605/56/10

#гиперграфы

#максимальные биклики

#бинарные матрицы

#максимально полные подматрицы

Title: О связи биклик гиперграфа и всех максимально полных подматриц матрицы смежности
Title: On connection between bicliques of hypergraph and all maximally complete submatrices of adjacency matrix
Creator: Солдатенко, Александр Александрович
|
Семенова, Дарья Владиславовна
Date: 2021
DOI: 10.17223/19988605/56/10
Description: в рамках мероприятий по созданию и развитию региональных НОМЦ (Соглашение 075-02-2020-1534/1). Исследуется связь между задачей поиска всех максимально полных подматриц (0, 1)-матрицы и задачей по-иска всех максимальных биклик гиперграфов. Разработан алгоритм HFindMCS нахождения всех максимально полных подматриц (0, 1)-матрицы. Проведен теоретический анализ вычислительной сложности предложен-ного алгоритма и доказана его корректность. Вычислительные эксперименты показали эффективность алго-ритма HFindMCS на гиперграфах с ограниченной степенью. Предложена процедура перехода от решения задачи поиска всех максимально полных подматриц (0, 1)-матрицы к решению задачи поиска всех макси-мальных биклик гиперграфов. Nowadays hypergraph models are actively used in modeling and researching road and telecommunication networks, design semantic networks and representing linguistic knowledge, when solving problems of control of large systems. In this paper we investigate connection between problem of finding all maximally complete submatrices of (0, 1)-matrix and problem of finding all maximal bicliques of hypergraph. Problem of finding all maximally complete submatrices of (0, 1)-matrix is in demand in the analysis of formal context. This problem arises in searching for hidden relationships in subject areas and building ontologies of subject areas. Finding bicliques in networks represented by graph and hypergraph can increase the efficiency of solving the problem of addressing and routing. It is known that problem of finding all maximally complete submatrices of (0, 1)-matrix is #P-complete, and problem of finding all maximal bicliques at least hard as NP-hard problems. We propose new hypergraph algo-rithm HFindMCS for searching all maximally complete submatrices of (0, 1)-matrix. In the algorithm initial (0, 1)-matrix is repre-sented as a hypergraph H. We introduce new definition of l-level for algorithm are given. By the complete l-level of (0, 1)-matrix we mean all its complete submatrices with the number of rows equal to l. Main idea of algorithm HFindMCS is to generate all possible l-levels of (0, 1)-matrix and then select maximally complete submatrices from them. Moreover, number of l-levels does not exceed the degree of the hypergraph. Level hierarchy makes it easy to check if complete submatrix is maximal. This idea is well implemented in the language of hypergraphs. We proved that algorithm HFindMCS finds all maximally complete submatrices of incidence (0, 1)-matrix I of hypergraph H in time 2log2log2OMCSUU . The efficiency of the HFindMCS algorithm has been confirmed by computational experiments for hypergraphs with limited degree. A procedure for transition from solution of the problem of finding all maximally complete submatrices of the (0, 1)-matrix (MCSP) to solution of the problem of finding the maximum bicliques of hypergraph (MBGP for Hypergraphs) is proposed. The idea of the procedure consists in splitting elements of the set of all maximally complete submatrices and checking for satisfaction to a special form of the matrix. A special form of matrix is associated with the adjacency matrix of the hypergraph. Computational experiments have shown the high complexity of the transition from solving the MCSP problem to solving the MBGP for Hyper-graphs problem. To improve the performance of procedure for constructing a solution of MBGP for Hypergraphs problem, we assume to apply the described procedure to sets Pl, which are formed in HFindMCS algorithm. This modification can decrease a number of needed splits hence increase overall algorithm performance. It is also worth noting that researches on using of parallel computing technologies for the HFindMCS algorithm are perspective and will allow to reduce it operation time.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2021. № 56. С. 90-99
Language: rus