Explaining and Visualizing Structural Knowledge in Bipartite Graphs

Bipartite graphs are an important model for the representation and analysis of relationships between two different types of entities. Datasets in this form are commonly found in many fields, such as social networks, biology, and economics. Formal concept analysis is a research approach that allows for the analysis of such bipartite graphs by clustering the data into so-called concepts and ordering those in a lattice structure.

In this thesis we propose multiple approaches for the extraction and visualization of structural knowledge from bipartite graphs. To this end, knowledge is presented as easily explainable substructures that appear in the dataset. We address the question, how to extract some of these substructures which provide insight into the information underlying the data. For this purpose, we consider several substructures such as contranominal scales and ordinal scales and provide algorithms on how to discover them. Furthermore, we tackle the visualization problem that is inherent to formal concept analysis. In formal concept analysis, the primary tool to visualize knowledge is the hierarchy of concepts which, even though it is unambiguously defined, can be represented by many different diagrams that entail the same information but are to a different degree readable. We provide two ways to compute human-readable drawings, one of them is inspired by techniques from graph drawing and the other is heavily related to the structural investigations that we performed before. Finally, we investigate the question, whether it is possible to embed formal concepts into a low-dimensional vector space to enhance tasks in formal concept analysis. Thereby, we present an algorithm for embedding formal concepts by learning the closure operator using a neural network architecture. This is inspired from the word2vec approach which was developed in the field of natural language processing. We demonstrate its potential in that regard as we are able to rediscover conceptual features in the computed embeddings.