Study Of The Topological Index Of Graphs And Its Applications On Complex Networks

The node centrality of complex networks identifies the importance of complex network nodes.The topological indices of graphs are graph invariants,which can express some properties of graphs well.The node centrality constructed by the topological indices of the graph can reflect the overall characteristics of the complex network,and can identify the node importance of the complex networks very well.We first study the topological indices of several types of complex graphs.The original graphs are graph G1 with order n1 and m1 edges and graph G2 with order n2,and m2,edges.Complex graphs include:the subdivision-vertex corona graph-S,(G1)OG2,which is constructed by subdivision graph S(G1)of graph G1 and n1 copies of graph G2.The subdivision-edge corona graph S(G1)?G2,which is constructed by subdivision graph S(G1)of the graph G1 and m1 copies of graph G2.The subdivision-vertex join graph G1*G2,which is constructed by subdivision graph S(G1)of the graph G1 and subdivision graph S(G2)of the graph G2,obtained by connecting all the original vertices of graph G1 and the original vertices of graph G2.The subdivision-edge join graph G1(?)G2,which is constructed by subdivision graph S(G1)of the graph G1 and subdivision graph S(G2)of the graph G2,obtained by connecting all the newly added vertices of graph S(G1)and the newly added vertices of graph S(G2).The subdivision-vertex-edge join graph G1(?)G2,which is constructed by subdivision graph S(G1)of the graph G1 and subdivision graph S(G2)of the graph G2,obtained by connecting all the original vertices of graph S(G1)and the newly added vertices of graph S(G2).The first Zagreb index,the second Zagreb index,the Hyper-Zagreb index,and the F index of these complex graphs are calculated by the correlation properties of these graphs.Existing complex networks are often subject to random attacks and deliberate attacks,resulting in reduced reliability of complex networks.How to find important nodes and protect them in order to improve reliability of complex network is an important issue of complex network research.Some topological indices of the graph,such as graph entropy,the first Zagreb index,the second Zagreb index,the Hyper-Zagreb index and the F index,are closely related to the centrality of the nodes in the network.And the graph entropy can be represented by Zagreb index.According to the graph entropy,combined with betweenness centrality and degree centrality we propose a new attack strategy,named betweenness and degree entropy(BDE),to identify the importance of complex network nodes.The experiments evaluate the efficiency of attack strategies on three standard network models and three real networks through static attacks and dynamic attacks respectively.By comparison,the betweenness and degree entropy is more efficient than the traditional attack strategy.The main results of this paper are as follows:(1)The degree distribution of the sub division-vertex corona graph S,(G1)(?)G2,the subdivision-edge corona graph S(G1)(?)G2,the subdivision-vertex join graph G1*G2,the subdivision-edge join graph G1(?)G2 and the subdivision-vertex-edge join graph G1(?)G2 are given,and the first Zagreb index and the second Zagreb index of these complex graphs are calculated.(2)The Hyper-Zagreb index and the F index of the sub division-vertex corona graph S(G1)(?)G2,the subdivision-edge corona graph S(G1)(?)G2,the subdivision-vertex j oin graph G1*G2,the subdivision-edge j oin graph G1(?)G2 and the subdivision-vertex-edge j oin graph G1(?)G2 are calculated.(3)A new attack strategy based on graph entropy and degree centrality and betweenness centrality is proposed.Taking three standard network models and three real networks for consideration,the relative size of the largest connected subgraph is selected as the network invulnerability evaluation index.By comparing invulnerability index of the six network models in five different attack strategies and two different attack modes(static attacks and dynamic attacks),we analyze the destructiveness of the newly proposed attack strategy(betweenness and degree entropy)and the traditional attack strategy on the network.In the experiment,when calculating the relative size of the largest connected subgraphs,each attack strategy selects 20 nodes at a time,and we compare the relative size changes of the maximum connected subgraphs of the six network models in the removal process.In order to analyze the attack efficiency of the five attack strategies.Experimental results show that the newly defined betweenness and degree entropy is more efficient than the traditional attack strategy.Attacking a network with a dynamic attack is more efficient than a static attack,but the attack of a dynamic attack is more expensive.The newly proposed betweenness and degree entropy can identify the importance of nodes very well in the network.