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

Descripción completa

Detalles Bibliográficos
Autores principales: Ouvrard, Xavier, Le Goff, Jean-Marie, Marchand-Maillet, Stéphane
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