Networked Dynamics

Systems of networked dynamics are used to model and analyze a variety of complex phenomena. Not only do linear networked dynamics define classical numerical physics simulations [8], but they are also used to analyze how opinions change among populations [5], and the ways epidemics spread [6,7], among many others. The analysis methods for these networks are almost as varying as their applications. In the case of opinion dynamics, one may be interested in the steady-state solutions of those opinions. That is, given enough time, what will the “spread” of opinions look like among the population? Alternatively, when analyzing an epidemic, we may want to predict when the disease will reach a certain country. Related to this problem, we may be interested to know how changing the network affects this timeline, or how network control [9,10] may be utilized. Because of its breadth, networked dynamics can easily swallow a researchers entire career. As someone who has not solely studied networked dynamics, we will only talk about two small sub-problems, being steady-state computation, and network control.

The computation of steady-states is of fundamental importance in physics, and closely related to the study of elliptic partial differential equations such as Poisson’s equation. As stated earlier, a social scientist studying computational opinion dynamics may also care about the steady-state. In both cases this can be extremely expensive to compute. Consider a social network with one million nodes (n), and ten times as many edges (m). In this case, evolving each time step of our networked dynamics requires O(m) operations. These computations then need to be repeated thousands, or millions of times. For bigger graphs and networks, this becomes incredibly expensive, especially because distributed implementations require moving data around between each time step.

How might we compute steady-state solutions faster? One answer is by using mean-field approximations. The idea here reasonably simple. Before breaking up our network for distributed computation, we first approximate how each section will behave. Then, instead of transferring data between each time step, we can just approximate the contribution from outside influences. This was explored in C. Jiang et. al. (2020) [1] in the context of networks with imperfect information. The same year I worked with many of the same authors to use this idea in the context of parallel and distributed computing. This was submitted as Parallel computation of fixed points on networks of nonlinear ODE [2]. This was a workshop submission, so it is very brief, but we found that this initial mean-field approximation method yields error in the single digits of percent and below. Furthermore, by adding ten data-movement (message passing) steps after this initial approximation, that error can be brought to a ten-thousandth of a percent as seen in Figure 1. In Figure 2 we can see scaling results as we increase the number of CPU cores utilized.

Figure 1: The proportional steady-state error obtained by the mean-field approximations of gene-regulatory dynamics on Erdos Renyi and Barabasi Albert models respectively.

Figure 2: Speed-ups provided by increasing the number of ranks on a test suite of real world graphs. Each run here is an initial mean-field approximation plus ten rounds of message passing.

Let’s change focus to network control. When it comes to network control, there is generally a single source of cost. That is, we want to force the network into a certain state, and we do this by spending some resource at specific nodes. As an example this could be controlling the spread of a disease using a universal basic income to ensure people can quarantine in the United States. In this case we are spending dollars to reduce fine-level network connectivity. Our single cost here is the dollar, and it is incurred from a single source, universal income. However if everyone is quarantined, this may incur costs from other sources as well. For instance, if the quarantine is all encompassing, important trade may not be able to happen, and infrastructure may degrade without upkeep. These costs should be accounted for. In 2021 I worked with many talented researchers to explore techniques for controlling these systems with multiple sources of cost in the paper Heuristic assessment of choices for risk network control [3].

Note, the paper came out in 2021 which, as an academic researcher, meant it had to be about COVID, almost contractually. That being said, the technique is more general than the the experiment in the paper implies, and a similar method was used by other members of the team to analyze airline traffic that same year [4]. In the model, we consider risk networks where nodes have some probability of incurring additional costs. Note, controlling one node may change that probability of activation for other nodes. In the paper we incorporate this into the cost function and use a popular control method, known as the linear quadratic regulator to determine dynamic control. Then for a set of control nodes we evaluate the total cost and control cost on the global risk network (described in the paper). These results can be seen in Figure 3.

Figure 3: Control cost and total cost for controlling the global risk network using LQR control. The average cost for a collection of 7 randomly chosen nodes is shown as the green bars, and the average cost is represented by a grey dotted line. In the paper, a collection of 7 specifically chosen nodes is compared against, and is represented by the red dotted line.

[1] Jiang, Chunheng, Jianxi Gao, and Malik Magdon-Ismail. "True nonlinear dynamics from incomplete networks." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 01, pp. 131-138. 2020.

[2] Brissette, Christopher, Jianxi Gao, Malik Magdon-Ismail, and George Slota. "Parallel computation of fixed points on networks of nonlinear ODE." networks 530, no. 7590 (2020): 307.

[3] Brissette, Christopher, Xiang Niu, Chunheng Jiang, Jianxi Gao, Gyorgy Korniss, and Boleslaw K. Szymanski. "Heuristic assessment of choices for risk network control." Scientific Reports 11, no. 1 (2021): 7645.

[4] Niu, Xiang, Chunheng Jiang, Jianxi Gao, Gyorgy Korniss, and Boleslaw K. Szymanski. "From data to complex network control of airline flight delays." Scientific Reports 11, no. 1 (2021): 18715.

[5] Das, Abhimanyu, Sreenivas Gollapudi, and Kamesh Munagala. "Modeling opinion dynamics in social networks." In Proceedings of the 7th ACM international conference on Web search and data mining, pp. 403-412. 2014.

[6] Keeling, Matt J., and Ken TD Eames. "Networks and epidemic models." Journal of the royal society interface 2, no. 4 (2005): 295-307.

[7] Zhang, Ju-ping, and Zhen Jin. "The analysis of an epidemic model on networks." Applied Mathematics and Computation 217, no. 17 (2011): 7053-7064.

[8] Larsson, Stig, and Vidar Thomée. Partial differential equations with numerical methods. Vol. 45. Berlin: Springer, 2003.

[9] Liu, Yang-Yu, and Albert-László Barabási. "Control principles of complex systems." Reviews of Modern Physics 88, no. 3 (2016): 035006.

[10] Gao, Jianxi, Yang-Yu Liu, Raissa M. D'souza, and Albert-László Barabási. "Target control of complex networks." Nature communications 5, no. 1 (2014): 5415.