Finding the proper node ranking method for complex networks

Abstract

Ranking node importance is crucial in understanding network structure and function on complex networks. Degree, h-index and coreness are widely used, but which one is more proper to a network associated with a dynamical process, e.g. SIR spreading process, is still unclear. To fill this gap, a, which is extracted from the fitting function (f(x)=1-1/(e^(2a(x-b))+1)) of the average number of nodes in each radius of the neighborhood of a node, is proposed. Experiment results which are carried out on twenty real-world networks show that a can classify which of the three measures (degree, h-index and coreness) is more proper to a network in ranking node importance. We also find that [b/3] is a good indicator for forecasting the optimal radius of the neighborhood of a node in ranking node importance for a given network. To the best of our knowledge, it is the first solution of this interesting and open issue. Furthermore, by extending the range of neighborhood where we construct an operator H on of a node, we propose a new method to quantify the importance of a node. The ranking accuracies of most networks can be improved when the radius is increased from 0 to its forecasting optimal radius and the improvement, for the best case, reaches up to 111%. The performances will reduce on half of the networks studied in this paper if we roughly extend the radius of the neighborhood. Our work deepens the understanding of how to find out the proper node ranking method for complex networks. The proposed methods bridge the gaps among network structure and node importance, and may have potential applications in controlling the outbreak of disease, designing of optimal information spreading strategies.

16 pages, 5 figures

References in corpus (27)

• Emergence of scaling in random networks
• An index to quantify an individual's scientific research output
• Epidemic spreading in scale-free networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Random graphs with arbitrary degree distributions and their applications
• Identification of influential spreaders in complex networks
• Resilience of the Internet to random breakdowns
• The Dynamics of Viral Marketing
• Attack vulnerability of complex networks
• Structural Vulnerability of the North American Power Grid
• Immunization of complex networks
• Influence maximization in complex networks through optimal percolation
• Does the h-index have predictive power?
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Ranking spreaders by decomposing complex networks
• Identifying influential spreaders in complex networks based on gravity formula
• Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
• Ranking the spreading influence in complex networks
• Spreading dynamics in complex networks
• A measure of individual role in collective dynamics
• Identify influential spreaders in complex networks, the role of neighborhood
• Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
• Leveraging local h-index to identify and rank influential spreaders in networks
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Weighted H-index for identifying influential spreaders
• Faster all-pairs shortest paths via circuit complexity