CS Events Monthly View
On Core Structures of Social Graphs
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