Random intersection graphs with communities

Remco van der Hofstad, Julia Komjathy, Viktoria Vadon

Published 2018-09-07Version 1

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of groups and individuals, where these groups may overlap. Group memberships are generated through the bipartite configuration model. Conditionally on the group memberships, the classical random intersection graph is obtained\hyphenation{ob-tained} by connecting individuals when they are together in at least one group. We generalize this definition, allowing for arbitrary community structures within the groups. In our new model, groups might overlap and they have their own internal structure described by a graph, the classical setting corresponding to groups being complete graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, derive the asymptotic degree distribution and the local clustering coefficient. These proofs rely on local weak convergence, which also implies that subgraph counts converge. We also exploit the connection to the bipartite configuration model, for which we also prove local weak convergence, and which is interesting in its own right.