TY - GEN
T1 - Network connectivity optimization: An evaluation of heuristics applied to complex networks and a transportation case study
AU - Auerbach, Jeremy
AU - Kim, Hyun
PY - 2020/7/31
Y1 - 2020/7/31
N2 - Network optimization has generally been focused on solving network flow
problems, but recently there have been investigations into optimizing
network characteristics. Optimizing network connectivity to maximize the
number of nodes within a given distance to a focal node and then
minimizing the number and length of additional connections has not been
as thoroughly explored, yet is important in several domains including
transportation planning, telecommunications networks, and geospatial
analysis. We compare several heuristics to explore this network
connectivity optimization problem with the use of random networks,
including the introduction of two planar random networks that are useful
for spatial network simulation research, and a real-world case study
from urban planning and public health. We observe significant variation
between nodal characteristics and optimal connections across network
types. This result along with the computational costs of the search for
optimal solutions highlights the difficulty of finding effective
heuristics. A novel genetic algorithm is proposed and we find this
optimization heuristic outperforms existing techniques and describe how
it can be applied to other combinatorial and dynamic problems.
AB - Network optimization has generally been focused on solving network flow
problems, but recently there have been investigations into optimizing
network characteristics. Optimizing network connectivity to maximize the
number of nodes within a given distance to a focal node and then
minimizing the number and length of additional connections has not been
as thoroughly explored, yet is important in several domains including
transportation planning, telecommunications networks, and geospatial
analysis. We compare several heuristics to explore this network
connectivity optimization problem with the use of random networks,
including the introduction of two planar random networks that are useful
for spatial network simulation research, and a real-world case study
from urban planning and public health. We observe significant variation
between nodal characteristics and optimal connections across network
types. This result along with the computational costs of the search for
optimal solutions highlights the difficulty of finding effective
heuristics. A novel genetic algorithm is proposed and we find this
optimization heuristic outperforms existing techniques and describe how
it can be applied to other combinatorial and dynamic problems.
KW - Physics - Physics and Society
KW - Computer Science - Computational Engineering
KW - Finance
KW - and Science
KW - Computer Science - Social and Information Networks
M3 - Other contribution
T3 - arXiv
ER -