Incremental Construction of Three-way Concept Lattice for Knowledge Discovery in Social Networks

Abstract

Three-way concept analysis (3WCA), a combination of three-way decision and formal concept analysis, is widely used in the field of knowledge discovery. Generally, constructing three-way concept lattices requires the original formal context and its complement context simultaneously. Additionally, the existing three-way concept lattice construction algorithms focus on the static formal context, and cannot cope with the dynamic formal context that is an essential representation in social networks. Toward this end, this paper pioneers a novel problem and method for the incremental construction of three-way concept lattice for knowledge discovery in social networks. Aiming to facilitate the construction efficiency, this paper firstly investigates the three-way concept lattice construction for attribute-incremental/object-incremental formal contexts, respectively. Then, the dynamic formal context of a social network can be viewed as a special formal context with both attribute-increment and object-increment. Further, we develop the AE/OE concept lattice incremental construction algorithms, called SNS-AE and SNS-OE. Extensive experiments are conducted on various formal contexts to evaluate the effectiveness of our incremental algorithms. The experimental results demonstrate that our proposed incremental algorithms can significantly decrease the construction time of three-way concept lattice compared to the non-incremental algorithm.