Skip to content Skip to navigation
Pre-Defense
6/5/2017 11:30 am
CoRE B (305)

On Core Structures of Social Graphs

Priya Govindan, Dept. of Computer Science

Defense Committee: Prof. S. Muthukrishnan (Chair), Prof. Badri Nath, Prof. William Steiger, Prof. Laks V.S. Lakshmanan (University of British Columbia)

Abstract

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.