Centralities for Networks with Consumable Resources

Abstract

Identification of influential nodes is an important step in understanding and controlling the dynamics of information, traffic and spreading processes in networks. As a result, a number of centrality measures have been proposed and used across different application domains. At the heart of many of these measures, lies an assumption describing the manner in which traffic (of information, social actors, particles, etc.) flows through the network. For example, some measures only count shortest paths while others consider random walks. This paper considers a spreading process in which a resource necessary for transit is partially consumed along the way while being refilled at special nodes on the network. Examples include fuel consumption of vehicles together with refueling stations, information loss during dissemination with error correcting nodes, and consumption of ammunition of military troops while moving. We propose generalizations of the well-known measures of betweenness, random walk betweenness, and Katz centralities to take such a spreading process with consumable resources into account. In order to validate the results, experiments on real-world networks are carried out by developing simulations based on well-known models such as Susceptible-Infected-Recovered and congestion with respect to particle hopping from vehicular flow theory. The simulation-based models are shown to be highly correlated to the proposed centrality measures.

References in corpus (21)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Identification of influential spreaders in complex networks
• The Dynamics of Viral Marketing
• Breakdown of the Internet under intentional attack
• Dynamics of Rumor Spreading in Complex Networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Cascade control and defense in complex networks
• Efficient routing on complex networks
• Optimal network topologies for local search with congestion
• The power of a good idea: quantitative modeling of the spread of ideas from epidemiological models
• Particle hopping models and traffic flow theory
• Understanding Road Usage Patterns in Urban Areas
• Congestion and centrality in traffic flow on complex networks
• A measure of individual role in collective dynamics
• Lurking in Social Networks: Topology-based Analysis and Ranking Methods
• A Microscopic Model for Packet Transport in the Internet
• Epidemic centrality - is there an underestimated epidemic impact of network peripheral nodes?
• Utility Maximization Framework for Opportunistic Wireless Electric Vehicle Charging