ITU

The Node Vector Distance Problem in Complex Networks

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

Standard

The Node Vector Distance Problem in Complex Networks. / Coscia, Michele; Gomez-Lievano, Andres; McNerney, James; Neffke, Frank.

In: ACM Computing Surveys, Vol. 53, No. 6, 124, 09.12.2020.

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

Harvard

Coscia, M, Gomez-Lievano, A, McNerney, J & Neffke, F 2020, 'The Node Vector Distance Problem in Complex Networks', ACM Computing Surveys, vol. 53, no. 6, 124. https://doi.org/10.1145/3416509

APA

Vancouver

Author

Coscia, Michele ; Gomez-Lievano, Andres ; McNerney, James ; Neffke, Frank. / The Node Vector Distance Problem in Complex Networks. In: ACM Computing Surveys. 2020 ; Vol. 53, No. 6.

Bibtex

@article{862316d0114d4d6abc2089d5bde3ede7,
title = "The Node Vector Distance Problem in Complex Networks",
abstract = "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.",
keywords = "complex networks, distance measure, social networks",
author = "Michele Coscia and Andres Gomez-Lievano and James McNerney and Frank Neffke",
year = "2020",
month = dec,
day = "9",
doi = "10.1145/3416509",
language = "English",
volume = "53",
journal = "A C M Computing Surveys",
issn = "0360-0300",
publisher = "Association for Computing Machinery",
number = "6",

}

RIS

TY - JOUR

T1 - The Node Vector Distance Problem in Complex Networks

AU - Coscia, Michele

AU - Gomez-Lievano, Andres

AU - McNerney, James

AU - Neffke, Frank

PY - 2020/12/9

Y1 - 2020/12/9

N2 - 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.

AB - 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.

KW - complex networks

KW - distance measure

KW - social networks

U2 - 10.1145/3416509

DO - 10.1145/3416509

M3 - Journal article

VL - 53

JO - A C M Computing Surveys

JF - A C M Computing Surveys

SN - 0360-0300

IS - 6

M1 - 124

ER -

ID: 85570355