Survey on Social Community Detection <s> From bipartite graphs to Galois hierarchies (C2) <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> BIB001 </s> Survey on Social Community Detection <s> From bipartite graphs to Galois hierarchies (C2) <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> BIB002 </s> Survey on Social Community Detection <s> From bipartite graphs to Galois hierarchies (C2) <s> We present an application of formal concept analysis aimed at representing a meaningful structure of knowledge communities in the form of a lattice-based taxonomy. The taxonomy groups together agents (community members) who develop a set of notions. If no constraints are imposed on how it is built, a knowledge community taxonomy may become extremely complex and difficult to analyze. We consider two approaches to building a concise representation, respecting the underlying structural relationships while hiding superfluous information: a pruning strategy based on the notion of concept stability and a representational improvement based on nested line diagrams and "zooming". We illustrate the methods on two examples: a community of embryologists and a community of researchers in complex systems. <s> BIB003 </s> Survey on Social Community Detection <s> From bipartite graphs to Galois hierarchies (C2) <s> In this paper we define and analyze stability of a formal concept. A stability index is based on the idea of a dependency in a dataset that can be reconstructed from different parts of the dataset. This idea, underlying various methods of estimating scientific hypotheses, is used here for estimating concept-based hypotheses. Combinatorial properties of stability indices, algorithmic comlpexity of their computation, as well as their dynamics with arrival of new examples are studied. <s> BIB004 </s> Survey on Social Community Detection <s> From bipartite graphs to Galois hierarchies (C2) <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> BIB005
This class extends another a step by attempting to extract communities while preserving knowledge shared in each community. No survey has described this type of method. The inputs are bipartite graphs, and the outputs a Galois hierarchy that reveals communities semantically defined with their common properties or shared knowledge. Communities are non-empty lattice extents, and the result is a hypergraph whose hyperedges are labeled by lattice intents (i.e. shared knowledge). However, a Galois hierarchy, which is roughly computed from the hypergraph input (as in the case of Freeman BIB001 ), is not a satisfactory scheme since a significant number of groups may be obtained. Under ideal conditions, reduction methods should be introduced, which at one level cause the loss of some semantic precision, yet on another level add precision, i.e. cohesion and reliability inside the extracted communities. Only very few authors have actually addressed this difficulty. Roth BIB002 found the epistemic communities described above before proposing to retain communities of significant size (extent) and semantics (intent), though with weak justification and validation for the proposed heuristics. The authors in BIB003 then proposed well-known Galois lattice reduction methods based on the so-called iceberg method as well as the stability method. The iceberg method from BIB005 identifies concepts with frequent intents above a set threshold. The authors however point out that some important concepts may be overlooked with this method. Stability methods, as used in BIB005 BIB004 , rely on concept stability. The fewer the number of extent subsets present in child concepts, the greater the concept stability. In  it is argued that combining both the iceberg and stability methods yields good results for extracting pertinent communities based on concepts. Two thresholds still need to be set however, as the algorithms computation time may be exponential in the number of objects and attributes (NP complete) and lastly the result presented in the form of a Galois lattice is not easily comprehensible.