Survey on Social Community Detection <s> The concept of modularity <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> The concept of modularity <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> BIB002
Modularity has been introduced to measure the quality of community algorithms. Newman BIB001 proceeded with the initial introduction, in providing the following formula: where • e ij : number of edges having one end in group i and the other end in group j. • a i = j e ij : number of edges having one end in group i. This quantity Q measures the fraction of edges in the network that connect vertices of the same type (i.e. "intra-community" edges) minus the expected value of the same quantity in a network with the same community divisions yet with random connections between vertices. Modularity measures the capacity of a given graph partition to yield the densest groups. This formula has mainly been used by researchers in order to measure the ability of a community detection algorithm to obtain a satisfactory partition of a given graph. Moreover, the formula may be adapted to weighted graphs (i.e. graphs whose edges display different weights or lengths), like in BIB002 . 3 State-of-the-art assessment: existing surveys This section will address the body of existing surveys on community detection. Most surveys primarily focus on the graph structure aspect of communities. Seven of the main existing surveys have in fact been recently conducted. Since the concept of community may differ, this existing body of surveys defines communities before classifying the methods employed according to various classification systems. This study will start by determining which definitions are provided for these different community detection methods before presenting a state-of-the-art on existing surveys.