Survey on Social Community Detection <s> From graphs to overlapping communities, hypergraphs (B1) <s> Abstract Ethnographers have traditionally defined human groups as disjoint collections of individuals who are linked to each other by regular interaction, shared perceptions and affective ties. They are internally differentiated: some members occupy a central position in the group, others are on the periphery or somewhere in between. This way of characterising a group is intuitive to seasoned observers but social network analysts seek a more systematic method for determining groups. Freeman [Freeman, L.C., 1996. Cliques, Galois lattices, and the structure of human social groups, Social Networks 18, 173–187.] describes a formal model based on the concept of overlapping social network cliques. Freeman's analysis produces results that are consistent with ethnographic results but his technique is not easily implemented for very large data sets. This paper describes two algorithms based on Freeman's clique–lattice analysis. The first implements his technique exactly; the second is a modification that exploits the clique structure, thereby enabling the analysis of large complex networks. We apply both algorithms to a real data set and compare the results. <s> BIB001 </s> Survey on Social Community Detection <s> From graphs to overlapping communities, hypergraphs (B1) <s> The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks. <s> BIB002 </s> Survey on Social Community Detection <s> From graphs to overlapping communities, hypergraphs (B1) <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> BIB003 </s> Survey on Social Community Detection <s> From graphs to overlapping communities, hypergraphs (B1) <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 overlapping communities, hypergraphs (B1) <s> We propose an algorithm for finding overlapping community structure in very large networks. The algorithm is based on the label propagation technique of Raghavan, Albert and Kumara, but is able to detect communities that overlap. Like the original algorithm, vertices have labels that propagate between neighbouring vertices so that members of a community reach a consensus on their community membership. Our main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Our algorithm can also handle weighted and bipartite networks. Tests on an independently designed set of benchmarks, and on real networks, show the algorithm to be highly effective in recovering overlapping communities. It is also very fast and can process very large and dense networks in a short time. <s> BIB005
TThis class of methods remains atypical, yet a number of authors have attempted its implementation. The input data is a normal graph, while the output is a list of node groups representing the communities of the initial graph; these communities may indeed overlap. The result could be represented as a hypergraph. The survey BIB003 mentions several methods without providing any description along with two surveys BIB004  that describe methods found in this class. The most famous of such methods is "Clique percolation"; this algorithm devised by Palla et al. BIB002 speculates that the internal edges of a community are likely to form cliques due to their high density. On the other hand, it is unlikely that intercommunity edges form cliques. Palla et al. use the term k-clique in reference to a complete graph with k vertices. Two k-cliques are adjacent if they share k-1 vertices. The union of adjacent k-cliques constitutes s a k-clique chain. Two k-cliques are connected if they form part of a k-clique chain. Moreover, a k-clique community is the largest connected subgraph obtained by uniting a k-clique with all k-cliques connected to it. Several authors have proposed improvements to this method given that the computing time may increase exponentially with the number of nodes or edges in the graph. This method has been determined to provide good results. Other authors have found alternative ways to extract overlapping communities, such as  BIB005 BIB001 . As an example, BIB005 enhanced the Girvan-Newman algorithm (see above) in its ability to detect overlapping communities.