Exchange-based diffusion in Hb-Graphs
Open Access
- 18 July 2020
- journal article
- research article
- Published by Springer Nature in Multimedia Tools and Applications
- Vol. 80 (15) , 22429-22464
Abstract
Highlighting important information of a network is commonly achieved by using random walks related to diffusion over such structures. Complex networks, where entities can have multiple relationships, call for a modeling based on hypergraphs. But, the limitation of hypergraphs to binary entities in co-occurrences has led us to introduce a new mathematical structure called hyperbaggraphs, that relies on multisets. This is not only a shift in the designation but a real change of mathematical structure, with a new underlying algebra. Diffusion processes commonly start with a stroke at one vertex and diffuse over the network. In the original conference article—(Ouvrard et al. 2018)—that this article extends we have proposed a two-phase step exchange-based diffusion scheme, in the continuum of spectral network analysis approaches, that takes into account the multiplicities of entities. This diffusion scheme allows to highlight information not only at the level of the vertices but also at the regrouping level. In this paper, we present new contributions: 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 between classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to two use cases, one based on Arxiv publications and another based on Coco dataset images. All the figures have been revisited in this extended version to take the new developments into account.Keywords
This publication has 33 references indexed in Scilit:
- Content-Based Visual Landmark Search via Multimodal Hypergraph LearningIEEE Transactions on Cybernetics, 2015
- Accounting Variables, Deception, and a Bag of Words: Assessing the Tools of Fraud DetectionContemporary Accounting Research, 2014
- Random walks in directed hypergraphs and application to semi-supervised image segmentationComputer Vision and Image Understanding, 2014
- Interactive Exploration of Implicit and Explicit Relations in Faceted DatasetsIEEE Transactions on Visualization and Computer Graphics, 2013
- Hypergraph Covering Problems Motivated by Genome Assembly Questions2013
- Bag-of-Words Representation in Image Annotation: A ReviewISRN Artificial Intelligence, 2012
- High-Ordered Random Walks and Generalized Laplacians on Hypergraphs2011
- Music recommendation by unified hypergraph2010
- Scientific collaboration networks. II. Shortest paths, weighted networks, and centralityPhysical Review E, 2001
- Scientific collaboration networks. I. Network construction and fundamental resultsPhysical Review E, 2001