Fast algorithms for determining (generalized) core groups in social networks. (English) Zbl 1284.05252

Summary: 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 \(\Delta\) is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.


05C82 Small world graphs, complex networks (graph-theoretic aspects)
05A18 Partitions of sets
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms
91D30 Social networks; opinion dynamics
Full Text: DOI


[1] Ahmed A, Batagelj V, Fu X, Hong S-H, Merrick D, Mrvar A (2007) Visualisation and analysis of the internet movie database. In: Proceedings of the Asia-Pacific symposium on visualisation (APVIS2007), Sydney, NSW, Australia, 5–7 February 2007. IEEE, New York, 17–24
[2] Alvarez-Hamelin JI, Dall’asta L, Barrat A, Vespignani A (2008) K-core decomposition of internet graphs: hierarchies, selfsimilarity and measurement biases. Netw Heterog Media 3(2): 371–393 · Zbl 1145.68470
[3] Batagelj V, Mrvar A (2003) Pajek–analysis and visualization of large networks. In: Jünger M, Mutzel P (eds) Graph drawing software. Springer, Berlin, pp 77–103. http://pajek.imfm.si · Zbl 1054.68564
[4] Batagelj V (2004) Pajek datasets: Geom. http://vlado.fmf.uni-lj.si/pub/networks/Data/Collab/Geom.htm
[5] Batagelj V, Mrvar A (2000) Some analyses of Erdos collaboration graph. Soc Netw 22: 173–186
[6] Batagelj V, Mrvar A, Zaveršnik M (1999) Partitioning approach to visualization of large graphs. In: KratochvÍl J (ed) Proceedings of 7th international symposium on graph drawing, 15–19 September 1999, Štiřín Castle, Czech Republic (Lecture notes in computer science, vol. 1731). Springer, Berlin, pp 90–97
[7] Batagelj V, Brandenburg FJ, Didimo W, Liotta G, Palladino P, Patrignani M (2010) Visual analysis of large graphs using (X;Y)-clustering and hybrid visualizations. In: IEEE Pacific visualization 2010 (PacVis ’10). IEEE, New YorK, pp 209–216
[8] Beebe NHF (2002) Nelson H. F. Beebe’s bibliographies page. http://www.math.utah.edu/\(\sim\)beebe/bibliographies.html
[9] Beiro MG, Alvarez-Hamelin JI, Busch JR (2008) A low complexity visualization tool that helps to perform complex systems analysis. New J Phys 10:125003, 1–18
[10] Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge
[11] Dorogovtsev SN, Goltsev AV, Mendes JFF (2006) k-Core architecture and k-core percolation on complex networks. Phys D Nonlinear Phenom 224(1–2): 7–19 · Zbl 1130.94024
[12] Eisterlehner F, Hotho A, Jäschke R (eds) (2009) Proceedings of ECML PKDD discovery challenge 2009 (DC09). http://www.kde.cs.uni-kassel.de/ws/dc09/papers/proceedings.pdf
[13] Garey MR, Johnson DS (1979) Computer and intractability. Freeman, San Francisco
[14] Janson S, Luczak MJ (2008) Asymptotic normality of the k-core in random graphs. Ann Appl Probab 18(3): 1085–1137 · Zbl 1157.05047
[15] Jäschke R, Marinho L, Hotho A, Schmidt-Thieme L, Stumme G (2007) Tag recommendations in folksonomies. Lecture notes in computer science, vol 4702. Springer, Berlin, pp 506–514
[16] Jones B (2002) Computational geometry database. http://compgeom.cs.uiuc.edu/\(\sim\)jeffe/compgeom/biblios.html , ftp://ftp.cs.usask.ca/pub/geometry/
[17] LaNet-vi (2009) Large network visualization tool. http://xavier.informatics.indiana.edu/lanet-vi/
[18] Seidman SB (1983) Network structure and minimum degree. Soc Netw 5: 269–287
[19] Schwartz J-M, Nacher JC (2009) Local and global modes of drug action in biochemical networks. BMC Chem Biol 9: 4–114
[20] Wang J-C, Chiu C-C (2008) Recommending trusted online auction sellers using social network analysis. Expert Syst Appl Int J Arch 34(3): 1666–1679
[21] Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge · Zbl 0926.91066
[22] Welsh DJA, Powell MB (1967) An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput J 10(1): 85–86 · Zbl 0147.15206
[23] Wuchty S, Almaas E (2005) Peeling the yeast protein network. Proteomics 5: 444–449
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.