Finding Effective Spreaders for Fast Communication in Small and Large Networks
The identification of nodes in a network that will enable the fastest spread of information is an important if not fundamental problem in network control and design. It is applicable to the optimal placement of sensors, the design of secure networks and the problem of control when network resources are limited.
We consider a discrete time model of information spread that is associated with a random walk in a graph on a set of nodes V and a subset of V that can be associated with information spreaders. The most effective set of nodes is identified by finding or approximating a subset that minimizes the sum of the expected first hitting times of random walkers starting outside the set. Minimization is over all subsets of some constrained cardinality. Two approaches to the solution of this problem are discussed. The first uses the supermodularity of the function to be minimized. The second scalable approach is suitable for networks with millions of nodes, producing approximate solutions in a fraction of a second.
Fern Y Hunt is a research associate and scientist emeritus at the National Institute of Standards and Technology (NIST). A New York City native, Dr. Hunt attended public schools there, graduating from Bronx High School of Science. She holds an A.B. in Mathematics from Bryn Mawr College and an M.S. and PhD from New York University’s Courant Institute of Mathematical Sciences. Dr. Hunt spent the first part of her career in academia teaching at various institutions including City College of New York, University of Utah and finally Howard University. She joined the staff at Applied and Computational Mathematics Division of NIST after leaving Howard and collaborated with scientists on projects in magnetics, bioinformatics, and network modeling. Her mathematical interests are in the area of Markov chains and dynamical systems.
Hunt is the recipient of the Arthur Flemming Award for Outstanding Federal Service in Science, various research grants from NSF and NIST and was named a 2019 Fellow of the American Mathematical Society.