2018/09/01 by Xavier Ouvrard, Ouvrard, Xavier, Jean‐Marie Le Goff +3
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Multimedia (cs.MM) #Opinion Dynamics and Social Influence #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1809.00190
openalex publication_date 2018/09/01 · openalex created_date 2022/08/03 · openalex updated_date 2026/07/28
Most networks tend to show complex and multiple relationships between\nentities. Networks are usually modeled by graphs or hypergraphs; nonetheless a\ngiven entity can occur many times in a relationship: this brings the need to\ndeal with multisets instead of sets or simple edges. Diffusion processes are\nuseful to highlight interesting parts of a network: they usually start with a\nstroke at one vertex and diffuse throughout the network to reach a uniform\ndistribution. Several iterations of the process are required prior to reaching\na stable solution. We propose an alternative solution to highlighting the main\ncomponents of a network using a diffusion process based on exchanges: it is an\niterative two-phase step exchange process. This process allows to evaluate the\nimportance not only of the vertices but also of the regrouping level. To model\nthe diffusion process, we extend the concept of hypergraphs that are families\nof sets to families of multisets, that we call hb-graphs. This version is an\nextended version of arXiv:1809.00190v1: the overlaps with the v1 are in black,\nthe new content is in blue. The contributions of this extended version are: the\nproofs of conservation and convergence of the extracted sequences of the\ndiffusion process, as well as the illustration of the speed of convergence and\ncomparison to classical and modified random walks; the algorithms of the\nexchange-based diffusion and the modified random walk; the application to a use\ncase based on Arxiv publications. All the figures except one have been either\nmodified or added in this extended version to take into account the new\ndevelopments.\n