Georgia Institute of Technology College of Sciences

A special feature possessed by the graphs of social networks is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a polynomial time graph algorithm to decompose a triangle-dense graph into some clusters preserving high edge density and high triangle density in each cluster with respect to the original graph and each cluster has radius 2. And high proportion of triangles of the original graph are preserved in these clusters. Furthermore, if high proportion of edges in the original graph is "locally triangle-dense", then additionally, high proportion of edges of the original graph are preserved in these clusters. In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs" in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.