ITU

Generalized Euclidean Measure to Estimate Network Distances

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

View graph of relations

Estimating the distance covered by a propagation phenomenon on a network is an important task: it can help us estimating the infectiousness of a disease or the effectiveness of an online viral marketing campaign. However, so far the only way to make such an estimate relies on solving the optimal transportation problem, or by adapting graph signal processing techniques. Such solutions are either inefficient, because they require solving a complex optimization problem; or fragile, because they were not designed with this problem in mind. In this paper, we propose a new generalized Euclidean approach to estimate distances between weighted groups of nodes in a network. We do so by adapting the Mahalanobis distance, incorporating the graph's topology via the pseudoinverse of its Laplacian. In experiments we see that this measure returns intuitive distances which agree with the ones a human would estimate. We also show that the measure is able to recover the infection parameter in an epidemic model, or the activation threshold in a cascade model. We conclude by showing that the measure can be used in online social media settings to identify fast-spreading behaviors. Our measure is also less computationally expensive.
Original languageEnglish
Title of host publicationProceedings of the International AAAI Conference on Web and Social Media
Number of pages11
PublisherAAAI Press
Publication date2 Jun 2020
Pages119-129
Publication statusPublished - 2 Jun 2020
Event14th International Conference on Web and Social Media (ICWSM) - Atlanta, United States
Duration: 8 Jun 202011 Jun 2020
https://www.icwsm.org/2020/index.html

Conference

Conference14th International Conference on Web and Social Media (ICWSM)
LandUnited States
ByAtlanta
Periode08/06/202011/06/2020
Internetadresse
Close

    Research areas

  • complex networks, social networks, euclidean distance, network distance

ID: 85143380