Distributed K-Core Algorithm Accelerates Solving Maximum Clique Problem And Its Application In Financial Social Network

With the continuous improvement and popularization of Internet technologies,more and more users have joined the social networking platform,thus forming a large-scale social network.It is very valuable to analyze and mine the information hidden in social networks.A maximal clique is the most closely related structure in a social network,so analyzing social networks through the maximal clique is a very effective way.Maximal Clique Problem(MCP)is a classic NP-complete problem,which has been widely used in real life.This paper studies the K-Core algorithm,which can be used to obtain a maximum approximate clique by iterative pruning.The resulting maximum approximate clique may contain a maximal clique.Therefore,this paper proposes a combined strategy,where the K-Core algorithm is first used to produce a maximum approximate clique,and the branch-and-bound method is then used to obtain a maximal clique in the shrunk graph.And in order to deal with the social network with massive data,this paper implements a distributed K-Core algorithm by using the Spark distributed memory framework.The main contents of this dissertation are as follows:1.By combining the K-Core algorithm with the branch-and-bound algorithm,it has been proved through experiments that the algorithm can speed up the efficiency of the branch-and-bound algorithm to search for the largest cluster.2.Combining the K-Core algorithm with the Spark distributed computing framework,the distributed K-Core algorithm is designed and implemented,and the feasibility of the algorithm is proved through experiments.3,the algorithm is applied to the real large-scale financial social network-BoardEx.Excavating the maximal clique by the combination algorithm in BoardEx and analyzing the position information,we found that the proportion of posts in this reduced image is similar to that of the original social network,indicating that the maximal clique acquired can represent the BoardEx social network to some extent.Perform data analysis of certain features.