Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> Abstract A procedure for forming hierarchical groups of mutually exclusive subsets, each of which has members that are maximally similar with respect to specified characteristics, is suggested for use in large-scale (n > 100) studies when a precise optimal solution for a specified number of groups is not practical. Given n sets, this procedure permits their reduction to n − 1 mutually exclusive sets by considering the union of all possible n(n − 1)/2 pairs and selecting a union having a maximal value for the functional relation, or objective function, that reflects the criterion chosen by the investigator. By repeating this process until only one group remains, the complete hierarchical structure and a quantitative estimate of the loss associated with each stage in the grouping can be obtained. A general flowchart helpful in computer programming and a numerical example are included. <s> BIB001 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> The main purpose of this paper is to describe a process for partitioning an N-dimensional population into k sets on the basis of a sample. The process, which is called 'k-means,' appears to give partitions which are reasonably efficient in the sense of within-class variance. That is, if p is the probability mass function for the population, S = {S1, S2, * *, Sk} is a partition of EN, and ui, i = 1, 2, * , k, is the conditional mean of p over the set Si, then W2(S) = ff=ISi f z u42 dp(z) tends to be low for the partitions S generated by the method. We say 'tends to be low,' primarily because of intuitive considerations, corroborated to some extent by mathematical analysis and practical computational experience. Also, the k-means procedure is easily programmed and is computationally economical, so that it is feasible to process very large samples on a digital computer. Possible applications include methods for similarity grouping, nonlinear prediction, approximating multivariate distributions, and nonparametric tests for independence among several variables. In addition to suggesting practical classification methods, the study of k-means has proved to be theoretically interesting. The k-means concept represents a generalization of the ordinary sample mean, and one is naturally led to study the pertinent asymptotic behavior, the object being to establish some sort of law of large numbers for the k-means. This problem is sufficiently interesting, in fact, for us to devote a good portion of this paper to it. The k-means are defined in section 2.1, and the main results which have been obtained on the asymptotic behavior are given there. The rest of section 2 is devoted to the proofs of these results. Section 3 describes several specific possible applications, and reports some preliminary results from computer experiments conducted to explore the possibilities inherent in the k-means idea. The extension to general metric spaces is indicated briefly in section 4. The original point of departure for the work described here was a series of problems in optimal classification (MacQueen [9]) which represented special <s> BIB002 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is, shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorith... <s> BIB003 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appeal and usefulness as one of the steps in exploratory data analysis. However, clustering is a difficult problem combinatorially, and differences in assumptions and contexts in different communities has made the transfer of useful generic concepts and methodologies slow to occur. This paper presents an overviewof pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval. <s> BIB004 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB005 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> We propose a novel approach to clustering, based on deterministic analysis of random walks on the weighted graph associated with the clustering problem. The method is centered around what we shall call separating operators, which are applied repeatedly to sharpen the distinction between the weights of inter-cluster edges (the so-called separators), and those of intra-cluster edges. These operators can be used as a stand-alone for some problems, but become particularly powerful when embedded in a classical multi-scale framework and/or enhanced by other known techniques, such as agglomerative clustering. The resulting algorithms are simple, fast and general, and appear to have many useful applications. <s> BIB006 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB007 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on particular aspects of this rather vague concept have been proposed no conclusive argument on their appropriateness has been given. As a first step towards understanding the consequences of particular conceptions, we conducted an experimental evaluation of graph clustering approaches. By combining proven techniques from graph partitioning and geometric clustering, we also introduce a new approach that compares favorably. <s> BIB008 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> We describe a methodology for the automatic identification of communities of practice from email logs within an organization. We use a betweeness centrality algorithm that can rapidly find communities within a graph representing information flows. We apply this algorithm to an email corpus of nearly one million messages collected over a two-month span, and show that the method is effective at identifying true communities, both formal and informal, within these scale-free graphs. This approach also enables the identification of leadership roles within the communities. These studies are complemented by a qualitative evaluation of the results in the field. <s> BIB009 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log^2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400,000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers. <s> BIB010 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> The networks considered here consist of sets of intercon- nected vertices, examples of which include social networks, technological networks, and biological networks. Two important issues are to measure the extent of proximity between vertices and to identify the community structure of a network. In this paper, the proximity index between two nearest-neighboring vertices of a network is measured by a biased Brown- ian particle which moves on the network. This proximity index integrates both the local and the global structural information of a given network, and it is used by an agglomerative hierarchical algorithm to identify the community structure of the network. This method is applied to several artificial or real-world networks and satisfying results are attained. Find- ing the proximity indices for all nearest-neighboring vertex pairs needs a computational time that scales as O(N 3 ), with N being the total number of vertices in the network. <s> BIB011 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties. <s> BIB012 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB013 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB014 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two nonoverlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of node, but links have an origin and an end. We show that directed unipartite networks can be conveniently represented as bipartite networks for module identification purposes. We report on an approach especially suited for module detection in bipartite networks, and we define a set of random networks that enable us to validate the approach. <s> BIB015 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <s> Networks in nature possess a remarkable amount of structure. Via a series of data-driven discoveries, the cutting edge of network science has recently progressed from positing that the random graphs of mathematical graph theory might accurately describe real networks to the current viewpoint that networks in nature are highly complex and structured entities. The identification of high order structures in networks unveils insights into their functional organization. Recently, Clauset, Moore, and Newman, introduced a new algorithm that identifies such heterogeneities in complex networks by utilizing the hierarchy that necessarily organizes the many levels of structure. Here, we anchor their algorithm in a general community detection framework and discuss the future of community detection. <s> BIB016 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB017 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB018 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB019 </s> Survey on Social Community Detection <s> State-of-the-art in community detection surveys <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> BIB020
Most surveys classify research papers and methods according to the type of community detection algorithm. The first of these seven main surveys by S. Fortunato BIB017 is exhaustive with respect to many community detection methods and has been based on a graphic representation. This survey provides an effective overview of the field and describes the methodological foundations of community detection, adopting a statistical physics perspective and specifically focusing on techniques designed by statistical physicists. His discussion also includes critical issues like: the significance of clustering, the procedure by which methods should be tested and compared to one another, and applications to real networks. Methods are classified into eight families, i.e.: • traditional methods based on clustering like k-means BIB002 and others applications  , • divisive algorithms mainly based on hierarchical clustering  , • modularity-based algorithms BIB007 BIB008 BIB010 and other similar algorithms, • spectral algorithms BIB003 , • dynamic algorithms   and other similar algorithms, • statistical inference-based methods [2] , • multi-resolution methods  , • and lastly methods to find overlapping communities BIB012 BIB013 and other miscellaneous methods. The second survey, conducted by Porter BIB018 only includes graph partitioning approaches and offers insight into graphical techniques through citing the first survey. An extensive set of techniques is highlighted, as are some of the most important unresolved issues remaining. Application examples are also given on some of the largest social networks in addition to grouping community detection into five main techniques: • centrality based techniques built around the Newman algorithm BIB007 , • local methods around the k-Clique percolation method BIB012 , • modularity optimization methods around the Newman algorithm  , • spectral partitioning methods around Simon's algorithm BIB003 • and lastly physics-based methods inspired by Potts law  . The third survey by B. Yang BIB020 is quite exhaustive relative to all techniques relying on graphical representation and produces a good overview of the field through classifying all techniques in a tree structure, according to three categories: • optimization based algorithms   BIB015 , • heuristic algorithms BIB005 BIB009 , • similarity based algorithms and hybrid methods  . The fourth one from N. Gulbahce and S. Lehmann BIB016 is a partial survey analyzing hierarchical type community detection methods and provides a number of leads for future community detection approaches. The fifth survey by Pons  incorporates several community detection methods and classifies them into five different families: • Classical approaches including classical graph partitioning, e.g. spectral bisection from BIB003 , Kernighan & Lin  , clustering BIB004 and hierarchical clustering like BIB001 . • Separative approaches attempting to split a graph into several communities by deleting the edges connecting distinct communities. In this group, Pons places the well-known Girvan-Newman algorithm BIB007 , and other variant approaches. • agglomerative approaches quite similar to their hierarchical counterparts and include a method based on optimized modularity by Newman  and others algorithms. • Random walk type algorithms BIB006 and others based on the mean time required to reach a vertex BIB011 . • Lastly, a broad group of miscellaneous approaches. The Pons survey has only examined graph partitioning approaches. The sixth survey by Papadopoulos  classifies community detection techniques in five methodological categories: • cohesive subgraph discovery BIB012 , • vertex clustering  , • community quality optimization BIB007 BIB014 , • divisive BIB007 • and model-based methods BIB019 . The seventh and last survey was undertaken by Danon  and primarily focuses on the performance of each type of algorithm. Among these seven surveys, only one offers leads on overlapping communities, while none make use of hypergraph structures. Another domain overlooked by these surveys is Galois lattice structures. As will be described below, Galois lattices are more complex structures than regular graphs, yet they provide more semantics to network structures.