Round Table: Tanmoy Chakrabroty - Aspects of Community Analysis in Large Graphs
The College of IS&T Round Table presents:
Department of Computer Science & Engineering, Indian Institute of Technology, Kharagpur, India
Aspects of Community Analysis in Large Graphs
Friday, September 5th, 2014
11:30 a.m. to 1:00 p.m.
(Talk starts at noon.)
Pizza and sodas provided on a first-come, first-served basis.
Please RSVP to firstname.lastname@example.org.
Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing certain parameters which are generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. We identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. On the other hand, another important aspect in community analysis is to understand whether a network is indeed modular and how resilient the community structure is under perturbations. To address this issue, we propose a new vertex-based metric called "permanence", that can quantitatively give an estimate of the community-like structure of the network. The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon the following two factors: (i) the distribution of external connectivity of the vertex to individual communities and not the total external connectivity, and (ii) the strength of its internal connectivity and not just the total internal edges. We demonstrate that compared to other metrics, permanence provides (i) a more accurate estimate of a derived community structure to the ground-truth community and (ii) is more sensitive to perturbations in the network. As a by-product of this study, we have also developed a community detection algorithm based on maximizing permanence. For a modular network structure, the results of our algorithm match well with ground-truth communities.
Tanmoy Chakrabroty is a PhD scholar in the Department of Computer Science & Engineering, Indian Institute of Technology, Kharagpur, India since December, 2011. He has completed his BTech in Computer Science and Engineering from West Bengal University of Technology, India in 2009, and ME in Computer Science, Jadavpur University, Kolkata, India in 2011. He is a recipient of prestigious Google India PhD Fellowship award. He has also received President Gold Medal award and Best Student award during his bachelor degree. The broad area of his research covers Complex Networks, Social Media, Graph Theory, Natural Language Processing. In particular, he is interested in analyzing topological structure of complex systems, modeling complex interaction phenomena, designing real-time search and recommendation systems, stylemoetry analysis of authors in literature and scientific documents.