CS Events Monthly View

Given graph G, the k-core is a maximal subgraph such that the minimum degree in the induced subgraph is k. It finds many applications in social graph analysis.

1.We present a O(n log d) space algorithm to estimate k-cores in large graphs, where n is the number of nodes, and d is the maximum degree. Our experimental study shows space savings up to 60X with average relative error less than 2.3%.

2. We propose 'k-peak' decomposition to understand different k-core density at different regions of graphs. We demonstrate that k-peak decomposition presents a global mapping of a graph.

3. K-core computing is related to h-index. We present algorithms to compute h-index in various streaming settings and get a (1 pm epsilon) estimate of the h-index with sublinear, ie, polylog or even O(1) space.

Our work contributes to the understanding of the k-core structure of social graphs.