如今，在虛擬世界中，人與人之間的關係已然形成一種網路社會，從而形成了「社群網絡」。
為了將網路作為圖形處理並考慮其時間特性，我們設置時間點作為固定間隔，並將一系列快照劃分為「動態社群網絡」，以觀察節點的連結趨勢並預測哪些節點將出現或消失在圖中。 此過程稱為「動態網路連結預測」(Dynamic Network Link Prediction ,DNLP)，這意味著我們可以根據其歷史行為來推斷將與目標用戶建立關係的特定人群。動態網路連結預測也可以應用於各個領域，並且由於其高靈活性，也非常適合與其他深度學習方法相結合。 我們提出了一種新的基於學習的模型，Enc-LSTM，用於動態網路的連結預測，並處理長期預測任務，以捕獲序列之間的向量相關性，並將它們映射至低維度以適應不同規模的網絡。 同時，它也具有更穩健的能力來預測將在下一個網路圖中將出現或消失的連結。

Nowadays, online society as the relationship between the person and others in the virtual world, so as to make the "social network". To deal with the network as the graph and considered its time characteristic, we set the fixed interval, timestamp, to divide a sequence of snapshots as the "dynamic social network", that can observe the link trend of nodes and predict which node will appear or disappear in the graph. This process called "dynamic network link prediction (DNLP)" which means we can infer the particular people who will make a relationship with the target user based on their historical behaviors. The dynamic network link prediction can also apply to various areas and has quite suitable to combine with other deep learning methods due to their high flexibility. We proposed a novel learning-based model, Enc-LSTM, to do the link prediction of dynamic social networks and deal with the long-term prediction tasks for capture the relevance of vectors between the sequences and maps them into low- dimension to suit the different scales network. At the same time, it also has a more robust ability to predict the links that are going to appear or disappear in the next network graphs.

Table of Contents
Chinese Abstract	I
Abstract	        III
Table of Contents	IV
List of Figures  	VI
List of Tables	        VII

Chapter 1 Introduction	                1
Chapter 2 Related Work	                4
2.1 Static Network Link Prediction	4
2.2 Dynamic Network Link Prediction	5
2.3 Autoencoder	                        6
2.4 Long Short Term Memory (LSTM)	6 
Chapter 3 Preliminaries	                7
3.1	Problem Description	        7
	3.1.1 Dynamic Social Network	7
	3.1.2 Compression Problem	8
	3.1.3 Prediction Problem	8
3.2	Models Description	        9
	3.2.1 Autoencoder	        9
	3.2.2 LSTM	                12
Chapter 4 Methodology	                14
4.1 Framework	                        14
4.2 Autoencoder Application	        17
	4.2.1 Vector Embedding	        17	
        4.2.2 Compression	        18
4.3 LSTM Application	                19
Chapter 5 Experiments Result	        22
5.1	Datasets	                22
5.2	Comparing Method	        23
5.3 Evaluation Metrics	                27
5.4	Experiment Result	        29
5.5 Parameter Sensitivity	        33
Chapter 6 Conclusion	                36
Reference	                        37

 
List of Figures
Figure 1: An Illustration of Network Evolution	2
Figure 2: Autoencoder Architecture	        10
Figure 3: Loss Calculation of Autoencoder	10
Figure 4: Basic Structure of LSTM	        12
Figure 5: Schema of Proposed Method	        14
Figure 6: Different Num. of Generated Snapshots	34
Figure 7: Different Num. of Units Setting in Same Datasets	                                35

 
List of Tables
Table 1: Terms and Notations in the Proposed Method	 
                                                     19
Table 2: Terms and Notations in LSTM	             20
Table 3: Virtual Datasets Generated from Synfix	     23
Table 4: The Units on the Encoder Processing of Enc-LSTM	 
                                                     27
Table 5: Accuracy of Methods on Dataset with 128 users	 
                                                     30
Table 6: Accuracy of Methods on Dataset with 200 users	                                                                                                          
                                                     30
Table 7: The Result on Dataset with 128 users and 50000 epochs	                                             31
Table 8: The Result on Dataset with 200 users and 50000 epochs	                                             31
Table 9: The Result on Dataset with 128 users and 55000 epochs	                                             32
Table 10: The Result on Dataset with 200 users and 55000 epochs	                                             32

