| Network(graph)is a basic form of describing data.The nodes in the network represent an entity,and the edges in the network represent the relationships between entities.Analyzing the structure of complex networks has always been a hot issue in academia,and community detection is one of them.In order to detect communities which with little internal connections and sparse external connections in complex networks,predecessors have made many useful contributions.On the one hand,various community detection algorithms,such as label propagation algorithm,have been proposed for networks of different sizes and characteristics;On the other hand,the industry has developed many convenient tools for large data scales,the most famous of which is Google’s "Troika".The distributed computing model Hadoop has bred the second generation of streaming computing engine Spark and the third generation of streaming computing engine Flink after years of iteration.Because Spark started early,most engineering practices in the past were based on Spark platform,and many only used batch processing api.How to better combine the traditional community detection algorithm with the features of Flink distributed computing is the focus of this paper.Therefore,on the basis of the traditional label propagation algorithm,this paper proposes an overlapping community discovery algorithm based on Flink Gelly-Master LPA.The work of this paper can be summarized as follows:1.In the core nodes selection stage,the concepts of Loacl Clique Ratio and Degree Factor are proposed,which can evaluate the possibility of nodes being in the community center based on the local community information of nodes,and then introduce the Vote mechanism to allow nodes to independently select the initial core node of label transmission in dynamic propagation,so as to avoid the close distance between the two core nodes and improve the division quality,Finally,the core node synchronizes its own label to the node group based on the maximization of domain compactness.2.In the overlapping community detection stage,firstly,based on the Loacl Clique Ratio and the distribution characteristics of the core nodes selected in the previous section,a Node Jurisdiction and a new belonging coefficient calculation method are proposed.The former evaluates the possibility of two nodes belonging to the same community,and the latter compensates the label selection process based on the common neighbor information to make the label selection more reasonable.Secondly,based on the idea of Tukey Method,a dynamic filtering strategy is proposed to help each node select appropriate labels and classify labels to improve the quality of label filtering.3.In the community border optimization stage,inspired by Palla G and others’ research on n-clique structure in complex networks and the idea of gain degree,the calculation method of Triangular Gain was proposed,and a propagative community border optimization algorithm was proposed based on the Flink computing model.Nodes can optimize their own stored labels in order according to their own location,reducing the unreasonable division caused by the update order.4.The algorithm program described above is written using the Flink Gelly distributed graph computing model.The Flink cluster is built on three computing nodes,on which the comparative experiments of four LPA algorithms in multiple data sets are carried out,and the algorithm evaluation indicators are recorded and charts are drawn.From the experimental results,it can be seen that the Master LPA algorithm has good stability and accuracy. |
