A local algorithm for detecting community structures in dynamic networks

The emergence and the global adaptation of mobile devices has influenced human interactions at the individual, community, and social levels leading to the so called Cyber-Physical World (CPW) convergence scenario [1]. One of the most important features of CPW is the possibility of exploiting information about the structure of social communities of users, that manifest through joint movement patterns and frequency of physical co-location: mobile devices of users that belong to the same social community are likely to "see" each other (and thus be able to communicate through ad hoc networking techniques) more frequently and regularly than devices outside of the community. In mobile opportunistic networks, this fact can be exploited, for example, to optimize networking operations such as forwarding and dissemination of messages. In this paper we present a novel local cognitive-inspired algorithm for revealing the structure of these dynamic social networks by exploiting information about physical encounters, logged by the users' mobile devices as they encounter each other. We show that with our approach, that mimics - locally at each node - the epidemic spread of information in the network induced by the observed frequency and regularity of contacts, we are able to detect not only the existing communities but also to identify dynamic interactions among the individuals. Thus, the main features of our scheme are: (i) the capacity of detecting social communities induced by physical co-location of users through distributed, online algorithms; (ii) the capacity to detect users belonging to more communities (thus acting as bridges across them), and (iii) the capacity to detect the dynamics of communities evolution over time.