Complex Network Node Covering Method Based on Snowdrift Game Evolution

Abstract

The invention discloses a snowdrift game evolution based complex network node covering method, which mainly solves a problem that complex network minimum node coverage cannot be accurately calculated in the prior art. The implementation comprises the steps of (1) setting the population size S and an algebra G, and randomly generating S individuals to form a parent population; (2) randomly selecting two individuals from the parent population to carry out crossover and mutation so as to acquire four quasi-offspring individuals, respectively carrying out memoryless snowdrift gaming on the four quasi-offspring individuals, and selecting two quasi-offspring individuals with a small evaluation function value from the four quasi-offspring individuals to act as new individuals; (3) repeating the step (2) until S new individuals are generated so as to act as a new parent population, thereby completing one time of population regeneration; and (4) repeating the steps (2)-(3) on the basis of the new parent population so as to complete G times of population regeneration, and using the individual with the minimum evaluation function value in a final population to act as a minimum node coverage result. The method disclosed by the invention can solve the minimum node coverage result of a complex network, and can be applied to distribution planning and network optimization.

Description

technical field [0001] The invention belongs to the field of network technology, and in particular relates to a node coverage method of a complex network, which can be used for distribution planning and network optimization, such as the selection of the optimal installation position of monitoring equipment in the urban road network, and the selection of key points according to the interpersonal relationship network when placing advertisements object. Background technique [0002] Complex network is a form of abstraction of complex systems in the real world. There are many such complex networks in the real world, such as friend relationship networks in social networks, power grids, the World Wide Web, neural networks in biological networks, and metabolic networks, etc. . The independent individuals in the real world system are abstracted into nodes in the network, and a relationship between individuals in the system that is naturally formed or artificially constructed accord...

AI Technical Summary

Problems solved by technology

Due to the connectivity characteristics of the network, the deviation of the local results will cause a chain reaction, causing the overall solution to fall into a local optimum, and the update process of the MBR algorithm is unable to avoid this bad situation, so the minimum coverage result is often not obtained in the end.

Images