Optimal Intervention on Weighted Networks via Edge Centrality

arXiv2303.09086MaRDI QIDQ6429760

Author name not available (Why is that?)

Publication date: 16 March 2023

Abstract: Suppose there is a spreading process such as an infectious disease propagating on a graph. How would we reduce the number of affected nodes in the spreading process? This question appears in recent studies about implementing mobility interventions on mobility networks (Chang et al. (2021)). A practical algorithm to reduce infections on unweighted graphs is to remove edges with the highest edge centrality score (Tong et al. (2012)), which is the product of two adjacent nodes' eigenscores. However, mobility networks have weighted edges; Thus, an intervention measure would involve edge-weight reduction besides edge removal. Motivated by this example, we revisit the problem of minimizing top eigenvalue(s) on weighted graphs by decreasing edge weights up to a fixed budget. We observe that the edge centrality score of Tong et al. (2012) is equal to the gradient of the largest eigenvalue of $W{W}^{op}$, where $W$ denotes the weight matrix of the graph. We then present generalized edge centrality scores as the gradient of the sum of the largest $r$ eigenvalues of $W{W}^{op}$. With this generalization, we design an iterative algorithm to find the optimal edge-weight reduction to shrink the largest $r$ eigenvalues of $W{W}^{op}$ under a given edge-weight reduction budget. We also extend our algorithm and its guarantee to time-varying graphs, whose weights evolve over time. We perform a detailed empirical study to validate our approach. Our algorithm significantly reduces the number of infections compared with existing methods on eleven weighted networks. Further, we illustrate several properties of our algorithm, including the benefit of choosing the rank $r$, fast convergence to global optimum, and an almost linear runtime per iteration.

Has companion code repository: https://github.com/neu-statsml-research/designing-intervention-on-mobility-networks

This page was built for publication: Optimal Intervention on Weighted Networks via Edge Centrality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429760)