English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Enumerating maximal $k$-biplexes (MBPs) of a bipartite graph has been usedfor applications such as fraud detection. Nevertheless, there usually exists anexponential number of MBPs, which brings up two issues when enumerating MBPs,namely the effectiveness issue (many MBPs are of low values) and the efficiencyissue (enumerating all MBPs is not affordable on large graphs). Existingproposals of tackling this problem impose constraints on the number of verticesof each MBP to be enumerated, yet they are still not sufficient (e.g., theyrequire to specify the constraints, which is often not user-friendly, andcannot control the number of MBPs to be enumerated directly). Therefore, inthis paper, we study the problem of finding $K$ MBPs with the most edges calledMaxBPs, where $K$ is a positive integral user parameter. The new proposal wellavoids the drawbacks of existing proposals. We formally prove the NP-hardnessof the problem. We then design two branch-and-bound algorithms, among which,the better one called FastBB improves the worst-case time complexity to$O^*(\gamma_k^ n)$, where $O^*$ suppresses the polynomials, $\gamma_k$ is areal number that relies on $k$ and is strictly smaller than 2, and $n$ is thenumber of vertices in the graph. For example, for $k=1$, $\gamma_k$ is equal to$1.754$. We further introduce three techniques for boosting the performance ofthe branch-and-bound algorithms, among which, the best one called PBIE canfurther improve the time complexity to $O^*(\gamma_k^{d^3})$ for large sparsegraphs, where $d$ is the maximum degree of the graph. We conduct extensiveexperiments on both real and synthetic datasets, and the results show that ouralgorithm is up to four orders of magnitude faster than all baselines andfinding MaxBPs works better than finding all MBPs for a fraud detectionapplication.

Maximum $k$-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach