The cover time of a sparse random intersection graph

arXiv1910.09639MaRDI QIDQ6327635FDOQ6327635

Authors: Mindaugas Bloznelis, Jerzy Jaworski, Katarzyna Rybarczyk 

Publication date: 21 October 2019

Abstract: Many known networks have structure of affiliation networks, where each of $n$ network's nodes (actors) selects an attribute set from a given collection of $m$ attributes and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study behaviour of the random walk on such networks. For that purpose we use commonly used model of such networks -- random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph $calG(n,m,p)$ at the connectivity threshold and above it. We consider the range of $n,m,p$ where the typical attribute is shared by (stochastically) bounded number of actors.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

This page was built for publication: The cover time of a sparse random intersection graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6327635)