Galois lattices

From InterSciWiki
Jump to: navigation, search

Anne Berry

Anne Berry, Romain Pogorelcnik. 2010. A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph. Inf. Process. Lett. 111(11): 508-511.

Anne Berry, Romain Pogorelcnik, Alain Sigaret. 2011. Vertical decomposition of a lattice using clique separators. Concept Lattices and their Applications

Formal Concept Analysis

Rudolf Wille. 2009. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts. ICFCA 2009: 314-339


Lattice theory today reflects the general Status of current mathematics: there is a rich production of theoretical concepts, results, and developments, many of which are reached by elaborate mental gymnastics; on the other hand, the connections of the theory to its surroundings are getting weaker and weaker, with the result that the theory and even many of its parts become more isolated. Restructuring lattice theory is an attempt to reinvigorate connections with our general culture by interpreting the theory as concretely as possible, and in this way to promote better communication between lattice theorists and potential users of lattice theory.

Vicky Choi, Yang Huaang, 2006. Faster Algorithms for Constructing a Galois Lattice, Enumerating enumerating all maximal bipartite cliques (of a bipartite graph)

Active Bibliography

Freeman, Linton C. 1996. Cliques, Galois lattices, and the Structure of Human Social Groups. Connections, 19:39-42.

Freeman, Linton C. 1996. Cliques, Galois lattices, and the Structure of Human Social Groups. Social Networks Volume 18(3): 173–187.

Linton C. Freeman & Douglas R. White. 1993. Using Galois lattices to represent network data. Sociological Methodology 1993 (23):127-146.

Falzon, Lucia. 2000. Determining groups from the clique structure in large social networks. Social Networks 22(2): 159-172.

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 wFreeman, L.C., 1996. Cliques, Galois lattices, and the structure of human social groups, Social Networks 18, 173–187.x 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.


 author = { Gerd Stumme and Rafik Taouil and Yves Bastide and Nicolas Pasquier

and Lotfi Lakhal},

 title = {Computing iceberg concept lattices with TITANIC},
 journal = {Data \& Knowledge Engineering},
 year = {2002},
 volume = {42},
 pages = {189--222},
 number = {2},
 abstract = {The paper shows how iceberg concept lattices can be used as a condensed

method to represent and visualize frequent (closed) itemsets. Iceberg concept lattices only show the top-most part of a concept lattices (known from Formal Concept Analysis). To compute iceberg concept lattices the algorithm TITANIC is presented which computes closed sets (a closure system) in a level-wise approach using weights (e.g., support), equivalence classes and key sets (minimal sets in an equivalence class). TITANIC is compared experimentally to Next-Closure and performs better. PASCAL (Bastide et al. 2000) is a modified version of TITANIC to mine all frequent itemsets. },

 category = {theory}