[1]  Nahla Mohamed Ahmed, Ling Chen, “An efficient algorithm for link prediction in temporal uncertain social networks” Information Sciences, 331:120–136, 2016.
[2]  N. M. Ahmed, L. Chen, Y. Wang, B. Li, Y. Li, and W. Liu, “Sampling-based algorithm for link prediction in temporal networks,” Information Sciences, vol. 374, pp. 1–14, 2016.
[3]  L. Backstrom, J. Leskovec, “Supervised Random Walks: Predicting and Recommending Links in Social Networks” in WSDM, 2011
[4]  Pierre Baldi, I. Guyon, G. Dror, V. Lemaire, G. Taylor and D. Silver, “Autoencoders, Unsupervised Learning, and Deep Architectures” JMLR: Workshop and Conference Proceedings 27:37-50, 2012
[5]  Jinyin Chen, Jian Zhang, Xuanheng Xu, Chengbo Fu, Dan Zhang, Qingpeng Zhang, and Qi Xuan. E-lstm-d: A deep learning framework for dynamic network link prediction. arXiv preprint arXiv:1902.08329, 2019.
[6]  Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078, 2014
[7]  Rahul Dey, Fathi M. Salemt, “Gate-variants of Gated Recurent Unit (GRU) neural networks”, 2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS)
[8]  Felix A. Gers, Jürgen Schmidhuber, and Fred Cummins, “Learning to Forget: Continual Prediction with LSTM”, In Artificial Neural Networks, 1999. ICANN 99. Ninth International Conference on (Conf. Publ. No. 470), volume 2, pages 850-855, 1999.
[9]  Klaus Greff, Rupesh K. Srivastava, Jan Koutn ́ık, Bas R. Steunebrink, Jurgen Schmidhuber, “LSTM: A Search Space Odyssey”, TRANSACTIONS on NEURAL NETWORKS and LEARNING SYSTEMS, 2017
[10]  Aditya Grover, Jure Leskovec, “Node2vec: Scalable Feature Learning for Networks”, in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016, pp.855-864.
[11]  N. M. A. Ibrahim and L. Chen, “Link prediction in dynamic social   networks by integrating different types of information,” Applied Intelligence, vol. 42, no. 4, pp. 738–750, 2015.
[12]  D. Kempe, J. M. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network”, In KDD, 2003
[13]  X. Li, N. Du, H. Li, K. Li, J. Gao, and A. Zhang, “A deep learning approach to link prediction in dynamic networks,” in Proceedings of the 2014 SIAM International Conference on Data Mining. SIAM, 2014, pp. 289–297.
[14]  Sheng Li, Jaya Kawale, Yun Fu, “Deep Collaborative Filtering via Marginalized Denoising Autoencoder”, ACM, 2015
[15]  Xiaopeng Li, James She, “Relational Variational Autoencoder for Link Prediction with Multimedia Data”, Thematic Workshops’ 17, Oct. 23-27, 2017, Mountain View, CA, USA
[16]  T. Li, J. Zhang, S. Y. Philip, Y. Zhang, and Y. Yan, “Deep dynamic network embedding for link prediction,” IEEE Access, 2018.


[17]  David Liben-Nowell, Jon Kleinberg, “The link-prediction problem for social networks”, Journal of the American Society for Information Science and Technology banner
[18]  Siddharth Pal, Yuxiao Dong, Bishal Thapa, nitesh V. Chawla, Ananthram Swami, Ram Ramanathan, “Deep Learning for Network Analysis: Problems, Approaches and Challenges”, Milcom Track 5 – Selected Topics in Communications, 2016
[19]  B. Perozzi, R. A1-Rfou, and S. Skiena, “DeepWalk: Online Learning of Social Representations”, I in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014, pp. 701-710.
[20]  Rudy Raymond, Hisashi Kashima, “Fast and Scalable Algorithms for Semi-supervised Link Prediction on Static and Dynamic Graphs”, ECML PKDD 2010: Machine Learning and Knowledge Discovery in Databases pp 131-147
[21]  Phi Vu Tran, “Learning to Make Predictions on Graphs with Autoencoders”, 2018 IEEE 5th International Conference on Data Science and Advanced Analytics
[22]  D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016, pp. 1225–1234.
[23]  Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang, “NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks”, KDD2018, August 19-23, 2018, London Kingdom 
[24]  L. Yao, L. Wang, L. Pan, and K. Yao, “Link prediction based on common-neighbors for dynamic social network,” Procedia Computer Science, vol.83, pp.82–89, 2016 
[25]  Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, Aram Galstyan, “Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks”, IEEE Transactions on Knowledge and Data Engineering, Vol. 28, No.10, October 2016