Communities In Social Networks

Abstract

Within the broad area of social network analysis research, the study of communities has become an important and popular topic. However, there is little consensus within the field regarding the structure of communities, and the research literature contains dozens of competing community detection algorithms and community evaluation metrics. In this dissertation, we present several connected contributions, each related to the general theme of communities in social networks. First, in order to motivate the study of communities in general, as well as the work later in this dissertation, we present an application of community detection methods to the link prediction problem, in which one attempts to predict which edges in an incomplete network dataset are most likely to exist in the complete network dataset. We demonstrate that use of community membership information can improve the accuracy of various simple link prediction methods, sometimes by a large margin. Next, we examine the structure of "real" annotated communities and present a novel community detection method. In this chapter, we study real networks, each containing metadata that allow us to identify "real" communities (e.g., all graduate students in the same department). We study details of these communities' structures and, based on these results, create and evaluate an algorithm for finding overlapping communities in networks. We show that this method outperforms other state-of-the-art community detection methods. Finally, we present two related sections. In the first of these two chapters, we describe the Community Structure Analysis Framework (CSAF), a machinelearning-based method for comparing and studying the structures and features of communities produced through different methods. The CSAF allows a practitioner to select a community detection method best suited for his or her application needs, and allows a researcher to better understand the behavior of different community detection algorithms. In the second of these chapters, we apply the CSAF to a variety of network datasets from different domains, and use it to obtain interesting results about the structures of communities identified algorithmically as well as through metadata annotation.