pith. sign in

arxiv: cs/0310049 · v1 · pith:VKJVPMROnew · submitted 2003-10-25 · 💻 cs.DS · cs.DM

An O(m) Algorithm for Cores Decomposition of Networks

V. Batagelj , M. Zaversnik This is my paper
classification 💻 cs.DS cs.DM
keywords coresalgorithmdecompositionnetworksdecompositionsdeterminingeasierefficient
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Scalable Algorithm for Dynamic Quasi-clique Detection

    cs.SI 2026-05 unverdicted novelty 7.0

    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.

  2. Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs

    cs.DS 2026-05 unverdicted novelty 7.0

    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.

  3. Syndesmoscope: The Power of Invariant Plots Linked to Traditional Network Views

    cs.HC 2026-06 unverdicted novelty 6.0

    Syndesmoscope combines traditional node-link views with invariant geometric plots and introduces kSnakes, supporting leapfrogging and hopscotching interactions demonstrated on 72 networks.

  4. Querying Cohesive Subgraph regarding Span-Constrained Triangles on Temporal Graphs with Dynamic Index Maintenance

    cs.DB 2026-06 unverdicted novelty 6.0

    Introduces (k,δ)-truss for temporal graphs and compressed indexes enabling optimal-time queries with dynamic maintenance.

  5. Toward a universal foundation model for graph-structured data

    cs.LG 2026-04 unverdicted novelty 6.0

    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.

  6. A Survey of Densest Subgraph Discovery on Large Graphs

    cs.SI 2023-06 unverdicted novelty 4.0

    A survey that classifies existing densest subgraph discovery solutions into groups, reviews around 50 papers, compares models, and identifies future research directions.