Community Extraction for Social Networks

• Activity Number: 561
• Type: Topic Contributed
• Date/Time: Wednesday, August 3, 2011 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Yunpeng Zhao*+ and Liza Levina and Ji Zhu
• Companies: University of Michigan and University of Michigan and University of Michigan
• Keywords: social networks ; community detection ; block model

Abstract

Analysis of networks and in particular discovering communities within networks has been a focus of recent work in several fields and has diverse applications. Most community detection methods focus on partitioning the entire network into communities, with the expectation of many ties within communities and few ties between. However, many networks contain nodes that do not fit in with any of the communities, and forcing every node into a community can distort results. Here we propose a new framework that focuses on community extraction instead of partition, which allows for weakly connected nodes. The main idea is that the strength of a community should not depend on ties between members of other communities, only on ties within itself and ties to the outside world. The proposed extraction criterion has a natural probabilistic interpretation in a wide class of models and performs well on simulated and real networks. Under the additional assumption of the block model, we establish asymptotic consistency of estimated node labels and propose a hypothesis test for determining the number of communities.