Survey on Social Community Detection <s> quality measure <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> BIB001 </s> Survey on Social Community Detection <s> quality measure <s> Although the inference of global community structure in networks has recently become a topic of great interest in the physics community, all such algorithms require that the graph be completely known. Here, we define both a measure of local community structure and an algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time. This algorithm runs in time O(k2d) for general graphs when d is the mean degree and k is the number of vertices to be explored. For graphs where exploring a new vertex is time consuming, the running time is linear, O(k). We show that on computer-generated graphs the average behavior of this technique approximates that of algorithms that require global knowledge. As an application, we use this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer. <s> BIB002 </s> Survey on Social Community Detection <s> quality measure <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> BIB003
A community detection scheme may be considered effective or ineffective by using a so-called quality function. This specific measure provides a means for comparing quality across several community detection schemes. One of these quality measures, "Modularity", which was introduced by Newman BIB001 and has already been mentioned in Section 2.4, is very famous and widely used. Modularity expresses the fact that a community has a high density ratio as compared to the same graph without any community structure. This high-density criterion is considered to offer good community detection quality. Some authors have combined a local quality measure (based on modularity) along with the potential of community communication in order to produce an overall quality ratio (see for example BIB002 ). Several authors cited in the Fortunato survey BIB003 (in his Section C2) note that a community detection method yielding strong modularity results is not always the best choice, in arguing that low modularity values could provide greater stability in communities.