DMI is a novel MinHash-based dynamic framework using l-buffered k-MinHash, Bottom-k MinHash, and batch reconstruction for fast approximate maintenance of maximum quasi-cliques in streaming graphs.
An O(m) Algorithm for Cores Decomposition of Networks
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
abstract
The structure of large networks can be revealed by partitioning them to smaller parts, which are easier to handle. One of such decompositions is based on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$, $m$ is the number of lines, algorithm for determining the cores decomposition of a given network is presented.
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
A deletion-based exact algorithm for maximum k-biplex search achieves worst-case time O*(γ_k^n) with γ_k < 2 and up to four orders of magnitude practical speedup over prior state-of-the-art.
Syndesmoscope combines traditional node-link views with invariant geometric plots and introduces kSnakes, supporting leapfrogging and hopscotching interactions demonstrated on 72 networks.
Introduces (k,δ)-truss for temporal graphs and compressed indexes enabling optimal-time queries with dynamic maintenance.
A pretrained graph model using feature-agnostic structural prompts matches or exceeds supervised baselines and shows strong zero-shot and few-shot transfer on held-out biomedical graphs, with a 21.8% ROC-AUC gain on SagePPI.
A survey that classifies existing densest subgraph discovery solutions into groups, reviews around 50 papers, compares models, and identifies future research directions.
citing papers explorer
-
Scalable Algorithm for Dynamic Quasi-clique Detection
DMI is a novel MinHash-based dynamic framework using l-buffered k-MinHash, Bottom-k MinHash, and batch reconstruction for fast approximate maintenance of maximum quasi-cliques in streaming graphs.
-
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
-
Revisiting Maximum $k$-Biplex Search Through $k$-Bounded-Degree Deletion
A deletion-based exact algorithm for maximum k-biplex search achieves worst-case time O*(γ_k^n) with γ_k < 2 and up to four orders of magnitude practical speedup over prior state-of-the-art.
-
Syndesmoscope: The Power of Invariant Plots Linked to Traditional Network Views
Syndesmoscope combines traditional node-link views with invariant geometric plots and introduces kSnakes, supporting leapfrogging and hopscotching interactions demonstrated on 72 networks.
-
Querying Cohesive Subgraph regarding Span-Constrained Triangles on Temporal Graphs with Dynamic Index Maintenance
Introduces (k,δ)-truss for temporal graphs and compressed indexes enabling optimal-time queries with dynamic maintenance.
-
Toward a universal foundation model for graph-structured data
A pretrained graph model using feature-agnostic structural prompts matches or exceeds supervised baselines and shows strong zero-shot and few-shot transfer on held-out biomedical graphs, with a 21.8% ROC-AUC gain on SagePPI.
-
A Survey of Densest Subgraph Discovery on Large Graphs
A survey that classifies existing densest subgraph discovery solutions into groups, reviews around 50 papers, compares models, and identifies future research directions.