The core decomposition of networks: theory, algorithms and applications
Open accessThe DOI matches its Crossref record; 132 of the 132 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476 · cited 1×
“In addition to the numerous ad-hoc solutions, several unified distributed platforms like MapReduce [37], Hadoop [149] and Spark [154] appeared and paved the way for nowadays cluster computing.”
BackgroundThe anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
Gephi: An Open Source Software for Exploring and Manipulating Networks
Bastian, M., Heymann, S., & Jacomy, M. (2009) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v3i1.13937 · Cited by 11,675
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326 · cited 1×
“[76], toward a scalable core-based influencemaximization algorithmwith theoretical guarantees.”
BackgroundEpidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,731
Mapping the structural core of human cerebral cortex
Hagmann, P., Cammoun, L., Gigandet, X., Meuli, R., Honey, C. J., Wedeen, V. J., & Sporns, O. (2008) · PLoS Biology · doi:10.1371/journal.pbio.0060159 · Cited by 4,173
TextRank: Bringing Order into Text
Mihalcea, R. F., & Tarau, P. (2004) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · Cited by 3,631
Pregel: a system for large-scale graph processing
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807184 · Cited by 3,515
Identification of influential spreaders in complex networks
Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010) · Nature Physics · doi:10.1038/nphys1746 · Cited by 3,212
White, T. (2009) · Cited by 2,800
Apache Spark: A unified engine for big data processing
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., et al. (2016) · Communications of the ACM · doi:10.1145/2934664 · Cited by 2,757
Börzsönyi, S., Kossmann, D., & Stocker, K. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2001.914855 · Cited by 2,463 · cited 1×
“The skyline concept was introduced in the data management community by [26].”
BackgroundRich-club organization of the human connectome
van den Heuvel, M. P., & Sporns, O. (2011) · The Journal of Neuroscience · doi:10.1523/jneurosci.3539-11.2011 · Cited by 2,354
Network structure and minimum degree
Seidman, S. B. (1983) · Social Networks · doi:10.1016/0378-8733(83)90028-x · Cited by 1,891
Bang-Jensen, J., & Gutin, G. (2002) · doi:10.1007/978-1-4471-3886-0 · Cited by 1,856
Keulen, D. S. (2014) · Cited by 1,677
Signed networks in social media
Leskovec, J., Huttenlocher, D., & Kleinberg, J. (2010) · Proceedings of the SIGCHI Conference on Human Factors in Computing Systems · doi:10.1145/1753326.1753532 · Cited by 1,306 · cited 1×
“Signed networks [81,82,88] are used to capture the notion of positive and negative interactions”
MethodHigher-order organization of complex networks
Benson, A. R., Gleich, D. F., & Leskovec, J. (2016) · Science · doi:10.1126/science.aad9029 · Cited by 1,270
The webgraph framework I: compression techniques
Boldi, P., & Vigna, S. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988752 · Cited by 1,201
Vital nodes identification in complex networks
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., & Zhou, T. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.007 · Cited by 1,183
Protein-protein interactions: methods for detection and analysis.
Phizicky, E. M., & Fields, S. (1995) · Microbiological reviews · doi:10.1128/mmbr.59.1.94-123.1995 · Cited by 966
GraphChi: Large-Scale Graph Computation on Just a PC
Kyrola, A., Blelloch, G. E., & Guestrin, C. (2018) · Figshare · doi:10.1184/r1/6605999 · Cited by 868
The Anatomy of the Facebook Social Graph
Ugander, J., Karrer, B., Backstrom, L., & Marlow, C. (2011) · arXiv · doi:10.48550/arxiv.1111.4503 · Cited by 819 · cited 2×
“Figure 6 depicts an example of the hierarchical structure of (3, 4)-nuclei decomposition in a snapshot of the Facebook graph composed by 88K nodes.”
Background(2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3 · Cited by 784 · cited 1×
“– In a social network [2], nodes may represent users and edgesmay provide information regarding friendship relationships.”
BackgroundA model of Internet topology using k-shell decomposition
Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y., & Shir, E. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0701175104 · Cited by 760
k-Core Organization of Complex Networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.040601 · Cited by 709
The H-index of a network node and its relation to degree and coreness
Lü, L., Zhou, T., Zhang, Q.-M., & Stanley, H. E. (2016) · Nature Communications · doi:10.1038/ncomms10168 · Cited by 690
Smallest-last ordering and clustering and graph coloring algorithms
Matula, D. W., & Beck, L. L. (1983) · Journal of the ACM · doi:10.1145/2402.322385 · Cited by 663
A Sufficient Condition for Backtrack-Free Search
Freuder, E. C. (1982) · Journal of the ACM · doi:10.1145/322290.322292 · Cited by 660
An O(m) Algorithm for Cores Decomposition of Networks
Batagelj, V., & Zaveršnik, M. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0310049 · Cited by 627 · cited 3×
“However, the problem can be solved in linear time, by using bin-sorting as it was demonstrated in [18] by Batagelj and Zaveršnik.”
MethodPlanetary-scale views on a large instant-messaging network
Leskovec, J., & Horvitz, E. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367620 · Cited by 616 · cited 2×
“Truss decomposition [34] 2008 Internet evolution [165], network analysis [9,69,87], neuroscience [67]”
BackgroundMethodManaging and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Recommendations in location-based social networks: a survey
Bao, J., Zheng, Y., Wilkie, D., & Mokbel, M. (2015) · GeoInformatica · doi:10.1007/s10707-014-0220-8 · Cited by 570
The community-search problem and how to plan a successful cocktail party
Sozio, M., & Gionis, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835923 · Cited by 490 · cited 1×
“This problem was introduced in [138], and it attracted significant interest.”
BackgroundLarge scale networks fingerprinting and visualization using the k-core decomposition
Alvarez-Hamelin, J. I., Dall’Asta, L., Barrat, A., & Vespignani, A. (2005) · neural information processing systems · Cited by 440
Truss decomposition in massive networks
Wang, J., & Cheng, J. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2311906.2311909 · Cited by 423
Cook, D. J., & Holder, L. B. (2006) · Wiley-Interscience eBooks · Cited by 396
The Slashdot Zoo: Mining a Social Network with Negative Edges
Kunegis, J., Lommatzsch, A., & Bauckhage, C. (2017) · arXiv (Cornell University) · doi:10.24406/publica-r-363202 · Cited by 384
Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization
Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., De Luca, E. W., & Albayrak, S. (2010) · Proceedings of the 2010 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972801.49 · Cited by 369 · cited 1×
“Signed networks [81,82,88] are used to capture the notion of positive and negative interactions”
MethodSearching for superspreaders of information in real-world social media
Pei, S., Muchnik, L., Andrade, Zheng, Z., & Makse, H. A. (2014) · Scientific Reports · doi:10.1038/srep05547 · Cited by 362
The slashdot zoo: mining a social network with negative edges
Kunegis, J., Lommatzsch, A., & Bauckhage, C. (2009) · Proceedings of the 18th international conference on World wide web · doi:10.1145/1526709.1526809 · Cited by 342
DOULION: counting triangles in massive graphs with a coin
Tsourakakis, C. E., Kang, U., Miller, G. L., & Faloutsos, C. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557111 · Cited by 328
Effective community search for large attributed graphs
Fang, Y., Cheng, R., Luo, S., & Hu, J. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/2994509.2994538 · Cited by 317
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299 · cited 1×
“detection problem has been addressed utilizing the properties of k-core decomposition, including local community detection techniques [37] and the influential community search”
MethodKumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tompkins, A., & Upfal, E. (2000) · Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems - PODS '00 · doi:10.1145/335168.335170 · Cited by 288 · cited 4×
“The Web [80] can be modeled as a graph, where nodes represent web pages and edges represent hyperlinks among them.”
BackgroundInfluentialA k-shell decomposition method for weighted networks
Garas, A., Schweitzer, F., & Havlin, S. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/8/083030 · Cited by 280
Graph-based keyword extraction for single-document summarization
Litvak, M., & Last, M. (2008) · Proceedings of the Workshop on Multi-source Multilingual Information Extraction and Summarization - MMIES '08 · doi:10.3115/1613172.1613178 · Cited by 272 · cited 1×
“For example, [108] utilizes PageRank and [96] uses HITS for ranking words in text based on their ranking in the corresponding graph.”
MethodEfficient core decomposition in massive networks
Cheng, J., Ke, Y., Chu, S., & Ozsu, M. T. (2011) · 2011 IEEE 27th International Conference on Data Engineering · doi:10.1109/icde.2011.5767911 · Cited by 266 · cited 2×
“…[64, 82, 9] • 2009 • cell biology [92] • 2010 • influential spreaders [74], mobile social networks [85] D-cores [57], disk-based computation [30], distributed computation [105], anchored k -core [19] • 2011 • communities [58], influence [26], neuroscience [143] triangle cores (truss) [146,…”
BackgroundMethodSearching for superspreaders of information in real-world social media
Pei, S., Muchnik, L., Andrade, Jr., Zheng, Z. M., & Makse, H. A. (2014) · CUNY Academic Works (City University of New York) · Cited by 265
Spreading dynamics in complex networks
Pei, S., & Makse, H. A. (2013) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2013/12/p12002 · Cited by 252
Influential community search in large networks
Li, R.-H., Qin, L., Yu, J. X., & Mao, R. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2735479.2735484 · Cited by 243
Shanahan, M., Bingman, V. P., Shimizu, T., Wild, M., & Güntürkün, O. (2013) · Frontiers in Computational Neuroscience · doi:10.3389/fncom.2013.00089 · Cited by 235
k-nearest neighbors in uncertain graphs
Potamias, M., Bonchi, F., Gionis, A., & Kollios, G. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920967 · Cited by 235
(2006) · Wiley eBooks · doi:10.1002/0470073047 · Cited by 228
K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
Ignacio Alvarez-Hamelin, J., C. A. F. D. I., Dall'Asta, L., Barrat, A., Vespignani, A., A. S. I. C. F. T. P., L. (. D. C. 8., & S. O. I. (2008) · Networks & Heterogeneous Media · doi:10.3934/nhm.2008.3.371 · Cited by 224 · cited 3×
“In a similar way, the decomposition has been applied to study [8, 9] and model [29] the Internet graph.”
BackgroundMethodEffective community search over large spatial graphs
Fang, Y., Cheng, R., Li, X., Luo, S., & Hu, J. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3055330.3055337 · Cited by 214
K-core decomposition of large networks on a single PC
Khaouid, W., Barsky, M., Srinivasan, V., & Thomo, A. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2850469.2850471 · Cited by 210 · cited 2×
“Another implementation of EMCore has been reported in [77],which is based onGraphChi [84].”
BackgroundMethodGeneralized CoresPreprint
Batagelj, V., & Zaveršnik, M. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0202039 · Cited by 199
Efficient Core Maintenance in Large Dynamic Graphs
Li, R.-H., Yu, J. X., & Mao, R. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.158 · Cited by 187
Streaming algorithms for k-core decomposition
Sarıyüce, A. E., Gedik, B., Jacques-Silva, G., Wu, K., & Çatalyürek, Ü. V. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2536336.2536344 · Cited by 187 · cited 7×
“The later work in [157] addresses [127] and [93] as being impractical for large graphs (in the aspect of the number of nodes).”
BackgroundMethodInfluentialk-core decomposition: a tool for the visualization of large scale networks
Alvarez-Hamelin, J. I., Dall’Asta, L., Barrat, A., & Vespignani, A. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0504107 · Cited by 183 · cited 6×
“Figure 14: Example of the model for graph visualization with k-cores of [6, 7].”
BackgroundMethodInfluentialDistributed k-Core Decomposition
Montresor, A., De Pellegrini, F., & Miorandi, D. (2013) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.124 · Cited by 181
The k-core as a predictor of structural collapse in mutualistic ecosystems
Morone, F., Ferraro, G. D., & Makse, H. A. (2018) · Nature Physics · doi:10.1038/s41567-018-0304-8 · Cited by 171 · cited 2×
“Distributed computation [71], probabilistic cores [121], radiusbounded cores [151], bipartite peeling [128], Temporal graphs [52], local truss and nucleus [129] 2018 Community search [90,91], biology [56], ecology [112], core resilience [86], metabolic networks [49], patterns and anomaly detection [137], graph similar…”
BackgroundA k-shell decomposition method for weighted networks
Garas, A., Schweitzer, F., & Havlin, S. (2012) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000055291 · Cited by 171
Social resilience in online communities: the autopsy of friendster
García, D., Mavrodiev, P., & Schweitzer, F. (2013) · Conference on Online Social Networks · doi:10.1145/2512938.2512946 · Cited by 170
Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
Zhang, Y., & Parthasarathy, S. (2012) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2012.35 · Cited by 168 · cited 3×
“, cycle subgraphs of length three [34,150, 166].”
BackgroundMethodEvolution of the Internet and its cores
Zhang, G., Zhang, G., Yang, Q., Cheng, S., & Zhou, T. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/12/123027 · Cited by 162
Dynamic reorganization of brain functional networks during cognition
Bola, M., & Sabel, B. A. (2015) · NeuroImage · doi:10.1016/j.neuroimage.2015.03.057 · Cited by 160
Fast and simple decycling and dismantling of networks
Zdeborová, L., Zhang, P., & Zhou, H.-J. (2016) · Scientific Reports · doi:10.1038/srep37954 · Cited by 158
Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions
Sarıyüce, A. E., Seshadhri, C., Pinar, A., & Çatalyürek, Ü. V. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741640 · Cited by 158 · cited 4×
“the authors of [130] have observed that the (3, 4)-nuclei provide themost interestingdecompositionof real-world graphs.”
BackgroundInfluentialLocating influential nodes in complex networks
Malliaros, F. D., Rossi, M.-E. G., & Vazirgiannis, M. (2016) · Scientific Reports · doi:10.1038/srep19307 · Cited by 153
Self-citationCoreScope: Graph Mining Using k-Core Analysis — Patterns, Anomalies and Algorithms
Shin, K., Eliassi‐Rad, T., & Faloutsos, C. (2016) · Proceedings · doi:10.1109/icdm.2016.0058 · Cited by 148 · cited 2×
“Incremental computation [126], disk-based computation [65,153], distributed computation [12], uncertain truss [72] 2016 Cell biology [42,120], graph mining [136], network analysis [148], neuroscience [85] , network decycling and dismantling [161], influential spreaders [102], keyword extraction [143], summarization [1…”
BackgroundMethodWhen engagement meets similarity: efficient (k,r)-core computation on social networks
Zhang, F., Zhang, Y., Qin, L., Zhang, W., & Lin, X. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3115404.3115406 · Cited by 140
D-cores: measuring collaboration of directed graphs based on degeneracy
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2012) · Knowledge and Information Systems · doi:10.1007/s10115-012-0539-0 · Cited by 131
Self-citationPeeling Bipartite Networks for Dense Subgraph Discovery
Sarıyüce, A. E., & Pinar, A. (2018) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3159652.3159678 · Cited by 130
I/O efficient Core Graph Decomposition at web scale
Wen, D., Qin, L., Zhang, Y., Lin, X., & Yu, J. X. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498235 · Cited by 128 · cited 6×
“The limitations of EMCore are highlighted in [153] especially concerning the amount of main memory it might need.”
BackgroundMethodInfluentialPersistent Community Search in Temporal Networks
Li, R.-H., Su, J. R., Qin, L., Yu, J. X., & Dai, Q. (2018) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00077 · Cited by 126 · cited 3×
“An interesting application of the k-core concept is the detection of persistent communities in networks that change over time, reported in [90].”
BackgroundAl-Garadi, M. A., Varathan, K. D., & Ravana, S. D. (2016) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2016.11.002 · Cited by 121
s -core network decomposition: A generalization of k -core analysis to weighted networks
Eidsaa, M., & Almaas, E. (2013) · Physical Review E · doi:10.1103/physreve.88.062819 · Cited by 121
Evaluating Cooperation in Communities with the k-Core Structure
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2011) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2011.65 · Cited by 119 · cited 4×
“Later, other studies in large-scale real networks followed [63,69], including the analysis of Microsoft Instant Messenger (MSN) [87] and Facebook [146] social graphs.”
BackgroundMethodInfluentialSelf-citationEmergence of core–peripheries in networks
Verma, T., Russmann, F., Araújo, N. A. M., Nagler, J., & Herrmann, H. J. (2016) · Nature Communications · doi:10.1038/ncomms10441 · Cited by 114
Efficient Fault-Tolerant Group Recommendation Using alpha-beta-core
Ding, D., Li, H., Huang, Z., & Mamoulis, N. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3133130 · Cited by 112 · cited 2×
“Hidden cores [139], multilayer graphs [53], parallel computation [74,152], density-friendly decomposition [38], k-peak decomposition [66], (k, r)-core [164], core unraveling [162], Truss in uncertain graphs [170], Dynamic graphs [167], α−β-core [40] 2017 Distributed clustering [33], community search [4,46], engagement…”
BackgroundIncremental k-core decomposition: algorithms and evaluation
Sarıyüce, A. E., Gedik, B., Jacques-Silva, G., Wu, K., & Çatalyürek, Ü. V. (2016) · The VLDB Journal · doi:10.1007/s00778-016-0423-8 · Cited by 109 · cited 2×
“temporal graphs [151], disk-based and in-memory [72], parallel computation [129], density-friendly decomposition [136] • 2015 • keyword extraction [121], community search [86], earthquake networks [63], software engineering [103], cell biology [68, 41], neuroscience [150, 20] incremental computation [123], disk-based…”
BackgroundMethodFinding Critical Users for Social Network Engagement: The Collapsed k-Core Problem
Zhang, F., Zhang, Y., Qin, L., Zhang, W., & Lin, X. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10482 · Cited by 109 · cited 2×
“Hidden cores [139], multilayer graphs [53], parallel computation [74,152], density-friendly decomposition [38], k-peak decomposition [66], (k, r)-core [164], core unraveling [162], Truss in uncertain graphs [170], Dynamic graphs [167], α−β-core [40] 2017 Distributed clustering [33], community search [4,46], engagement…”
BackgroundTruss Decomposition of Probabilistic Graphs
Huang, X. S., Lu, W., & Lakshmanan, L. V. S. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2882913 · Cited by 106
Core decomposition in large temporal graphs
Wu, H., Cheng, J. S.-C., Lu, Y., Ke, Y., Huang, Y., Yan, D., & Wu, H. (2015) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2015.7363809 · Cited by 103
Main Core Retention on Graph-of-Words for Single-Document Keyword Extraction
Rousseau, F., & Vazirgiannis, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-16354-3_42 · Cited by 98 · cited 2×
“Naturally, the ranking provided from degeneracy has been utilized as well for keyword extraction [124].”
BackgroundSelf-citationPartitioning Approach to Visualization of Large Graphs
Batagelj, V., Mrvar, A., & Zaveršnik, M. (1999) · Lecture notes in computer science · doi:10.1007/3-540-46648-7_9 · Cited by 95 · cited 2×
“One of the earliest pieces of work for k-core-based graph visualization focused on the presentation of the graph’s adjacency matrix [16].”
BackgroundInfluence of Wiring Cost on the Large-Scale Architecture of Human Cortical Connectivity
Samu, D., Seth, A. K., & Nowotny, T. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003557 · Cited by 92
Density-friendly Graph Decomposition
Tatti, N., & Gionis, A. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741119 · Cited by 88 · cited 4×
“Temporal graphs [157], disk-based and in-memory [77], parallel computation [134], density-friendly decomposition [141] 2015 Keyword extraction [124], influential communities [92], earthquake networks [68], cell biology [44,73], neuroscience [21, 156], textual event detection [106], engagement [104]”
BackgroundInfluentialPatterns and anomalies in k-cores of real-world graphs with applications
Shin, K., Eliassi‐Rad, T., & Faloutsos, C. (2017) · Knowledge and Information Systems · doi:10.1007/s10115-017-1077-6 · Cited by 87
Degeneracy-Based Real-Time Sub-Event Detection in Twitter Stream
Meladianos, P., Nikolentzos, G., Rousseau, F., Stavrakas, Y., & Vazirgiannis, M. (2021) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v9i1.14597 · Cited by 86 · cited 2×
“Temporal graphs [157], disk-based and in-memory [77], parallel computation [134], density-friendly decomposition [141] 2015 Keyword extraction [124], influential communities [92], earthquake networks [68], cell biology [44,73], neuroscience [21, 156], textual event detection [106], engagement [104]”
BackgroundSelf-citationLocal algorithms for hierarchical dense subgraph discovery
Sariyüce, A. E., Seshadhri, C., & Pinar, A. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3275536.3275540 · Cited by 85
A Graph Degeneracy-based Approach to Keyword Extraction
Tixier, A. J. ‐., Malliaros, F. D., & Vazirgiannis, M. (2016) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d16-1191 · Cited by 83 · cited 2×
“[143] further refined the concept of core (and truss) decomposition for the task of keyword extraction.”
BackgroundMethodSelf-citationTo stay or not to stay: modeling engagement dynamics in social graphs
Malliaros, F. D., & Vazirgiannis, M. (2013) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2505515.2505561 · Cited by 81
Self-citationDeciphering the global organization of clustering in real complex networks
Colomer-de-Simón, P., Serrano, M. Á., Beiró, M. G., Alvarez-Hamelin, J. I., & Boguñá, M. (2013) · Scientific Reports · doi:10.1038/srep02517 · Cited by 80 · cited 1×
“The m-core is utilized in [35] on an internet graph as well as on the E.”
MethodLarge Scale Density-friendly Graph Decomposition via Convex Programming
Danisch, M., Chan, T.-H. H., & Sozio, M. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3038912.3052619 · Cited by 79 · cited 2×
“Hidden cores [139], multilayer graphs [53], parallel computation [74,152], density-friendly decomposition [38], k-peak decomposition [66], (k, r)-core [164], core unraveling [162], Truss in uncertain graphs [170], Dynamic graphs [167], α−β-core [40] 2017 Distributed clustering [33], community search [4,46], engagement…”
BackgroundCore Decomposition and Densest Subgraph in Multilayer Networks
Galimberti, E., Bonchi, F., & Gullo, F. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3132993 · Cited by 79 · cited 3×
“Hidden cores [139], multilayer graphs [53], parallel computation [74,152], density-friendly decomposition [38], k-peak decomposition [66], (k, r)-core [164], core unraveling [162], Truss in uncertain graphs [170], Dynamic graphs [167], α−β-core [40] 2017 Distributed clustering [33], community search [4,46], engagement…”
BackgroundMethodD-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2011) · Proceedings · doi:10.1109/icdm.2011.46 · Cited by 78
Self-citationIdentifying the node spreading influence with largest k -core values
Lin, J., Guo, Q., Dong, W.-Z., Tang, L., & Liu, J.-G. (2014) · Physics Letters A · doi:10.1016/j.physleta.2014.09.054 · Cited by 73
CoreCluster: A Degeneracy Based Graph Clustering Framework
Giatsidis, C., Malliaros, F. D., Thilikos, D. M., & Vazirgiannis, M. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8731 · Cited by 67 · cited 2×
“In a recent work on community detection [61], the authors built upon the properties of the decomposition to speed up the execution time of computationally intensive graph clustering algorithms, such as spectral clustering.”
BackgroundSelf-citationCalders, T., Esposito, F., Hüllermeier, E., & Meo, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44845-8 · Cited by 65
Core and periphery structures in protein interaction networks
Luo, F., Li, B., Wan, X., & Scheuermann, R. H. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-s4-s8 · Cited by 64
Protein complex prediction for large protein protein interaction networks with the Core&Peel method
Pellegrini, M., Baglioni, M., & Geraci, F. (2016) · BMC Bioinformatics · doi:10.1186/s12859-016-1191-6 · Cited by 63
IDENTIFYING IMPORTANT CLASSES OF LARGE SOFTWARE SYSTEMS THROUGH K-CORE DECOMPOSITION
MEYER, P., Siy, H. P., & Bhowmick, S. (2014) · Advances in Complex Systems · doi:10.1142/s0219525915500046 · Cited by 51 · cited 1×
“temporal graphs [151], disk-based and in-memory [72], parallel computation [129], density-friendly decomposition [136] • 2015 • keyword extraction [121], community search [86], earthquake networks [63], software engineering [103], cell biology [68, 41], neuroscience [150, 20] incremental computation [123], disk-based…”
BackgroundK -shell decomposition reveals hierarchical cortical organization of the human brain
Lahav, N., Ksherim, B., Simon, E. B., Maron‐Katz, A., Cohen, R., & Havlin, S. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/8/083013 · Cited by 42
I/O Efficient Core Graph Decomposition: Application to Degeneracy Ordering
Wen, D., Qin, L., Zhang, Y., Lin, X., & Yu, J. X. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2833070 · Cited by 41
García-Algarra, J., Pastor, J. M., Iriondo, J. M., & Galeano, J. (2017) · PeerJ · doi:10.7717/peerj.3321 · Cited by 37 · cited 2×
“dynamic cores [127], distributed computation [110] , weighted networks [43] • 2013 • influential spreaders [168], engagement [103, 55], network analysis [1], neuroscience [135] local estimation [114], uncertain graphs [24], S-cores [60] • 2014 • clustering [61], neuroscience [125], influential spreaders [119, 95] temp…”
BackgroundLocally Estimating Core Numbers
O’Brien, M. P., & Sullivan, B. D. (2014) · Proceedings · doi:10.1109/icdm.2014.136 · Cited by 36
Percolation on random networks with arbitrary k -core structure
Hébert‐Dufresne, L., Allard, A., Young, J.-G., & Dubé, L. J. (2013) · Physical Review E · doi:10.1103/physreve.88.062820 · Cited by 34
How Robust Is the Core of a Network?
Adiga, A., & Vullikanti, A. K. S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40988-2_35 · Cited by 34 · cited 4×
“The most closely related works can be found in [1, 2, 3]”
BackgroundInfluentialk-core decomposition: a tool for the analysis of large scale Internet graphsPreprint
Alvarez-Hamelin, J. I., Dall’Asta, L., Barrat, A., & Vespignani, A. (2005) · arXiv (Cornell University) · Cited by 32
Networks with arbitrary edge multiplicities
Zlatić, V., Garlaschelli, D., & Caldarelli, G. (2012) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/97/28005 · Cited by 29 · cited 1×
“A similar concept to the triangle cores, them-core is defined based on the number of triangles an edge (instead of a vertex) belongs to [169].”
BackgroundMining Uncertain Graphs: An Overview
Kassiano, V., Gounaris, A., Papadopoulos, A. N., & Tsichlas, K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-57045-7_6 · Cited by 28
Self-citationGovindan, P., Wang, C., Xu, C., Duan, H., & Soundarajan, S. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3038912.3052635 · Cited by 25
Analyzing the structure of earthquake network by k -core decomposition
He, X., Hai, Z., Cai, W., Li, G.-G., & Pei, F.-D. (2014) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2014.11.022 · Cited by 20
Filho, H. A. D. A., Machicao, J., & Bruno, O. M. (2018) · PLoS ONE · doi:10.1371/journal.pone.0195843 · Cited by 18
Identifying the Most Connected Vertices in Hidden Bipartite Graphs Using Group Testing
Wang, J., Lo, E., & Yiu, M. L. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.178 · Cited by 17 · cited 1×
“Motivated by recent developments in the area [140, 159] for detecting the top-k nodes with the highest degrees in bipartite graphs, in [139], an algorithm is proposed to discover if a hidden graph contains a k-core subgraph or not, by applying as few edge probing queries as possible.”
BackgroundEmerson, A. I., Andrews, S., Ahmed, I., Karedath, T., & Malek, J. A. (2015) · Journal of Clinical Bioinformatics · doi:10.1186/s13336-015-0016-6 · Cited by 16
Emerson, I. A., & Sinha, S. (2015) · Journal of Biosciences · doi:10.1007/s12038-015-9554-0 · Cited by 13
Minimal sets to destroy the k -core in random networks
Schmidt, C., Pfister, H. D., & Zdeborová, L. (2019) · Physical review. E · doi:10.1103/physreve.99.022310 · Cited by 13 · cited 2×
“distributed computation [71], probabilistic cores [121], radius-bounded cores [151], bipartite peeling [128], temporal graphs [52], local truss and nucleus [129] • 2018 • community search [90, 91], biology [56], ecology [112], core resilience [86], metabolic networks [49], patterns and anomaly detection [137], graph s…”
BackgroundCore2Vec: A Core-Preserving Feature Learning Framework for Networks
Sarkar, S., Bhagwat, A., & Mukherjee, A. (2018) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2018.8508693 · Cited by 8
A Structural Approach to Disentangle the Visualization of Bipartite Biological Networks
García-Algarra, J., Pastor, J. M., Mouronte-López, M. L., & Galeano, J. (2018) · Complexity · doi:10.1155/2018/6204947 · Cited by 6
Applications of Network Science to Criminal Networks, University Education, and Ecology
Marshak, C. Z. (2017) · eScholarship (California Digital Library) · Cited by 5
Core Decomposition of Massive, Information-Rich Graphs
Bonchi, F., Gullo, F., & Kaltenbrunner, A. (2017) · Springer eBooks · doi:10.1007/978-1-4614-7163-9_110176-1 · Cited by 5
Core Decomposition of Massive, Information-Rich Graphs
Bonchi, F., Gullo, F., & Kaltenbrunner, A. (2018) · Springer eBooks · doi:10.1007/978-1-4939-7131-2_110176 · Cited by 5 · cited 3×
“Two notable attempts in similar reviews exist in the general literature as book chapters found in “Encyclopedia of Social Network Analysis and Mining” [23] and in “Cohesive Subgraph Computation over Large Sparse Graphs” [31] both covering to a lesser extend a subset of the main topics presented in this manuscript.”
BackgroundInfluentialNimbleCore: A space-efficient external memory algorithm for estimating core numbers
Govindan, P., Soundarajan, S., Eliassi‐Rad, T., & Faloutsos, C. (2016) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2016.7752237 · Cited by 4 · cited 2×
“In [60] a space-efficient algorithm is proposed ( NimbleCore ), that provides accurate estimates of the core numbers by using O ( n ) space for graphs with power-law degree distribution and O ( n log d max ) space for arbitrary graphs, where d max is the maximum node degree.”
BackgroundMethod
Metadata
- Authors
- Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., & Vazirgiannis, M.
- Venue
- The VLDB Journal
- Published
- 2019-11-04
- Volume
- 29
- Issue
- 1
- Pages
- 61-92
- ISSN
- 0949-877X (ISSN-L)
- 1066-8888
- OpenAlex
- W2912708407
- Cited by
- 161
- References
- 132
- FWCI
- 8.04
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.