Maximum Butterfly Generators Search in Bipartite Networks

Jianrong Huang, Guangyao Pang and Fei Hao ()
Additional contact information
Jianrong Huang: Guangxi Key Laboratory of Machine Vision and Intelligent Control, Wuzhou University, Wuzhou 543002, China
Guangyao Pang: Guangxi Key Laboratory of Machine Vision and Intelligent Control, Wuzhou University, Wuzhou 543002, China
Fei Hao: School of Computer Science, Shaanxi Normal University, Xi’an 710119, China

Mathematics, 2024, vol. 13, issue 1, 1-21

Abstract: Bipartite graphs are widely used for modelling various real-world scenarios characterized with binary relations, such as, scholarly articles recommendation with author-paper relations, and product recommendation with user-product relations. Particularly, maximum butterfly as a special cohesive subgraph of bipartite graphs, is playing an critical role in many promising application such as recommendation systems and research groups detection. Enumerating maximal butterfly has been proved to be a NP-hard and suffers time and space complexity. To conquer this challenge, this paper pioneers a novel problem called maximal butterfly generators search (MBGS) for facilitating the detection of maximal butterflies. The MBGS problem is to find a subgraph B of G such that maximize the number of butterflies in B and it is mathematically proved to NP-Hard. To address this problem, an equivalence relation theorem between maximum butterfly generator and maximum butterfly concept is presented. Furthermore, an effective MBGS search algorithm is proposed. Extensive experiments on real-world networks with ground-truth communities and interesting case studies validated the effectiveness and efficiency of our MBGS model and algorithm.

Keywords: bipartite networks; maximum butterfly generators; maximum butterfly concept; butterfly concept lattice (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/1/88/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/1/88/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2024:i:1:p:88-:d:1555784

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().