Research And Implementation Of Community Detection Algoritym Based On Data Mining

With the repaid development of information technology, the research about network community has become a hot topic. Community detection could help us better understand the network topology and network structures, which is of great importance. In recent years an algorithm named Label Propagation Algorithm (LPA) was proposed, which is simple and free of resolution limits, making it very popular in real large-scale sparse networks. LPA is one of the fastest community detection algorithms, but it is not perfect and still has some shortcomings. For example, there may be too large communities in the LPA result, which is called monster community problem. Besides, LPA is not designed for detecting overlapping communities and has poor capabilities of finding them. This paper proposes community detection algorithms based on LPA, trying to solve the monster community problem and improve the ability to detect overlapping communities.In order to solve the monster community problem, this paper proposes a new algorithm called Booming-LPA. Researches find that the booming phenomenon during label propagation in attenuated LPA is one of important reasons for the monster community problem. Based on the booming phenomenon, Booming-LPA terminates the algorithm iterations in time, which avoids the monster community problem and improves community results and the time complexity at the same time. Experiments show that the results of Booming-LPA are the sub communities of attenuated LPA and our algorithm has a high precision rate.Besides, this paper also proposes a new algorithm called AOLPA (Attenuated Overlapping LPA) to detect overlapping communities. By adding attenuation factors in the original algorithm named COPRA(Community Overlap Propagation Algorithm) we gain rapid convergence, and by reconstructing overlapping community detection model we fix the problem where some labels are erased too early, which improves the capacity of overlapping detection a lot. Experiments show that AOLPA gains great improvement in time and space complexity and can detect overlapping communities far better than original algorithms.