File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)

Article: Heterogeneous message passing for heterogeneous networks

TitleHeterogeneous message passing for heterogeneous networks
Authors
Issue Date26-Sep-2023
PublisherAmerican Physical Society
Citation
Physical Review E, 2023, v. 108 How to Cite?
Abstract

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.


Persistent Identifierhttp://hdl.handle.net/10722/338082
ISSN
2023 Impact Factor: 2.2
2023 SCImago Journal Rankings: 0.805

 

DC FieldValueLanguage
dc.contributor.authorCantwell, George T-
dc.contributor.authorKirkley, Alec-
dc.contributor.authorRadicchi, Filippo-
dc.date.accessioned2024-03-11T10:26:07Z-
dc.date.available2024-03-11T10:26:07Z-
dc.date.issued2023-09-26-
dc.identifier.citationPhysical Review E, 2023, v. 108-
dc.identifier.issn2470-0045-
dc.identifier.urihttp://hdl.handle.net/10722/338082-
dc.description.abstract<p>Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.</p>-
dc.languageeng-
dc.publisherAmerican Physical Society-
dc.relation.ispartofPhysical Review E-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.titleHeterogeneous message passing for heterogeneous networks-
dc.typeArticle-
dc.identifier.doi10.1103/PhysRevE.108.034310-
dc.identifier.volume108-
dc.identifier.eissn2470-0053-
dc.identifier.issnl2470-0045-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats