An O(m) Algorithm for Cores Decomposition of Networks

By V. Batagelj, Matjaz Zaversnik. 2003

986 citations recorded by the source corpus.

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 ecien t, O(m), m is the number of lines, algorithm for determining the cores decomposition of a given simple network is presented. An application on the authors collaboration network in computational geometry is presented.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Community detection in graphs (2009, background): “…is not expected to have a cluster structure, so the possible existence of clusters is revealed by the comparison between the actual density of edges in a subgraph and the density one would expect to have in the subgraph if the vertices of the graph were attached regardless of community structure.”
Not All Qubits Are Created Equal: A Case for Variability-Aware Policies for NISQ-Era Quantum Computers (2018, methodology): “VQA computes the strongest set of sub-graphs by using K-core algorithm that that recursively prunes nodes with degrees less than k [2].”
DeepInf: Social Influence Prediction with Deep Learning (2018, neutral): “Coreness [4].”
Pajek - Analysis and Visualization of Large Networks (2004, neutral): “For details see [18].”
Efficient Graph Generation with Graph Recurrent Attention Networks (2019, background): “Most importantly, the core decomposition, i.e ., all cores ranked based on their orders, can be found in linear time (w.r.t. | E | ) [3].”
Effective Community Search for Large Attributed Graphs (2016, methodology): “A common notion of structure cohesiveness is that the minimum degree of all the vertices that appear in the community has to be k or more [26, 25, 2, 7, 5, 18].”
Querying k-truss community in large and dynamic graphs (2014, methodology): “There are different definitions of dense subgraph patterns, including clique [3, 5, 22, 24], quasi-clique [19], k-core [2, 4], k-truss [7, 21, 26], dense neighborhood graph [23], dense bipartite subgraph [12], etc.”
Computational approaches for detecting protein complexes from protein interaction networks: a survey (2010, background): “For example, the node set {4, 5, 6, 7} is the highest k-core in node 5's neighborhood graph with k=2 [28,29] and density d = 5/ 6 (5 interactions out of a total possible 6 interactions between the nodes).”
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time (2010, methodology): “We can implement this algorithm in O(n+m) time by maintaining an array D, where D[i] stores a list of vertices of degree i in the graph [5].”