2012 Poster Sessions : Model-Based Approach to Detecting Densely Overlapping Communities in Networks

Student Name : Jaewon Yang
Advisor : Jure Leskovec
Research Areas: Computer Systems
Abstract:
Networks are a powerful way to represent social, technological and biological systems. Nodes in such networks organize into densely linked communities of related nodes that correspond to functional modules, such as social communities, functionally related proteins, or topically related webpages. Identifying such communities | the building blocks of networks is crucial to the understanding of the structural and functional roles of networks. Communities in networks often overlap in the sense that a node can belong to multiple communities. However, existing community detection methods implicitly assume that overlaps between communities are less densely connected than the non-overlapping parts of communities. As a consequence, the more community memberships the nodes have in common, the less likely it is that they are linked. In contrast, we find that on a wide variety of networks drawn from a range of domains that nodes in community overlaps are more densely connected than the non-overlapping parts of communities. This is due to the increase in probability of linking as a function of the number of shared community memberships. Existing community detection methods fail to detect communities with such overlaps. We propose a model-based community detection method that builds on bipartite node-community a liation networks. Our method successfully detects overlapping as well as non-overlapping communities. We accurately identify relevant communities in networks ranging from biological protein-protein interaction networks to social, collaboration and information networks. Our results show that while networks organize into overlapping communities, globally networks also exhibit a nested core-periphery structure, which arises as a consequence of overlapping parts of communities being more densely connected.

Bio:
Jaewon is a Ph,D student at Stanford University advised by Prof. Jure Leskovec. His research focuses on the applied machine learning and data mining on social networks. He received a Master in Statistics from Stanford university and a BS degree in Electrical Engineering from Seoul National University. Prior to Stanford, Jaewon worked at an IT start-up in Korea as a software engineer for three years.