An O(m) Algorithm for Cores Decomposition of Networks
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.
Forward citations
Cited by 3 Pith papers
-
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.
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.