Survey on Social Community Detection <s> Approach classification <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> BIB001 </s> Survey on Social Community Detection <s> Approach classification <s> Using Galois Lattices to Represent Network Data Author(s): Linton C. Freeman and Douglas R. White Source: Sociological Methodology, Vol. 23 (1993), pp. 127-146 Published by: American Sociological Association Stable URL: http://www.jstor.org/stable/271008 Accessed: 16-03-2017 20:56 UTC JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact support@jstor.org. Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at http://about.jstor.org/terms American Sociological Association is collaborating with JSTOR to digitize, preserve and extend access to Sociological Methodology This content downloaded from 128.200.102.71 on Thu, 16 Mar 2017 20:56:14 UTC All use subject to http://about.jstor.org/terms <s> BIB002 </s> Survey on Social Community Detection <s> Approach classification <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> BIB003 </s> Survey on Social Community Detection <s> Approach classification <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> BIB004 </s> Survey on Social Community Detection <s> Approach classification <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> Approach classification <s> We present a method that allows for the discovery of communities within graphs of arbitrary size in times that scale linearly with their size. This method avoids edge cutting and is based on notions of voltage drops across networks that are both intuitive and easy to solve regardless of the complexity of the graph involved. We additionally show how this algorithm allows for the swift discovery of the community surrounding a given node without having to extract all the communities out of a graph. <s> BIB006 </s> Survey on Social Community Detection <s> Approach classification <s> We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have nontrivial clustering or network transitivity and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could account for the observed clustering. We demonstrate that group structure in networks can also account for degree correlations. We show using a simple model that we should expect assortative mixing in such networks whenever there is variation in the sizes of the groups and that the predicted level of assortative mixing compares well with that observed in real-world networks. <s> BIB007 </s> Survey on Social Community Detection <s> Approach classification <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> BIB008 </s> Survey on Social Community Detection <s> Approach classification <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> BIB009 </s> Survey on Social Community Detection <s> Approach classification <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> BIB010 </s> Survey on Social Community Detection <s> Approach classification <s> We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a new centrality measure that identifies those vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks. <s> BIB011 </s> Survey on Social Community Detection <s> Approach classification <s> We present a method for describing taxonomy evolution. We focus on the structure of epistemic communities (ECs), or groups of agents sharing common knowledge concerns. Introducing a formal framework based on Galois lattices, we categorize ECs in an automated and hierarchically structured way and propose criteria for selecting the most relevant epistemic communities - for instance, ECs gathering a certain proportion of agents and thus prototypical of major fields. This process produces a manageable, insightful taxonomy of the community. Then, the longitudinal study of these static pictures makes possible an historical description. In particular, we capture stylized facts such as field progress, decline, specialization, interaction (merging or splitting), and paradigm emergence. The detection of such patterns in epistemic networks could fruitfully be applied to other contexts. <s> BIB012 </s> Survey on Social Community Detection <s> Approach classification <s> We present a new benchmarking procedure that is unambiguous and specific to local community finding methods, allowing one to compare the accuracy of various methods. We apply this to new and existing algorithms. A simple class of synthetic benchmark networks is also developed, capable of testing properties specific to these local methods. <s> BIB013 </s> Survey on Social Community Detection <s> Approach classification <s> Modularity is a widely used quality measure for graph clusterings. Its exact maximization is prohibitively expensive for large graphs. Popular heuristics progressively merge clusters starting from singletons (coarsening), and optionally improve the resulting clustering by moving vertices between clusters (refinement). This paper experimentally compares existing and new heuristics of this type with respect to their effectiveness (achieved modularity) and runtime. For coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria. For refinement, a new multi-level algorithm produces significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature. <s> BIB014 </s> Survey on Social Community Detection <s> Approach classification <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> BIB015 </s> Survey on Social Community Detection <s> Approach classification <s> Complex network topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of a modularity function, given by Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new data set which could be used as a reference benchmark for overlapping community structures identification. <s> BIB016 </s> Survey on Social Community Detection <s> Approach classification <s> In this paper, we presents a research work based on formal concept analysis and interest measures associated with formal concepts. This work focuses on the ability of concept lattices to discover and represent special groups of individuals, called social communities. Concept lattices are very useful for the task of knowledge discovery in databases, but they are hard to analyze when their size become too large. We rely on concept stability and support measures to reduce the size of large concept lattices. We propose an example from real medical use cases and we discuss the meaning and the interest of concept stability for extracting and explaining social communities within a healthcare network. <s> BIB017 </s> Survey on Social Community Detection <s> Approach classification <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> BIB018 </s> Survey on Social Community Detection <s> Approach classification <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> BIB019 </s> Survey on Social Community Detection <s> Approach classification <s> In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm that produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this. <s> BIB020 </s> Survey on Social Community Detection <s> Approach classification <s> This paper aims at discovering community structure in rich media social networks, through analysis of time-varying, multi-relational data. Community structure represents the latent social context of user actions. It has important applications in information tasks such as search and recommendation. Social media has several unique challenges. (a) In social media, the context of user actions is constantly changing and co-evolving; hence the social context contains time-evolving multi-dimensional relations. (b) The social context is determined by the available system features and is unique in each social media website. In this paper we propose MetaFac (MetaGraph Factorization), a framework that extracts community structures from various social contexts and interactions. Our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multi-relational and multi-dimensional social data; (2) an efficient factorization method for community extraction on a given metagraph; (3) an on-line method to handle time-varying relations through incremental metagraph factorization. Extensive experiments on real-world social data collected from the Digg social media website suggest that our technique is scalable and is able to extract meaningful communities based on the social media contexts. We illustrate the usefulness of our framework through prediction tasks. We outperform baseline methods (including aspect model and tensor analysis) by an order of magnitude. <s> BIB021 </s> Survey on Social Community Detection <s> Approach classification <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> BIB022 </s> Survey on Social Community Detection <s> Approach classification <s> This paper quantitatively explores the social and socio-semantic patterns of constitution of academic collaboration teams. To this end, we broadly underline two critical features of social networks of knowledge-based collaboration: first, they essentially consist of group-level interactions which call for team-centered approaches. Formally, this induces the use of hypergraphs and n-adic interactions, rather than traditional dyadic frameworks of interaction such as graphs, binding only pairs of agents. Second, we advocate the joint consideration of structural and semantic features, as collaborations are allegedly constrained by both of them. Considering these provisions, we propose a framework which principally enables us to empirically test a series of hypotheses related to academic team formation patterns. In particular, we exhibit and characterize the influence of an implicit group structure driving recurrent team formation processes. On the whole, innovative production does not appear to be correlated with more original teams, while a polarization appears between groups composed of experts only or non-experts only, altogether corresponding to collectives with a high rate of repeated interactions. <s> BIB023
All community detection methods will be classified in a grid divided into six categories based on the types of input data and output data; it will then be shown how each author can be placed in this grid. In order to detect communities, the initial input data were considered in network form (whether a social network or biological network, etc.) and represented by different mathematical structures relative to graph structures, which may be of three distinct types: • unipartite graph: this is a normal graph whose vertices are individuals and whose edges are links connecting the individuals (these links may be of various types: friend, family, club, sport, university, etc.); • a bipartite graph: this type of graph may be generated whenever individuals share tags (i.e. terms assigned by users), web pages or links. The first set contains individuals, and the second is a set of tags, web links or documents, etc.; • a multipartite graph: very similar to bipartite graphs, this graph however is composed of several disjoint sets. In this survey, this type of graph has not been directly taken into account since it may be reduced to a bipartite graph, as shown in  and elsewhere. The output data of a community detection method consists mainly of a set of node groups representing communities. The following merit consideration: • Graph partition, where each node is associated with just one group of nodes and where no overlap exists between groups. Partitions are the primary result of most community detection algorithms. • Hypergraph with overlapping communities. • Concept graphs or Galois lattices where nodes share several common properties. The following table (1) explains which type of input and output data each method is capable of accepting. Most existing surveys included in our state-of-the-art evaluation describe community detection methods that may be classified within the "A1" cell of [10,  BIB005   BIB013 BIB008 BIB004 [  BIB006 BIB007 BIB014 BIB011 BIB001 BIB015  B: hypergraph S BIB018 BIB019 : BIB016 BIB020   BIB009 .   BIB021  (overlapping communities) BIB003 , S  : BIB022 BIB009 BIB010 S  : BIB021 C: Galois Hierarchy  : partial results BIB017 BIB023 BIB012 BIB002 Table Legend : Letter S preceding a publication number indicates that this paper is a survey. The expression: S[2]:  , indicates that the survey referenced in paper number 2 cites and comments on the community detection method described by paper number 1, and moreover paper number 1 can be classified according to the table cell where it has been placed.