Skip to content Skip to navigation

Pre-Defense: On Core Structures of Social Graphs


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.

Priya Govindan
CoRE B (305)
Event Date: 
06/05/2017 - 11:30am
Prof. S. Muthukrishnan (Chair), Prof. Badri Nath, Prof. William Steiger, Prof. Laks V.S. Lakshmanan (University of British Columbia)
Event Type: 
Dept. of Computer Science