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

For clustering of an undirected graph, this paper presents an exact algorithmfor the maximization of modularity density, a more complicated criterion toovercome drawbacks of the well-known modularity. The problem can be interpretedas the set-partitioning problem, which reminds us of its integer linearprogramming (ILP) formulation. We provide a branch-and-price framework forsolving this ILP, or column generation combined with branch-and-bound. Aboveall, we formulate the column generation subproblem to be solved repeatedly as asimpler mixed integer linear programming (MILP) problem. Accelerationtechniques called the set-packing relaxation and themultiple-cutting-planes-at-a-time combined with the MILP formulation enable usto optimize the modularity density for famous test instances including oneswith over 100 vertices in around four minutes by a PC. Our solution method isdeterministic and the computation time is not affected by any stochasticbehavior. For one of them, column generation at the root node of thebranch-and-bound tree provides a fractional upper bound solution and ouralgorithm finds an integral optimal solution after branching.

A branch-and-price approach with MILP formulation to modularity density maximization on graphs