Maximum Butterfly Generators Search in Bipartite Networks
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 subgr...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/1/88 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850116715592024064 |
|---|---|
| author | Jianrong Huang Guangyao Pang Fei Hao |
| author_facet | Jianrong Huang Guangyao Pang Fei Hao |
| author_sort | Jianrong Huang |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="double-struck">B</mi></semantics></math></inline-formula> of <i>G</i> such that maximize the number of butterflies in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="double-struck">B</mi></semantics></math></inline-formula> 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. |
| format | Article |
| id | doaj-art-b71347d7c0ab48ffa75b2d96cc6ef735 |
| institution | OA Journals |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-b71347d7c0ab48ffa75b2d96cc6ef7352025-08-20T02:36:15ZengMDPI AGMathematics2227-73902024-12-011318810.3390/math13010088Maximum Butterfly Generators Search in Bipartite NetworksJianrong Huang0Guangyao Pang1Fei Hao2Guangxi Key Laboratory of Machine Vision and Intelligent Control, Wuzhou University, Wuzhou 543002, ChinaGuangxi Key Laboratory of Machine Vision and Intelligent Control, Wuzhou University, Wuzhou 543002, ChinaSchool of Computer Science, Shaanxi Normal University, Xi’an 710119, ChinaBipartite 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="double-struck">B</mi></semantics></math></inline-formula> of <i>G</i> such that maximize the number of butterflies in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="double-struck">B</mi></semantics></math></inline-formula> 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.https://www.mdpi.com/2227-7390/13/1/88bipartite networksmaximum butterfly generatorsmaximum butterfly conceptbutterfly concept lattice |
| spellingShingle | Jianrong Huang Guangyao Pang Fei Hao Maximum Butterfly Generators Search in Bipartite Networks Mathematics bipartite networks maximum butterfly generators maximum butterfly concept butterfly concept lattice |
| title | Maximum Butterfly Generators Search in Bipartite Networks |
| title_full | Maximum Butterfly Generators Search in Bipartite Networks |
| title_fullStr | Maximum Butterfly Generators Search in Bipartite Networks |
| title_full_unstemmed | Maximum Butterfly Generators Search in Bipartite Networks |
| title_short | Maximum Butterfly Generators Search in Bipartite Networks |
| title_sort | maximum butterfly generators search in bipartite networks |
| topic | bipartite networks maximum butterfly generators maximum butterfly concept butterfly concept lattice |
| url | https://www.mdpi.com/2227-7390/13/1/88 |
| work_keys_str_mv | AT jianronghuang maximumbutterflygeneratorssearchinbipartitenetworks AT guangyaopang maximumbutterflygeneratorssearchinbipartitenetworks AT feihao maximumbutterflygeneratorssearchinbipartitenetworks |