The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “ k -cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity $$O(m)$$, where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k -core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in $$O(m\cdot\max(\Delta,n))$$ time, where n is the number of vertices and Δ is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.
Description
Advances in Data Analysis and Classification, Volume 5, Number 2 - SpringerLink
%0 Journal Article
%1 batagelj2011algorithms
%A Batagelj, Vladimir
%A Zaveršnik, Matjaž
%C Berlin / Heidelberg
%D 2011
%I Springer
%J Advances in Data Analysis and Classification
%K core graph
%N 2
%P 129-145
%R 10.1007/s11634-010-0079-y
%T Fast algorithms for determining (generalized) core groups in social networks
%U http://dx.doi.org/10.1007/s11634-010-0079-y
%V 5
%X The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “ k -cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity $$O(m)$$, where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k -core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in $$O(m\cdot\max(\Delta,n))$$ time, where n is the number of vertices and Δ is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.
@article{batagelj2011algorithms,
abstract = {The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on “ k -cores”, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity $${\mathcal{O}(m)}$$, where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k -core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in $${\mathcal{O}(m\cdot\max(\Delta,\log{n}))}$$ time, where n is the number of vertices and Δ is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.},
added-at = {2012-10-04T16:29:29.000+0200},
address = {Berlin / Heidelberg},
affiliation = {Department of Mathematics, FMF, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia},
author = {Batagelj, Vladimir and Zaveršnik, Matjaž},
biburl = {https://www.bibsonomy.org/bibtex/2cd0d5266688af6bb98bde7f99e3a54c1/sdo},
description = {Advances in Data Analysis and Classification, Volume 5, Number 2 - SpringerLink},
doi = {10.1007/s11634-010-0079-y},
interhash = {a0bd7331f81bb4da72ce115d5943d6e4},
intrahash = {cd0d5266688af6bb98bde7f99e3a54c1},
issn = {1862-5347},
journal = {Advances in Data Analysis and Classification},
keyword = {Mathematics and Statistics},
keywords = {core graph},
number = 2,
pages = {129-145},
publisher = {Springer},
timestamp = {2012-10-04T16:29:29.000+0200},
title = {Fast algorithms for determining (generalized) core groups in social networks},
url = {http://dx.doi.org/10.1007/s11634-010-0079-y},
volume = 5,
year = 2011
}