ITU

The Node Vector Distance Problem in Complex Networks

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

View graph of relations

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.
Original languageEnglish
Article number124
JournalACM Computing Surveys
Volume53
Issue number6
Number of pages27
ISSN0360-0300
DOIs
Publication statusPublished - 9 Dec 2020
Close

    Research areas

  • complex networks, distance measure, social networks

Downloads

No data available

ID: 85570355