Vladimir Ouzienko, Prediction of Attributes and Links in Temporal Social Networks

Citation

Vladimir Ouzienko, Yuhong Guo and Zoran Obradovic. Prediction of Attributes and Links in Temporal Social Networks. Proceeding of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence.

Online Version

Prediction of Attributes and Links in Temporal Social Networks

Datasets

Experiments were conducted on two synthetic datasets and two real life datasets - Delinquency and Teenagers. The Delinquency consists of 4 temporal observation of 26 students where for each observation, the researchers collected delinquency measure (5 points scale score). The Teenagers consists of 3 temporal observations of 50 students, where for each observation the measurement of the students alcohol consumption was taken (also 5 points scale score).

Summary

This paper comes up a new model named Temporal Exponential Random Graphical Model(tERGM) to predict the attributes and links in Temporal Social Network. Mathematical theory and formula are presented in this paper to show how this model works in predicting nodes and links in a temporal social network. Additionally, some experiments based on this model are conducted to show the performance of this model. According to the paper's experiments results, this model has a fairly accurate prediction and lower MSE in prediction.

Brief Description of the tERGM Model Methods

This novel Model comes from htERGM Model. However, it has some difference with the htERGM Model in the following aspects:

• The tERGM model considers only the structures and topologies of the temporal networks, while node attributes are ignored.
• the htERGM model learns the network based on node attributes, but it does not make predictions of the future step.
• The application of htERGM is limited to retrieval of networks of up to 10 nodes because the model

requires to learn two sets of latent parameters the evolving structure of a temporal network and the changing attribute values of the nodes are given.

Given the evolving structure of a temporal network and the changing attribute values of the nodes,the tERGM model can facilitate simultaneous prediction of links and nodes attribute in a temporal social network. Instead of training a single joint probability prediction model, they build two conditional exponential random graph models. These two conditional predictors are mutually dependent on each other, and can then be used to predict the links, and the attribute values in an alternative way.

Different models are used to predict nodes and links:

For node prediction, use the following model:

For link prediction, use the following model

The node and link prediction models proposed above are all log-linear.Two sets of parameters, θ and γ need to be learned. This paper use Newton's optimization to learn the two parameters.

Experiments

This paper conducted some experiments by apply the tERGM to 4 different datasets, 2 of them are sythetic, the other two are real-life ones. The accuracy of the model and also the MSE between the prediction and the truth value.

In both experiments on synthetic and real life data the etERGM clearly outperformed the conventional predictors in prediction of actor’s attributes while the difference in predicting links for Teenagers was inconclusive which could be expected for a network of low density where the prediction problem is very difficult.

Self Comments

This model cannot be used in large-scale network according to my investigation. The author also admitted in the email, they only tested the model in a 500 nodes network. And it takes almost 50 hours to run the code. So, the model is still not perfect and may not be practical when applied to large-scale network. Further improvement is needed if planed to use in a large-scale network.

Related Papers

1. O. Frank and D. Strauss, ‘Markov graphs’, Journal of the American Statistical Association, 81, 832–842, (1986).
2. F. Guo, S. Hanneke, W. Fu, and E. P. Xing, ‘Recovering temporally rewiring networks: a model-based approach’, in ICML ’07: Proceedings of the 24th international conference on Machine learning, pp. 321–328, New York, NY, USA, (2007). ACM.
3. S. Hanneke and E. Xing, ‘Discrete temporal models of social networks’, in Proceedings of the ICML 06 Workshop on Statistical Network Analysis. Springer-Verlag (2006).
4. L. Michell and A. Amos, ‘Girls, pecking order and smoking’, Social Science and Medicine, 44(12), 1861 – 1869, (1997).
5. T. Snijders, C. Steglich, and G. van de Bunt, ‘Introduction to stochastic actor-based models for network dynamics’, Social Networks, (2009).