An O(m) Algorithm for Cores Decomposition of Networks

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.

Cited by in corpus (84)

• Community detection in graphs
• DeepInf: Social Influence Prediction with Deep Learning
• Spreading dynamics in complex networks
• k-core decomposition: a tool for the visualization of large scale networks
• Identify influential spreaders in complex networks, the role of neighborhood
• Investigating Italian disinformation spreading on Twitter in the context of 2019 European elections
• K-Core based Temporal Graph Convolutional Network for Dynamic Graphs
• Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
• Keyword and Keyphrase Extraction Using Centrality Measures on Collocation Networks
• Solving large Maximum Clique problems on a quantum annealer
• Impact of network assortativity on epidemic and vaccination behaviour
• Enumerating Top-k Quasi-Cliques
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Multi-attributed Community Search in Road-social Networks
• Listing Maximal k-Plexes in Large Real-World Graphs
• Permutation Invariant Graph Generation via Score-Based Generative Modeling
• Fully Dynamic Algorithm for Top-$k$ Densest Subgraphs
• A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem
• Forecasting countries' gross domestic product from patent data
• Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks
• The AI Community Building the Future? A Quantitative Analysis of Development Activity on Hugging Face Hub
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• Geo-Social Group Queries with Minimum Acquaintance Constraint
• CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks
• Surname affinity in Santiago, Chile: A network-based approach that uncovers urban segregation
• Mathematical and Algorithmic Analysis of Network and Biological Data
• Truss Decomposition in Massive Networks
• A Survey of Community Search Over Big Graphs
• Efficient Core Maintenance in Large Dynamic Graphs
• Exploring Cohesive Subgraphs in Hypergraphs: The (k,g)-core Approach
• Heterogeneous Data Fusion Considering Spatial Correlations using Graph Convolutional Networks and its Application in Air Quality Prediction
• Combinatorial Optimization by Decomposition on Hybrid CPU--non-CPU Solver Architectures
• OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree
• Distributed k-Core Decomposition
• Mathematical Programming Formulations for the Collapsed k-Core Problem
• Non-backtracking Spectrum: Unitary Eigenvalues and Diagonalizability
• Computational Models for Commercial Advertisements in Social Networks
• Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
• Finding Maximum Cliques on the D-Wave Quantum Annealer
• Keywords lie far from the mean of all words in local vector space
• Mapping leadership and communities in EU-funded research through network analysis
• Enumerating k-Vertex Connected Components in Large Graphs
• Efficient Bitruss Decomposition for Large-scale Bipartite Graphs
• Understanding edge-connectivity in the Internet through core-decomposition
• Fast Hierarchy Construction for Dense Subgraphs
• COREATTACK: Breaking Up the Core Structure of Graphs
• External-Memory Network Analysis Algorithms for Naturally Sparse Graphs
• The Atlas for the Aspiring Network Scientist
• Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach
• Chargrid-OCR: End-to-end Trainable Optical Character Recognition for Printed Documents using Instance Segmentation
• Efficient Algorithms for Densest Subgraph Discovery
• Identifying Influential Nodes in Weighted Networks using k-shell based HookeRank Algorithm
• Motif statistics of artificially evolved and biological networks
• Butterfly-Core Community Search over Labeled Graphs
• Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition
• Attentive Geo-Social Group Recommendation
• Graph Decompositions Analysis and Comparison for Cohesive Subgraphs Detection
• I/O Efficient Core Graph Decomposition at Web Scale
• Evaluating the performance of geographical locations in scientific networks with an aggregation - randomization - re-sampling approach (ARR)
• Network structure and disease risk for an endemic infectious disease
• Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
• LUEM : Local User Engagement Maximization in Networks
• Towards User Engagement Dynamics in Social Networks
• Peeling Bipartite Networks for Dense Subgraph Discovery
• Keyword Aware Influential Community Search in Large Attributed Graphs
• Mapping the Timescale Organization of Neural Language Models
• The clique problem on inductive $k$-independent graphs
• Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs
• Improved Space efficient linear time algorithms for BFS, DFS and applications
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
• Parameter-free Structural Diversity Search
• Understanding Vulnerability of Communities in Complex Networks
• Parallel Algorithms for Densest Subgraph Discovery Using Shared Memory Model
• COREclust: a new package for a robust and scalable analysis of complex data
• Adversarial Stein Training for Graph Energy Models
• Identifying Ransomware Actors in the Bitcoin Network
• New algorithms for $k$-degenerate graphs
• Algorithm Engineering for Cut Problems
• Competitive Dynamics on Complex Networks
• The Bron-Kerbosch Algorithm with Vertex Ordering is Output-Sensitive
• Fast Algorithms for Intimate-Core Group Search in Weighted Graphs