Evaluating dynamically evolving mobile-based social networks

Abstract

The increasing capabilities of mobile phones enable them to participate in different type of web-based systems. One of the most popular systems are social networks. The phonebooks of the mobile devices also represent social relationships of the owner. This can be used for discovering additional relations in social networks. Following this line of thought, mobile-based social networks can be created by enabling a synchronization mechanism between phonebooks of the users and the social network. This mechanism detects similarities between phonebook contacts and members of the network. Users can accept or ignore these similarities. After acceptance, identity links are formed. If a member changes her or his personal detail, it will be propagated automatically into the phonebooks, via identity links after considering privacy settings. Estimating the total number of these identity links is a key issue from scalability and performance point of view in such networks. We have implemented a mobile-based social network, called Phonebookmark and examined the structure of the network during a test period of the system. We have found, that the distribution of identity links of the users follows a power law. Based on this, we propose a model for estimating the total number of identity links in the dynamically evolving network. We verify the model by measurements and we also prove the accuracy of the model mathematically. For this we use the fact, that the number of identity links of each user (and thus, the value of the random variable modeling it) is bounded linearly by the number of members Nm of the network. Then we show, that the variance of the random variable is Θ(Nm3-β), where 2 < β ≤ 3 is the exponent of the bounded power law distribution, i.e. for constant c > 0, Pr[X = x] = c∙x-β, if x ≤ Nm and Pr[X = x] = 0 otherwise. The model and the results can be used in general when the distribution shows similar behavior.