Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known—a collaboration network and a food web—and find that it detects significant and informative community divisions in both cases. <s> BIB001 </s> Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems. <s> BIB002 </s> Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad hoc modular networks. <s> BIB003 </s> Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks. <s> BIB004 </s> Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> We survey some of the concepts, methods, and applications of community detection, which has become an increasingly important area of network science. To help ease newcomers into the field, we provide a guide to available methodology and open problems, and discuss why scientists from diverse backgrounds are interested in these problems. As a running theme, we emphasize the connections of community detection to problems in statistical physics and computational optimization. <s> BIB005 </s> Survey on Social Community Detection <s> From graphs to partitions (cell A1) <s> A network community refers to a group of network nodes within which the links connecting them are dense but between which they are sparse. A network community mining problem (NCMP for short) can be stated as the problem of finding all such communities from a given network. A large variety of problems can be translated into NCMPs, ranging from graph partition applications, such as VLSI layout [1, 2], large-scale scientific computing [3, 4], load balance for distributed computing [5, 6], and image segmentation [19], to complex network analysis, such as social network analysis [7, 8, 9], biological network analysis[11, 12, 24], and Web pages clustering [13, 14, 15]. Network communities in different application contexts may imply different meanings and serve different purposes. For example, they may be sets of electronic units closely placed on a VLSI circuit board, collections of processes that frequently communicate with each other, segments of an image, circles of a society within which people share common interests and keep frequent contacts, classes of Web pages related to common topics, or groups of proteins exhibiting similar functions. Discovering such hidden patterns from networks will enable us to better understand the structural and/or functional characteristics of networks and to more effectively utilize them. The remainder of this chapter is organized as follows: Section 2 introduces some of the existing methods for solving NCMPs. Section 3 presents several interesting applications of NCMPs as related to social network analysis. Finally, Section 4 concludes the chapter. <s> BIB006
Most community detection algorithms lie in this class of methods. The input data is a normal graph (i.e. a set of vertices representing individuals, who are connected by edges), and the output is a list of node groups representing the communities on the initial graph. Each individual belongs to one and only one community. All surveys mentioned in Section 3 describe these algorithms in full detail; the following algorithm classification has been adopted: top-down (separate) methods in S BIB004 ,  ; bottom-up (agglomerative) and/or clustering methods in S BIB004  BIB006 BIB005 ,  ; optimization-based algorithms BIB006 and heuristic algorithms BIB006 . The three most popular algorithms will be discussed hereafter, i.e. the Girvan-Newman algorithm BIB001 based on intermediate cen-trality, the Newman algorithm  BIB002 based on modularity and the Louvain Algorithm BIB003 .