CS Events Monthly View


On Core Structures of Social Graphs


Download as iCal file

Monday, June 05, 2017, 11:30am


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.

Speaker: Priya Govindan



Location : CoRE B (305)


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

Event Type: Pre-Defense


Dept. of Computer Science