Important Node Identification In The Complex Networks And Its Application In Evidence Theory

As a new branch of physics,complex network has attracted the attention of many domestic and abroad scholars with the rise of the Internet and the explosive growth of data.Complex network is an interdisciplinary applied subject based on graph theory,which has a long research history up to now.In 1988,the discovery of the small-world property raised the attention to complex networks to a new level,and the discovery of the scale-free property had a profound impact on it.Unlike random or artificial networks,the non-homogeneity of networks in the real world determines that the importance of the physical objects represented behind the nodes is not equally distributed.The influential nodes accounts for only a few,most belong to the trivial nodes,and it can be seen as a complex network of Matthew effect,quickly find out this type of node for a lot of practical problems have great significance.Information fusion is a technology that makes use of multi-source information to get a more objective and essential understanding of the tar-get.Driven by military applications,information fusion is developing rapidly,not only in traditional military fields,but also in civil fields such as fault diagnosis and indoor posi-tioning.Dempster put forward evidence theory in 1967,and then Shafer further promoted the theory of reasoning against uncertainty,so it is also known as Dempster-Shafer evi-dence theory.It differs from traditional Bayesian probability theory in that it allows for more vague expressions and has the ability to express uncertainty.At the same time,it has been widely used in expert decision system because of its decision attribute of direct reasoning type.Therefore,the contribution of this paper mainly focuses on the influence node mining in complex networks and the complex network modeling of evidence theory.The work of this paper can be summarized as follows:(1)The identification of influential nodes in complex networks has been a topic of immense interest.The local approach represented by degree centrality performs well on most graphs,but does not work well when dealing with bridge nodes.In order to solve the problem of being trapped in locality,many scholars have put forth different solutions.Gravity models are a popular research direction,but the current gravity models have to traverse the shortest distance between all nodes,which makes them difficult to run over large graphs.In this paper,we propose a random walk based gravity model to identify influential spreaders.This model require O(|N|*?*^l_k(l-k))of time complexity to sample walks but reduce space complexity of O(|N|²)to O(<K>²|N|)and time complexity of calculating the shortest path from O(|N|²)to O(1),where<K>²?|N|and?*^l_k(l-k)?|N|.Moreover,some random walk properties are investigated to support our model.To demonstrate the feasibility,we define an error rate and test their spreading ability and convergence speed under different random walk strategies.Experimental results show that our method can achieve the better effect than the most existing gravity models.(2)Complex network model of evidence theory:Because of the advantages of graphs in visualizing the relationship between individuals,complex networks have been widely used and greatly developed.In real-world applications of Dempster-Shafer evidence the-ory,there are usually thousands of sensors collecting information.It is easy to be over-whelmed by the mass of information and ignore the connections between them.The rise of the semi-supervised learning method Graph Convolutional Network(GCN)makes it possible to address this issue.Inspired by complex network,the basic probability assign-ment function(BPA),the basic function of evidence theory,is modeled in a novel form of the network graph.Some typical issues of evidence theory,such as conflicting evidence,multi-class evidence clustering,and computational complexity for large-scale fusion are systematically addressed in the framework of the proposed network model.What's more,a new combination rule is presented from the point view of the graph.The empirical re-sults of experiments on real data set demonstrate the potential and feasibility of complex networks in traditional evidence theory.