报告题目：Cohesive Subgraph Computation over Large Graphs
报告人：Dr. Lijun Chang
报告人单位：University of New South Wales
报告人简介：Lijun Chang is currently an ARC DECRA (Discovery Early Career Researcher Award) research fellow in the School of Computer Science and Engineering at University of New South Wales. He received his B.Eng. in computer science and technology from Renmin University of China in 2007, and Ph.D. in Systems Engineering and Engineering Management from Chinese University of Hong Kong in 2011. His research interests are in the fields of big graph (network) analytics, with a focus on devising practical algorithms and theoretical foundations for massive graph analysis. He has published over 35 papers in top-tier Database conferences and journals, including 7 SIGMOD papers, 8 VLDB papers, 9 ICDE papers, 1 KDD paper, 6 VLDB Journal papers, 3 TKDE papers, and 1 Algorithmica paper.
报告摘要：With the proliferation of graph applications and the recent advent of Big Data, research efforts have been devoted towards many fundamental problems in managing and analysing big graph data. In this talk, I focus on the basic techniques for efficient cohesive subgraph computation over large graphs. The general guideline is that to efficiently process graphs with billions of edges, an algorithm should run in subquadratic time and take c m+O(n) memory space, where c is a small constant and should be analyzed explicitly, and n and m are the number of vertices and the number of edges, respectively. I present the techniques by investigating cohesive subgraph computation with four different types of cohesiveness measures, k-core-based (core decomposition), edge density-based (densest subgraph computation), edge connectivity-based (k-edge connected component computation), and higher-order structure-based (truss decomposition, triangle densest subgraph computation, structural graph clustering).