Physarum Polycephalum Inspired Algorithm For Node Centrality In Complex Networks

Over the years, the study of graphs and complex networks has drawn increasing attention in a wide variety of scientific disciplines, such as physics, chemistry, computer science, mathematics, biology and economics. And relevant researches are gradually transferring from single discipline to multidisciplinary. Meanwhile, network analysis, as a key tool to map and measure those network entities and their connections, has been well studied to provide a visual and mathematical view of networks. Due to the complexity of complex network itself, it is of great application value for the fields, such as sociology, medicine, information technology, economic management and so on, to determine the status of each node in network and identify those nodes which are more central and outstanding, according to topology and relevant information of the nodes in the network. However, as the understanding and preference of the concept of node centrality is different, there is no uniform approach for assessing node centrality so far. What’s more, based on the search results of current studies on node centrality in networks, it is shown that no bio-inspired solution for this problem has ever been proposed yet. According to recent study, it is found that a single cell organism, called Physarum polycephalum, shows its amazing intelligence in network design, analysis and optimization. In biology experiments, the foraging tube network connecting each food sources that Physarum forms, is comparable to real-world Tokyo rail network in cost, efficiency and fault tolerance. Thus, a new idea for assessing node centrality in complex networks has been proposed in this paper, which is based on the network optimizing mechanisms of Physarum.This paper firstly studies the intelligent behavior of Physarum shows in its foraging network and reproduces the existing path finding model. During the process of experimental verificaiton of this model, some shortcomings have been found. Aiming at each shortcoming, corresponding improvements are then provided. After that, combining with the application background of assessing node centrality in complex networks, three different algorithms based on the improved bio-inspired algorithm have been proposed.The main work of this paper has been summarized as follows:1. Study of rapid optimization mechanismAs the existing path finding model of Physarum has the problem of redundant computation, the implementing process of the model is observed carefully. And then, heuristic rule for rapid optimization has been extracted to develop the rapid Physarum algorithm (RPA). This method has reduced the redundant computation to some extent and improved the efficiency of the algorithm.2. Extend of application in directed networksAs the existing model can’t be used in directed networks, the similarity in basic theory of existing model and circuit system, and the ability of diodes in circuit system in handling directions have been taken into consideration. By adopting the direction control ability of diodes and integrating a module of analog circuit analysis, our directed Physarum algorithm (DPA) has been proposed in this paper.3. Proposing of Physarum algorithm for the shortest path(PASP)After DPA integrates the module of analog circuit analysis, the whole procedure of the algorithm is a little more complex. By analyzing the inner mechanism of this module further, an effective substitute method has been developed to improve the algorithm. With the help of this method, the Physarum algorithm for the shortest path (PASP) has been proposed, which is suitable in both directed and undirected networks.4. Proposing of primary assessing algorithm based on PASPBased on constructing the corresponding relationship between complex network and Physarum’s tube network, a primary assessing metric based on PASP, Cp, has been proposed by combing the background of node centrality assessment. This metric not only considers the influence of the shortest path has on centrality, but also includes the contribution of shorter paths.5. Proposing of improved assessing algorithm based on PASPDue to high computation complexity of the primary assessing algorithm, as the scale of the problem increases, this algorithm is no longer suitable. Thus, by adopting the idea of ground node in LeaderRank algorithm, an improved assessing metric, CIP, has been developed, which leads to the computation complexity of outer loop reducing from O(n2) to O(n) and efficiency improvements.6. Proposing of PhysarumSpreader algorithm Based on the LeaderRank algorithm designed for binary networks, the network optimizing mechanisms of Physarum is combined to develop our PhysarumSpreader algorithm, which is applicable in weighted networks. After that, a weighted SI model has been adopted in our paper, whose experimental results have shown that the nodes with higher node centrality value given by our PhysarumSpreader algorithm, have better performance in information spreading.