Proceedings of the VLDB Endowment · 2021 · 54 citations · 62 references
ComputingBiologyComputer ScienceComputational BiologyData StructuresNetwork BiologyGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryDynamic Graph AlgorithmsDynamic Graph AnalysisK-core DecompositionScalable Graph AlgorithmsSubgraph Extraction
The model of k -core and its decomposition have been applied in various areas, such as social networks, the world wide web, and biology. A graph can be decomposed into an elegant k -core hierarchy to facilitate cohesive subgraph discovery and network analysis. As many real-life graphs are fast evolving, existing works proposed efficient algorithms to maintain the coreness value of every vertex against structure changes. However, the maintenance of the k -core hierarchy in existing studies is not complete because the connections among different k -cores in the hierarchy are not considered. In this paper, we study hierarchical core maintenance which is to compute the k -core hierarchy incrementally against graph dynamics. The problem is challenging because the change of hierarchy may be large and complex even for a slight graph update. In order to precisely locate the area affected by graph dynamics, we conduct in-depth analyses on the structural properties of the hierarchy, and propose well-designed local update techniques. Our algorithms significantly outperform the baselines on runtime by up to 3 orders of magnitude, as demonstrated on 10 real-world large graphs.
62
What is Twitter, a social network or a news media?
Haewoon Kwak, Changhyun Lee, Hosung Park et al. · 2010 · 6.7K citations · Full text
Network structure and minimum degree
Stephen B. Seidman · Social Networks · 1983 · 1.9K citations