Community discovery method based on node intimacy and label propagation

Abstract

The invention provides a community discovery method based on node intimacy and label propagation. The method belongs to the field of complex network analysis. The main technical feature of the methodcomprises the steps of estimating intimacy among adjacent nodes in a network through utilization of local topology information, and establishing an intimacy matrix based on the intimacy; estimating importance of the nodes in the network based on the intimacy matrix, and ensuring that the nodes are updated based on the importance in a descending order; in an iterative updating process, updating a label of each node as the label with the greatest influence in neighbors, and determining the unique label through calculation of the intimacy of the labels if a plurality of labels with the greatest influence exist; and when an algorithm satisfies a stop condition, jumping out of a label propagation process, and subjecting the nodes wit the same label to the same community. The method is reasonable in design; a high quality community can be rapidly detected; the robustness of the label propagation method can be effectively improved; and the method can be widely applied to fields such as protein function prediction, epidemic surveillance and electronic commerce precise recommendation.

Description

technical field [0001] The invention belongs to the field of complex network analysis, and in particular relates to a problem of community discovery based on a label propagation algorithm based on node intimacy. Background technique [0002] In the real world, many complex systems can be abstracted into network models, such as social networks (QQ, WeChat, Weibo, Facebook, Twitter, etc.), scientist citation networks, protein interaction networks, and the World Wide Web. In these networks, some statistical features such as "small world", "scale-free" and "community structure" do not exist in simple networks. Numerous studies have shown that individuals in complex networks are not connected randomly, but have heterogeneous characteristics, that is, nodes of the same type are closely connected, while nodes of different types are sparsely connected. This feature is called community structure, that is, nodes of the same type and the connections between them belong to the same com...

AI Technical Summary

Problems solved by technology

However, the disadvantage of the low robustness of the label propagation algorithm makes the quality of the solutions produced by executing the algorithm multiple times have large differences, and some solutions may even include the entire network, which is the so-called "monster community".

Images