skip to main content


Title: 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 with the proposed centrality measures. Reproducibility: Our code and experiments are available at https://github.com/hmwesigwa/soc_centrality  more » « less
Award ID(s):
1647361
NSF-PAR ID:
10125785
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Network Science
Volume:
7
Issue:
3
ISSN:
2050-1242
Page Range / eLocation ID:
376 to 401
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In this paper we evaluate the effect of noise on community scoring and centrality-based parameters with respect to two different aspects of network analysis: (i) sensitivity, that is how the parameter value changes as edges are removed and (ii) reliability in the context of message spreading, that is how the time taken to broadcast a message changes as edges are removed. Our experiments on synthetic and real-world networks and three different noise models demonstrate that for both the aspects over all networks and all noise models, permanence qualifies as the most effective metric. For the sensitivity experiments closeness centrality is a close second. For the message spreading experiments, closeness and betweenness centrality based initiator selection closely competes with permanence. This is because permanence has a dual characteristic where the cumulative permanence over all vertices is sensitive to noise but the ids of the top-rank vertices, which are used to find seeds during message spreading remain relatively stable under noise. 
    more » « less
  2. Althouse, Benjamin Muir (Ed.)
    Disease epidemic outbreaks on human metapopulation networks are often driven by a small number of superspreader nodes, which are primarily responsible for spreading the disease throughout the network. Superspreader nodes typically are characterized either by their locations within the network, by their degree of connectivity and centrality, or by their habitat suitability for the disease, described by their reproduction number ( R ). Here we introduce a model that considers simultaneously the effects of network properties and R on superspreaders, as opposed to previous research which considered each factor separately. This type of model is applicable to diseases for which habitat suitability varies by climate or land cover, and for direct transmitted diseases for which population density and mitigation practices influences R . We present analytical models that quantify the superspreader capacity of a population node by two measures: probability-dependent superspreader capacity, the expected number of neighboring nodes to which the node in consideration will randomly spread the disease per epidemic generation, and time-dependent superspreader capacity, the rate at which the node spreads the disease to each of its neighbors. We validate our analytical models with a Monte Carlo analysis of repeated stochastic Susceptible-Infected-Recovered (SIR) simulations on randomly generated human population networks, and we use a random forest statistical model to relate superspreader risk to connectivity, R , centrality, clustering, and diffusion. We demonstrate that either degree of connectivity or R above a certain threshold are sufficient conditions for a node to have a moderate superspreader risk factor, but both are necessary for a node to have a high-risk factor. The statistical model presented in this article can be used to predict the location of superspreader events in future epidemics, and to predict the effectiveness of mitigation strategies that seek to reduce the value of R , alter host movements, or both. 
    more » « less
  3. Objective: Inferring causal or effective connectivity between measured timeseries is crucial to understanding directed interactions in complex systems. This task is especially challenging in the brain as the underlying dynamics are not well-understood. This paper aims to introduce a novel causality measure called frequency-domain convergent cross-mapping (FDCCM) that utilizes frequency-domain dynamics through nonlinear state-space reconstruction. Method: Using synthesized chaotic timeseries, we investigate general applicability of FDCCM at different causal strengths and noise levels. We also apply our method on two resting-state Parkinson's datasets with 31 and 54 subjects, respectively. To this end, we construct causal networks, extract network features, and perform machine learning analysis to distinguish Parkinson's disease patients (PD) from age and gender-matched healthy controls (HC). Specifically, we use the FDCCM networks to compute the betweenness centrality of the network nodes, which act as features for the classification models. Result: The analysis on simulated data showed that FDCCM is resilient to additive Gaussian noise, making it suitable for real-world applications. Our proposed method also decodes scalp-EEG signals to classify the PD and HC groups with approximately 97% leave-one-subject-out cross-validation accuracy. We compared decoders from six cortical regions to find that features derived from the left temporal lobe lead to a higher classification accuracy of 84.5% compared to other regions. Moreover, when the classifier trained using FDCCM networks from one dataset was tested on an independent out-of-sample dataset, it attained an accuracy of 84%. This accuracy is significantly higher than correlational networks (45.2%) and CCM networks (54.84%). Significance: These findings suggest that our spectral-based causality measure can improve classification performance and reveal useful network biomarkers of Parkinson's disease. 
    more » « less
  4. Abstract Group work is often a critical component of how we ask students to interact while learning in active and interactive environments. A common-sense extension of this feature is the inclusion of group assessments. Moreover, one of the key scientific practices is the development of collaborative working relationships. As instructors, we should be cognizant of our classes’ development in the social crucible of our classroom, along with their development of cognitive and/or problem solving skills. We analyze group exam network data from a two-class introductory physics sequence. In each class, on each of four exams, students took an individual version of the exam and then reworked the exam with classmates. Students recorded their collaborators, and these reports are used to build directed networks. We compare global network measures and node centrality distributions between exams in each semester and contrast these trends between semesters. The networks are partitioned using positional analysis, which blocks nodes by similarities in linking behavior, and by edge betweenness community detection, which groups densely connected nodes. By calculating the block structure for each exam and mapping over time, it is possible to see a stabilizing social structure in the two-class sequence. Comparing global and node-level measures suggests that the period from the first to second exam disrupts network structure, even when the blocks are relatively stable. 
    more » « less
  5. The use of network models to study the spread of infectious diseases is gaining increasing interests. They allow the flexibility to represent epidemic systems as networks of components with complex and interconnected structures. However, most of previous studies are based on networks of individuals as nodes and their social relationships (e.g., friendship, workplace connections) as links during the virus spread process. Notably, the transmission and spread of infectious viruses are more pertinent to human dynamics (e.g., their movements and interactions with others) in the spatial environment. This paper presents a novel network-based simulation model of human traffic and virus spread in community networks. We represent spatial points of interests (POI) as nodes where human subjects interact and perform activities, while edges connect these POIs to form a community network. Specifically, we derive the spatial network from the geographical information systems (GIS) data to provide a detailed representation of the underlying community network, on which human subjects perform activities and form traffics that impact the process of virus transmission and spread. The proposed framework is evaluated and validated in a community of university campus. Experimental results showed that the proposed simulation model is capable of describing interactive human activities at an individual level, as well as capturing the spread dynamics of infectious diseases. This framework can be extended to a wide variety of infectious diseases and shows strong potentials to aid the design of intervention policies for epidemic control. 
    more » « less