An Overlapping Community Detection Algorithm Based On Formal Concept Analysis

Community detection has developed rapidly in recent years as an important part of complex network research. Detecting communities in complex network can not only help us understand the organizational structure of the network, but also can dig out a lot of hidden information. By studying the representative papers in this area appeared in recent years, in this paper, we proposed an overlapping community detection algorithm based on formal concept analysis which can not only identify the overlapping communities, but also can show the inner core community and its hierarchical relationships.This paper mainly studies the following aspects:(1) First of all, we introduces the situation of the complex network and the community detection, then analysis and compares the definition of community, existing community detection algorithms, especially the overlapping community detection algorithms.(2) On the basis of sociological theory, we put forwad that the smallest unit which can influence the community is the core community, and then we introduce the FCA method to identify the core community, make the edge’s end as the property of the start, and study the concept collection of start points.(3) According to the characteristics of the the network’s formal background, we proposed a concept lattice generation algorithm based on the matrix operation to identify the core community, and describe the core community’s level and interactive relationship by Hasse diagram. The algorithm in our paper has lower complexity.(4) We put forward an overlapping community detection algorithm based on FCA. First, design the concept’s similarity model to measure the connectivity between core communities, then hierarchical clustering the concepts, merge the core of the community, in the end, we get the larger community and the overlapping node.(5) The application of overlapping community detection algorithm in the author’s domain division is proposed. First of all, construct the author coordination network according to DBLP data set, get the author cooperation network division and analysis its actual significance. And then put forward the concept of the scientific research team, through the research of the core community and the overlapping community to reveal the evolution of scientific research team. On this basis, the superiority of algorithm applying in DBLP the author’s domain division was introduced.