Survey on Social Community Detection <s> Community definitions <s> By using the concepts of antimetry andn-chain it is possible to define and to investigate some properties of connectivity in a sociometric group. It is shown that the number of elements in a group, the number of antimetries, and the degree of connectivity must satisfy certain inequalities. Using the ideas of connectivity, a generalized concept of clique, called ann-clique, is introduced.n-cliques are shown to have a very close relationship to the existence of cliques in an artificial structure defined on the same set of elements, thus permitting the determination ofn-cliques by means of the same simple matrix procedures used to obtain the clique structures. The presence of two or morem-cliques, wherem is the number of elements in the group, is proved to mean an almost complete splitting of the group. <s> BIB001 </s> Survey on Social Community Detection <s> Community definitions <s> The problem of decomposing a network into different groups of electrical components, which are interconnected by the minimum number of leads, is discussed. For this purpose, minimal groups of components are defined as the ones fulfilling a chosen minimality criterion, and a number of their properties are illustrated. Some of these properties are directly employed in a procedure for the determination of all the minimal groups for a given network. <s> BIB002 </s> Survey on Social Community Detection <s> Community definitions <s> For at least twenty‐five years, the concept of the clique has had a prominent place in sociometric and other kinds of sociological research. Recently, with the advent of large, fast computers and with the growth of interest in graph‐theoretic social network studies, research on the definition and investigation of the graph theoretic properties of clique‐like structures has grown. In the present paper, several of these formulations are examined, and their mathematical properties analyzed. A family of new clique‐like structures is proposed which captures an aspect of cliques which is seldom treated in the existing literature. The new structures, when used to complement existing concepts, provide a new means of tapping several important properties of social networks. <s> BIB003 </s> Survey on Social Community Detection <s> Community definitions <s> Abstract Seidman (1983a) has suggested that the engineering concept of LS sets provides a good formalization of the intuitive network notion of a cohesive subset. Some desirable features that LS sets exhibit are that they are difficult to disconnect by removing edges, they are relatively dense within and isolated without, they have limited diameter, and individual members have more direct links to other members than to non-members. Unfortunately, this plethora of features means that LS sets occur only rarely in real data. It also means that they do not make good independent variables for structural analyses in which greater-than-expected in-group homogeneity is hypothesized with respect to some substantive dependent variable, because it is unclear which aspect of the LS set was responsible for the observed homogeneity. We discuss a variety of generalizations and relations of LS sets based on just a few of the properties possessed by LS sets. Some of these simpler models are drawn from the literature while others are introduced in this paper. One of the generalizations we introduce, called a lambda set, is based on the property that members of the set have greater edge connectivity with other members than with non-members. This property is shared by LS sets. Edge connectivity satisfies the axioms of an ultrametric similarity measure, and so LS sets and lambda sets are shown to correspond to a particular hierarchical clustering of the nodes in a network. Lambda sets are straightforward to compute, and we have made use of this fact to introduce a new algorithm for computing LS sets which runs an order of magnitude faster than the previous alternative. <s> BIB004 </s> Survey on Social Community Detection <s> Community definitions <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> BIB005 </s> Survey on Social Community Detection <s> Community definitions <s> Social scientists have shown an increasing interest in understanding the structure of knowledge communities, and particularly the organization of"epistemic communities", that is groups of agents sharing common knowledge concerns. However, most existing approaches are based only on either social relationships or semantic similarity, while there has been roughly no attempt to link social and semantic aspects. In this paper, we introduce a formal framework addressing this issue and propose a method based on Galois lattices (or concept lattices) for categorizing epistemic communities in an automated and hierarchically structured fashion. Suggesting that our process allows us to rebuild a whole community structure and taxonomy, and notably fields and subfields gathering a certain proportion of agents, we eventually apply it to empirical data to exhibit these alleged structural properties, and successfully compare our results with categories spontaneously given by domain experts. <s> BIB006 </s> Survey on Social Community Detection <s> Community definitions <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> BIB007 </s> Survey on Social Community Detection <s> Community definitions <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> BIB008 </s> Survey on Social Community Detection <s> Community definitions <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> BIB009 </s> Survey on Social Community Detection <s> Community definitions <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> BIB010 </s> Survey on Social Community Detection <s> Community definitions <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> BIB011
Defining a community is quite a challenging task. Definitions vary from author to author and from algorithm to algorithm. The most commonly used definition is that of Yang BIB011 : "a community as a group of network nodes, within which the links connecting nodes are dense but between which they are sparse". This definition is applicable for graphs and could be extended to bipartite graphs. Fortunato BIB009 identifies three levels to define a community: local definitions, global definitions, and definition based on vertex similarity. In the local definition group, a definition of communities consists of: "parts of the graph with few ties to the rest of the system". In this partition, communities are studied from their inner structure independently of the remaining part of the graph. In the global definition group, a global criterion associated with the graph is used to compute communities. This global criterion is dependent on the algorithm implemented to locate communities. Either a clustering criterion or a distance-based criterion may be introduced; more often, the criterion commonly used shows that the graph contains a community structure different from that of a random graph. In the vertex similarity-based community definition group, communities are considered as groups of vertices similar to one another. Fortunato BIB009 further defines communities, in also calling them clusters or modules, as "groups of vertices that probably share common properties and/or play similar roles within the graph". His assigned definition depends on the algorithm employed, resulting in the identification of at least eight different definitions: • Clique: subgroups whose members are all "friends" (i.e. connected with an edge) to each other  , • n-clique with two variants : maximal sub-graphs such that the distance of each pair from its vertices is not greater than n BIB001 , • k-plex: maximal subgraph in which each vertex is adjacent to all other vertices of the subgraph except at most k of them BIB003 , • LS-set (weak community) : subgraph such that the internal degree is greater than the external degrees BIB002 , • lambda set: subgraph where each pair of vertices has a greater edge connectivity than any pair formed by one vertex of the subgraph and one outside the subgraph BIB004 , • communities based on either a fitness measure or a quality measure, • communities determined by means of modularity-based algorithms, • clusters: communities derived using well-known clustering methods  . Porter BIB010 recalls the origins of community study in the fields of sociology and anthropology. He defines communities as: "cohesive groups of nodes that are connected more densely to each other than to the nodes in other communities". The difference in methods highlighted in his survey relies on a definition of the expression "more densely", which is identified with five types of algorithms, namely: clustering techniques  , quality function algorithms  , centrality based community detection algorithms BIB005 and other similar ones, clique percolation algorithms BIB007 and lastly modularity optimization algorithms  . N. Gulbahce and S. Lehmann BIB008 define a community as "a densely connected subset of nodes that is only sparsely linked to the remaining network". Papadopoulos  ultimately defines communities as: "groups of vertices that are more densely connected to each other than to the rest of the network". It can be seen that all definitions are quite similar yet may still differ in their associated formal mathematical definition. Communities may also be considered from a different perspective. The initial approach partitions the underlying graph, i.e. by dividing the existing graph or network structure into distinct communities using the optimal algorithms. The second approach then detects overlapping communities and seeks the best community arrangement. In BIB006 Roth defines a new type of community: "epistemic communities", which are "knowledge communities or groups of agents sharing common knowledge concerns", for instance a group of researchers investigating a single precise topic. This new type of community concept requires new kinds of structures to proceed with their description. Roth has opted to use Galois lattices.