The Transport Complexity of Data Dissemination in Online Social Networks

In this paper, we address the issue on measuring the transport difficulty of data dissemination in online social networks (OSNs). We define a new metric, called \emph{transport complexity}, as one of the fundamental limits on the data dissemination in OSNs. It involves two key factors: data arrival process at users and transport distance of messages, which are also both significant factors for the network's transport capacity. To model the data dissemination in OSNs, we formulate the geographical distribution feature of dissemination sessions in OSNs by introducing a three-layered system model that consists of physical deployment layer, social relationship layer, and application session layer. We discover and validate the mutual relevances among these three layers as the preconditions for bounding the transport complexity. Moreover, we introduce the Zipf's distribution to describe the friendship degree by considering the scale-free property of user degree centrality in OSNs. Furthermore, in order to model the diversity of session patterns, we assume that: for the session with a source node, say $v$, the number of chosen destinations from all friends of $v$ follows a special Zipf's distribution whose parameters depend on the degree of $v$. Based on this system model, we derive the lower bound on transport complexity for the novel data dissemination in a large-scale OSN.