Cargando…
Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships
Most networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes a...
Autores principales: | , , |
---|---|
Lenguaje: | eng |
Publicado: |
2018
|
Materias: | |
Acceso en línea: | https://dx.doi.org/10.1109/CBMI.2018.8516525 http://cds.cern.ch/record/2647073 |
_version_ | 1780960583068155904 |
---|---|
author | Ouvrard, Xavier Le Goff, Jean-Marie Marchand-Maillet, Stéphane |
author_facet | Ouvrard, Xavier Le Goff, Jean-Marie Marchand-Maillet, Stéphane |
author_sort | Ouvrard, Xavier |
collection | CERN |
description | Most networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes are useful to highlight interesting parts of a network: they usually start with a stroke at one vertex and diffuse throughout the network to reach a uniform distribution. Several iterations of the process are required prior to reaching a stable solution. We propose an alternative solution to highlighting main components of a network using a diffusion process based on exchanges; it is an iterative two-phase step exchange process. This process allows to evaluate the importance not only at the vertices level but also at the regrouping level. To model the diffusion process, we extend the concept of hypergraphs that are family of sets to family of multisets, that we call hb-graphs. |
id | oai-inspirehep.net-1702517 |
institution | Organización Europea para la Investigación Nuclear |
language | eng |
publishDate | 2018 |
record_format | invenio |
spelling | oai-inspirehep.net-17025172022-08-10T12:28:01Zdoi:10.1109/CBMI.2018.8516525http://cds.cern.ch/record/2647073engOuvrard, XavierLe Goff, Jean-MarieMarchand-Maillet, StéphaneExchange-Based Diffusion in Hb-Graphs: Highlighting Complex RelationshipsComputing and ComputersMost networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes are useful to highlight interesting parts of a network: they usually start with a stroke at one vertex and diffuse throughout the network to reach a uniform distribution. Several iterations of the process are required prior to reaching a stable solution. We propose an alternative solution to highlighting main components of a network using a diffusion process based on exchanges; it is an iterative two-phase step exchange process. This process allows to evaluate the importance not only at the vertices level but also at the regrouping level. To model the diffusion process, we extend the concept of hypergraphs that are family of sets to family of multisets, that we call hb-graphs.Most networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes are useful to highlight interesting parts of a network: they usually start with a stroke at one vertex and diffuse throughout the network to reach a uniform distribution. Several iterations of the process are required prior to reaching a stable solution. We propose an alternative solution to highlighting the main components of a network using a diffusion process based on exchanges: it is an iterative two-phase step exchange process. This process allows to evaluate the importance not only of the vertices but also of the regrouping level. To model the diffusion process, we extend the concept of hypergraphs that are families of sets to families of multisets, that we call hb-graphs. This version is an extended version of arXiv:1809.00190v1: the overlaps with the v1 are in black, the new content is in blue. The contributions of this extended version are: the proofs of conservation and convergence of the extracted sequences of the diffusion process, as well as the illustration of the speed of convergence and comparison to classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to a use case based on Arxiv publications. All the figures except one have been either modified or added in this extended version to take into account the new developments.arXiv:1809.00190oai:inspirehep.net:17025172018-09-01 |
spellingShingle | Computing and Computers Ouvrard, Xavier Le Goff, Jean-Marie Marchand-Maillet, Stéphane Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title | Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title_full | Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title_fullStr | Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title_full_unstemmed | Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title_short | Exchange-Based Diffusion in Hb-Graphs: Highlighting Complex Relationships |
title_sort | exchange-based diffusion in hb-graphs: highlighting complex relationships |
topic | Computing and Computers |
url | https://dx.doi.org/10.1109/CBMI.2018.8516525 http://cds.cern.ch/record/2647073 |
work_keys_str_mv | AT ouvrardxavier exchangebaseddiffusioninhbgraphshighlightingcomplexrelationships AT legoffjeanmarie exchangebaseddiffusioninhbgraphshighlightingcomplexrelationships AT marchandmailletstephane exchangebaseddiffusioninhbgraphshighlightingcomplexrelationships |