Тип публикации: статья из журнала
Год издания: 2021
Идентификатор DOI: 10.17223/19988605/56/10
Ключевые слова: hypergraph, maximal bicliques, (0, 1)-matrix, maximally complete submatrices
Аннотация: 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 algorithm HFindMCS for searching all maximally complete submatrices of (0, 1)-matrix. In the algorithm initial (0, 1)-matrix is represented 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 O[log vertical bar MCS vertical bar)vertical bar U vertical bar(2)Delta 2(Delta) log(2(Delta)vertical bar U vertical bar)]. 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 Hypergraphs 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. 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 algorithm HFindMCS for searching all maximally complete submatrices of (0, 1)-matrix. In the algorithm initial (0, 1)-matrix is represented 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 Olog(MCS) U 2 ∆2∆ log(2∆ U ) . 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 Hypergraphs 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. © 2021 Tomsk State University. All rights reserved.
Журнал: VESTNIK TOMSKOGO GOSUDARSTVENNOGO UNIVERSITETA-UPRAVLENIE VYCHISLITELNAJA TEHNIKA I INFORMATIKA-TOMSK STATE UNIVERSITY JOURNAL OF CONTROL AND COMPUTER SCIENCE
Выпуск журнала: Is. 56
Номера страниц: 90-99
ISSN журнала: 19988605
Место издания: TOMSK
Издатель: TOMSK STATE UNIV