Diffusion Dynamics Prediction on Networks Using Sub-graph Motif Distribution

摘要

Motifs are believed to represent structural and dynamical properties in networks. Nevertheless, small motifs are not always representative, while large motifs are hard to evaluate, which results in problem of recognition of optimal motif size, effective algorithms development, and motif significance estimation. We explore, in which extent diffusion dynamics on a graph can be estimated on the base of its subgraphs and motifs in particular. For this purpose we explore and compare motifs distributions for initial graph and its samples extracted by different techniques, and analyse how subgraph sizes affect prediction accuracy of diffusion time on the base on motifs. This allows to understand which subgraph sizes are appropriate for such kind of prediction, and how can we represent subgraph structural patterns to use smaller samples for dynamics approximations on large graphs. Several sampling techniques are compared for VK dataset with interest attribute markup. 4-5 node motifs are taken for graphs representation and for prediction evaluation.