pith. machine review for the scientific record. sign in

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

Recognition: unknown

An O(m) Algorithm for Cores Decomposition of Networks

V. Batagelj , M. Zaversnik
Authors on Pith no claims yet
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 2 Pith papers

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

  1. 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.

  2. 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.