Research On Measurement Methods Of Node Importance Based On Graph Energy

The measuring of vertex centrality,which determines the importance of vertices in a network,has been one of key issues in network analysis.Important vertices in complex networks,often play important roles in the structure and function of networks.Therefore,identifying the key vertices is crucial in the networks,which has a wide range of practical application value,such as controlling the outbreak of epidemics,conducting success-ful advertisements for e-commercial products,predicting epidemic scientific publications,prevention of catastrophic outages in power grids or the Inter-net and so on.For unweighted networks,many classical methods have been presented,such as degree,closeness,betweenness centrality,PageRank and Coreness etc..Graph energy is a measurement of determining the structural informa-tion content of graphs,which has been widely used in many fields,including biology,chemistry,and sociology.Graph energy also can be used to measure the vertex importance,i.e.,the importance of a vertex is equivalent to the change of graph energy caused by its removal.In this paper,two new vertex importance measurement algorithms are introduced based on the concept of graph energy.The first method is called Quasi-Laplacian centrality.A new kind of graph energy will be introduced based on quasi-Laplacian matrix-Quasi-Laplacian energy,and a new vertex centricity measurement based on this energy-Quasi-Laplacian centricity,will be proposed.Our main idea is that the importance(centrality)of a vertex v is reflected by the drop of the Quasi-Laplacian energy responding to the deletion of the vertex v from the network.Furthermore,we prove that the Quasi-Laplacian energy of a network G is related not only to the number of edges in the original network G but also to the number of edges in its corresponding linear graph L(G).Thus,the new presented Quasi-Laplacian centrality of a vertex v considers not only its position in the original graph G,but also its position in the line graph L(G).We further investigate the validness and robustness of this new centrality measure by applying this method to 3 classical social network data sets and 14 other data sets from various domains.And all obtain reliable and even better results by using the common-used SIR evaluation model.which provide strong evidences of the new measure's utility.The second method is called hyper-Zagreb centrality.Since hyper-Zagreb index is often used to describe the energy relationships between molecules,we extend this index to the field of graph energy and propose a new mea-surement method of vertex centrality-hyper-Zagreb centrality.Besides,we apply it to measure the vertex importanceWe find that the hyper-Zagreb centrality of vertex v is not only related to its own degree and the degree of its neighborsbut also related to its neighbors' neighbors.The centrality is also tested on real networks to verify its effectiveness.Specifically,Quasi-Laplacian and hyper-Zagreb centrality have direct relation to the parameters of the graph,so the calculations are relatively convenient.In particular,Quasi-Laplacian centrality has lower time com-plexity than other methods(except degree centrality),thus can be applied to large networks.