Estimating the number of covering relations in a formal concept lattice

Date
2015-01-01
Authors
Rodriguez, Aaron
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

Given data organized in a tabular form called a cross table, the multi-dimensional relationships in the data are represented by a directed acyclic graph called a formal concept lattice. For large sets of data, drawing the graph is not reasonable. We focus on quantitative characteristics of the lattice structure that lead to decreased computation time in the determination of nodes and edge sets on large lattices from big data.

This work addresses the problem of recovering the covering relations, of a concept lattice, given the set of nodes. We implement one existing algorithm and formally prove that it correctly computes the covering relations of a given concept lattice from its nodes. We also discuss methods for estimating the number of covering relations in a lattice and offer a conjecture for an upper bound for this number. We present experimental results to predict edge frequency distribution for a range of cross table densities. Finally we discuss some open problems.

Description
Keywords
Applied Mathematics, complete lattices, concept lattices, cover relations, FCA, Formal Concept Analysis, posets
Citation