Concept analysis approach for graphs

Graphs possess the ability to model complex systems in the real world, leading to their widespread application in fields such as social network analysis and recommendation systems. However, one of the major challenges in processing graph data lies in the inherent structural complexity of graphs. Consequently, extracting meaningful structural information from graph data has become a significant area of research. Formal Concept Analysis provides a method for expressing and analyzing algebraic structures by constructing concept lattices, which can effectively uncover complex structures within data. This paper proposes a concept analysis approach for graph data, revealing the relationship between graph structures and their corresponding concepts. Initially, the paper focuses on the connected components of disconnected graphs, exploring their specific representations in their respective concept lattices, and demonstrating that each connected component corresponds to a connected equivalence class within its associated lattice. Subsequently, the paper investigates the correspondence between graph structures of connected components and their associated concepts, identifying the concepts corresponding to cliques and to non-clique connected subgraphs. The findings indicate that these graph structures can be reconstructed through their corresponding concepts, thereby transforming operations on graph structures into operations on concepts and offering a novel perspective on graph structure manipulation. Finally, the paper analyzes the correspondence between concepts in concept lattices and graph structures, revealing the rationale behind concept construction. The results show that the concepts are closely related to a special class of graph structures, namely maximal star-clique graphs.

Authors

• Mengyao Zhao
• Yanhui Zhai
• Deyu Li

Keywords

• Graph
• Formal concept analysis
• Concept lattice
• Connected component
• Star-clique graph