Сибирский федеральный университет

Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций

Конференция: Institute of Electrical and Electronics Engineers Inc.; 13 September 2021 through 17 September 2021; 13 September 2021 through 17 September 2021

Год издания: 2021

Идентификатор DOI: 10.1109/OPCS53376.2021.9588790

Ключевые слова: hypergraph, maximal induced bicliques, real networks

Аннотация: In this paper algorithm for finding all maximal induced bicliques in network is considered. It is assumed that the network is represented by a graph or hypergraph. Induced biclique is a bipartite subgraph in which every vertex of one part adjacent to each vertex of another part. The algorithm uses in its work statement of the theorem on the equivalence of induced bipartite subhypergraphs of a hypergraph and bipartite subgraphs of a vertex graph. This fact allows to apply this algorithm to a graphs as well as to hypergraphs. An interpretation of the selected bicliques for real networks is proposed. For this bicliques corresponding visualizations in road networks are given. We provide computational experiments for considered algorithm on real road networks. Results of experiments are shown that algorithm solve maximal induced bicliques generation problem in real time. Also given types and number of bicliques that contained in each network. © 2021 IEEE

Журнал: Proceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021

Номера страниц: 121-125

ISSN журнала: 00177065

• Soldatenko A. (Institute of Mathematics and Computer Science, Siberian Federal University, Krasnoyarsk, Russian Federation)
• Semenova D. (Institute of Mathematics and Computer Science, Siberian Federal University, Krasnoyarsk State Medical University, Krasnoyarsk, Russian Federation)

• Scopus
• Ядро РИНЦ (eLIBRARY.RU)