پیش بینی تکامل جوامع در شبکه های اجتماعی با استفاده از ویژگی های ساختاری و موقت Predicting the Evolution of Communities in Social Networks Using Structural and Temporal Features

I. INTRODUCTION Social networks evolve over time as a result of the activity of their users. New users join the network, old ones cease to be active or depart, while edges representing user interaction can be created, destroyed or exhibit a complex intermittent behaviour, giving rise to a dynamic network. Predicting the future form of a social network presents an interesting challenge with numerous applications, such as in marketing to locate appropriate groups of users on which to target advertisements, criminology to identify growing cliques of delinquent individuals that require immediate attention and journalism to uncover developing stories. One of the first prediction problems to be investigated in the context of social networks was edge prediction. Edge prediction refers to predicting whether an interaction (edge) will occur between two users of the network [1]–[3]. A related problem is that of edge sign prediction, where the goal is to infer whether an interaction between two users has a positive or negative context [4]–[6]. Communities represent the mesoscale structure of the social network and are implicitly formed as users with the same interests closely interact. As the interests of users change over time so do the communities, which may reduce or increase in size, or, even completely disappear from the network. Community evolution prediction concerns the prediction of the future form of a community given its present and past form and has been a hot research topic lately [7]–[10]. In this work we focus on four popular evolutionary phenomena of communities; growth, shrinkage, continuation and dissolution [7]. We present a framework for predicting these types of evolution that covers all the necessary steps involved, including the preprocesing of the data, the detection and tracking of the communities, the extraction of features to represent the communities and finally the training of a predictive model that discriminates the four evolutionary events. Particular focus is placed on employing an extensive set of structural and temporal features that capture various characteristics of the communities in order to get accurate predictions. To test the proposed framework, experiments are performed on a reallife social network dataset obtained from the Mathematics Stack Exchange Q&A site. Results confirm the efficacy of our framework and the importance of using a mixture of structural and temporal features. The rest of paper is organized as follows. In Section II we provide a review of related on work on methods for community evolution prediction. In Section III we present our framework for community evolution prediction placing special focus on the extraction of appropriate features to represent communities. Next, in Section IV we present experiments using a real-life social network. Finally, in Section V concludes this work and offers directions for future work.