The Node Vector Distance Problem in Complex Networks

Michele Coscia, Andres Gomez-Lievano, James McNerney, Frank Neffke

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

We describe a problem in complex networks we call the Node Vector Distance (NVD) problem, and we survey algorithms currently able to address it. Complex networks are a useful tool to map a non-trivial set of relationships among connected entities, or nodes. An agent—e.g., a disease—can occupy multiple nodes at the same time and can spread through the edges. The node vector distance problem is to estimate the distance traveled by the agent between two moments in time. This is closely related to the Optimal Transportation Problem (OTP), which has received attention in fields such as computer vision. OTP solutions can be used to solve the node vector distance problem, but they are not the only valid approaches. Here, we examine four classes of solutions, showing their differences and similarities both on synthetic networks and real world network data. The NVD problem has a much wider applicability than computer vision, being related to problems in economics, epidemiology, viral marketing, and sociology, to cite a few. We show how solutions to the NVD problem have a wide range of applications, and we provide a roadmap to general and computationally tractable solutions. We have implemented all methods presented in this article in a publicly available open source library, which can be used for result replication.
OriginalsprogEngelsk
Artikelnummer124
TidsskriftACM Computing Surveys
Vol/bind53
Udgave nummer6
Antal sider27
ISSN0360-0300
DOI
StatusUdgivet - 9 dec. 2020

Fingeraftryk

Dyk ned i forskningsemnerne om 'The Node Vector Distance Problem in Complex Networks'. Sammen danner de et unikt fingeraftryk.

Citationsformater