TY - JOUR
T1 - Algorithm for Mining Maximal Balanced Bicliques using Formal Concept Analysis
AU - Ilkhomjon, Sadriddinov
AU - Peng, Sony
AU - Siet, Sophort
AU - Kim, Dae Young
AU - Park, Doo Soon
AU - Yi, Gangman
N1 - Publisher Copyright:
Authors
PY - 2024
Y1 - 2024
N2 - One of the most fundamental models for cohesive subgraph mining in network analysis is that which involves the use of cliques. In bipartite graph analysis, the detection of maximal balanced bicliques (MBB) is an important problem with numerous applications, including VLSI design, protein interactions, and social networks. However, MBB detection is difficult, complex, and time-consuming. In the current paper, to address these disadvantages, we propose a new algorithm for detecting MBB using formal concept analysis (FCA) on bipartite graphs. We applied an algorithm to compute formal concepts from the formal context, which is an alternative way of representing a bipartite graph.We proved that the MBB problem is equivalent to the semi-equiconcept enumeration problem in the formal context. Therefore, the semi-equiconcept mining algorithm was applied to theMBB enumeration problem. However, since the existing FCA algorithm cannot be directly applied to mine all MBBs, the FCA algorithm was modified in its entirety. Thorough asymptotic analysis was performed on the proposed algorithm. Experiments were also conducted on various real-world bipartite graphs to which the proposed algorithm was applied, and our results were found to be significantly better than those obtained by the preexisting algorithm.
AB - One of the most fundamental models for cohesive subgraph mining in network analysis is that which involves the use of cliques. In bipartite graph analysis, the detection of maximal balanced bicliques (MBB) is an important problem with numerous applications, including VLSI design, protein interactions, and social networks. However, MBB detection is difficult, complex, and time-consuming. In the current paper, to address these disadvantages, we propose a new algorithm for detecting MBB using formal concept analysis (FCA) on bipartite graphs. We applied an algorithm to compute formal concepts from the formal context, which is an alternative way of representing a bipartite graph.We proved that the MBB problem is equivalent to the semi-equiconcept enumeration problem in the formal context. Therefore, the semi-equiconcept mining algorithm was applied to theMBB enumeration problem. However, since the existing FCA algorithm cannot be directly applied to mine all MBBs, the FCA algorithm was modified in its entirety. Thorough asymptotic analysis was performed on the proposed algorithm. Experiments were also conducted on various real-world bipartite graphs to which the proposed algorithm was applied, and our results were found to be significantly better than those obtained by the preexisting algorithm.
KW - Bipartite Graph
KW - Bipartite graph
KW - Formal Concept Analysis
KW - Formal concept analysis
KW - Lattices
KW - Maximal Balanced Biclique
KW - Shape
KW - Social networking (online)
KW - Time complexity
KW - Web pages
UR - http://www.scopus.com/inward/record.url?scp=85197078718&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2024.3419838
DO - 10.1109/ACCESS.2024.3419838
M3 - Article
AN - SCOPUS:85197078718
SN - 2169-3536
SP - 1
JO - IEEE Access
JF - IEEE Access
ER -