Modeling interest-based social networks: Superimposing Erdős-Rényi graphs over random intersection graphs

摘要

There is a recent rise of interest-based social networks (e.g., Pinterest and Goodreads), which connect users by relations based on shared interests. In these networks, links between users manifest from selecting common interests from a pool of available interests. For example, two users may establish a link on Pinterest because of both liking dog photos, or on Goodreads due to reading the same novel. In this paper, we introduce a random graph model to represent an interest-based social network, in consideration of users' shared interests as well as their friend relations. More specifically, the graph model is the result of superimposing an Erdös-Rényi graph (representing friendships) over a uniform random d-intersection graph (representing common interests). We present critical conditions of the model parameters so that the network is connected. Our connectivity results are useful to understand interest-based social networks and particularly beneficial for publish-subscribe services in these networks. The formally-proved results are also confirmed via experiments.