Network reconfiguration algorithm based on game theory and genetic algorithm

Abstract

The invention belongs to the technical field of a complicated network, and particularly discloses a network reconfiguration algorithm based on a game theory and a genetic algorithm. The algorithm comprises the main realization steps: firstly, as for a network with N nodes, A 0-1 matrixes are initialized randomly, and a game theory strategy is initialized; secondly, according to the known node actual earnings values, node earnings values of the A matrixes are calculated, and the total earnings value of each node is calculated; thirdly, a population is updated according to the genetic algorithm, and T generations are iterated to obtain A new matrixes; and finally, according to improvement on a reconfiguration algorithm on a compressed sensing network, the algorithm is used for reconstruction on a single node until the earnings values of all nodes are equal to the actual earnings values, and an actual network is obtained. Reconstruction of a network with many nodes and a large degree can be totally correct, and the time is excessively fast.

Description

technical field [0001] The invention belongs to the technical field of complex networks, relates to complex network reconstruction and data mining technology, in particular to a network reconstruction algorithm based on game and genetic algorithm. Background technique [0002] Complex network is a form of abstraction of complex systems in the real world. There are many complex networks of this type in the real world, such as friend relationship networks in social networks, power grids, the World Wide Web, neural networks in biological networks, and metabolism. network and so on. In the real-world network, we abstract the independent individuals in the system into nodes in the network, and abstract a relationship between individuals in the system that is formed naturally or artificially according to certain rules into edges between nodes. [0003] Since the publication of two articles on small-world networks and scale-free networks in "Nature" and "Science" in 1998 and 1999,...

AI Technical Summary

Problems solved by technology

[0005] In the past few years, the problem of network reconstruction has received more and more attention. Most of the existing algorithms are based on the compressed sensing algorithm, which uses the sparseness of the network to reconstruct the network with the compressed sensing model. For sparse network effects Very good, but at the same time, the disadvantage is the constraint of sparsity. For complex and non-sparse networks such as community networks, it cannot be reconstructed correctly, and the time complexity is very high. It is time-consuming to reconstruct large networks. There are shortcomings of the algorithm. This algorithm solves the shortcomings of the existing algorithms, is not constrained by sparsity, and greatly reduces the time complexity

Images