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

We propose quasi-stable coloring, an approximate version of stable coloring.Stable coloring, also called color refinement, is a well-studied technique ingraph theory for classifying vertices, which can be used to build compact,lossless representations of graphs. However, its usefulness is limited due toits reliance on strict symmetries. Real data compresses very poorly using colorrefinement. We propose the first, to our knowledge, approximate colorrefinement scheme, which we call quasi-stable coloring. By using approximation,we alleviate the need for strict symmetry, and allow for a tradeoff between thedegree of compression and the accuracy of the representation. We study threeapplications: Linear Programming, Max-Flow, and Betweenness Centrality, andprovide theoretical evidence in each case that a quasi-stable coloring can leadto good approximations on the reduced graph. Next, we consider how to compute amaximal quasi-stable coloring: we prove that, in general, this problem isNP-hard, and propose a simple, yet effective algorithm based on heuristics.Finally, we evaluate experimentally the quasi-stable coloring technique onseveral real graphs and applications, comparing with prior approximationtechniques.  A reference implementation and the experiment code are available athttps://github.com/mkyl/QuasiStableColors.jl .

Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality