REVIEW 21 cited by
An O(m) Algorithm for Cores Decomposition of Networks
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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.
Forward citations
Cited by 21 Pith papers
-
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.
-
Hardness of Dynamic Core and Truss Decompositions
Dynamic k=3 core and truss decompositions are conditionally hard under OMv and SETH, while dynamic 2-core admits a polylog algorithm.
-
Parallel $k$-Core Decomposition: Theory and Practice
A parallel peeling framework with O(n+m) work, combined with sampling, vertical granularity control, and hierarchical buckets, beats three prior parallel k-core implementations on 23 of 25 graphs.
-
Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search
A lightweight GNN surrogate trained on seed-outcome pairs, combined with batched multi-swap simulated annealing, outperforms deeper learning-based influence maximization frameworks on tested benchmarks.
-
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.
-
Accelerating Historical K-Core Search in Temporal Graphs
A new edge-centric binary forest index answers temporal k-core component queries with far smaller index size and much faster construction than the existing EF-Index.
-
Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation
The paper presents OptiUCF, an optimized algorithm that constructs a correct UCF-Index for (k,eta)-core queries on uncertain graphs by replacing division-based updates with on-demand dynamic programming recomputation.
-
Bridging Visualization and Optimization: Multimodal Large Language Models on Graph-Structured Combinatorial Optimization
Feeding graph images to GPT-4o and refining its node choices with local search outperforms centrality and GNN baselines on influence maximization and network dismantling.
-
Fast Algorithms for Intimate-Core Group Search in Weighted Graphs
LEKS, a tree-based local expansion algorithm, finds smaller-weight intimate-core groups in weighted graphs faster than the existing ICG-M heuristic on three real networks.
-
Streaming and Batch Algorithms for Truss Decomposition
New incremental and batch algorithms for updating k-truss decompositions under edge insertions, with large speedups on sparse graphs.
-
CS-Agent: LLM-based Community Search via Dual-agent Collaboration
CS-Agent, a Solver-Validator two-agent dialogue with a Decider selector, improves LLM community search on synthetic graphs, and GraphCS is a new benchmark for measuring it.
-
Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs
The authors propose the (k,g)-core model and two algorithms, EPA and BCA, for finding and decomposing cohesive subhypergraphs based on pair co-occurrence.
-
Density-aware Walks for Coordinated Campaign Detection
Density-aware random-walk embeddings improve coordinated campaign detection accuracy on the LEN Twitter graph dataset.
-
Identifying Key Nodes for the Influence Spread using a Machine Learning Approach
A network science paper introduces Smart Bins, a clustering-based label generation method, and two new prediction targets (influence peak and peak time), reporting improved and more stable key node classification.
-
Parameter-free Structural Diversity Search
A new h-index based structural diversity score built from discriminative cores, with an efficient top-k search algorithm and experiments on four public social networks.
-
Experimental Analysis and Evaluation of Cohesive Subgraph Discovery
A systematic empirical comparison of 14 cohesive subgraph models shows truss-based and combined models find denser subgraphs, while core-based models return larger, more interpretable ones.
-
Monero Peer-to-peer Network Topology Analysis
Using k-core decomposition, the authors report that Monero's P2P network has a core-periphery structure dominated by 14 super-peers.
-
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). Continue with ORCID to comment.