An O(m) Algorithm for Cores Decomposition of Networks
arXiv (Cornell University)Published 25 October 2003Open access
Vladimir Batagelj, Matjaž Zaveršnik
Citations624
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for determining the cores decomposition of a given simple network, based on k{cores, proposed in 1983 by Seidman, and an application on the authors collaboration network in computational geometry is presented.
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.
Keywords
Computer ScienceEngineering
Social network analysis methods and applications
18,142 Citations2007Stanley Wasserman, Katherine Faust
Social NetworksNetwork structure and minimum degree
1,873 Citations1983Stephen B. Seidman
An approach to network cohesion is proposed that is based on minimum degree and which produces a sequence of subgraphs of gradually increasing cohesion that associates with any network measures of local density which promise to be useful both in characterizing network structures and in comparing networks.
Lecture notes in computer sciencePartitioning Approach to Visualization of Large Graphs
72 Citations1999Vladimir Batagelj, Andrej Mrvar +1 more
The use of core decomposition as an efficient approach for partitioning large graphs and on the selected subgraphs, clustering and blockmodeling can be used to analyze their internal structure.