隨著社群網路的普及，在網路上人與人的連結已成為一種社群網路，而這些連結會隨著時間改變，稱為動態社群網路。我們將網路以圖形的方式呈現，為了考慮其有時續性，我們將一系列的社群網路以一定的時間間隔劃分為動態社群網路，以用來觀察節點的連結的演化趨勢來預測為來會有那些連結出現或消失。這就是所謂的動態網路連結預測(DNLP)，也就是說我們可以根據歷史行為來推斷目標未來的行動或是偏好。我們提出了一種基於長短期記憶(LSTM)模型，稱之為 E-TLSTM-D，E-TLSTM-D結合了分群演算法, auto-encoder 和Time-Aware LSTM(T-LSTM)，用於動態網路的連結預測，將分群後的資料壓縮，再以T-LSTM捕獲其時序之間的關聯性，最後再將其還原並且判斷其預測結果與真實資料的相似度。同時，他能夠在有限的記憶體下有效的預測大型社群網路在下一個網路圖中將會出現及消失的連結。

With the popularity of social networks, the connection between people on the Internet has become a kind of social network, and these connections will change over time, called dynamic social networks. We present the network as a graphical format. In order to consider its temporal continuity, we divide a series of social networks into dynamic social networks at certain time intervals, and use them to observe the evolution of links to predict which links will appear or disappear in the future. This is called Dynamic Network Link Prediction (DNLP), which means that we can predict a target's future actions or preferences based on historical behaviors. We propose a model based on long and short-term memory (LSTM), called E-TLSTM-D. E-TLSTM-D combines cluster algorithm, auto-encoder and T-LSTM for link prediction of dynamic networks. We compress the clustered data, and then capture the correlation between the time series by T-LSTM. Finally, we reconstruct data and evaluate the similarity between the prediction results and the real data. At the same time, it is able to effectively predict the links that will appear and disappear in the next network graph for large social networks with limited memory.

Table of Contents 
Chapter 1 Introduction…………………………………………………………… 1 
Chapter 2 Related Work ………………………………………………………...... 4 
2.1 Social Network Compression ……………………………………………... 4 
2.2 Social Network Link Prediction……………………………………... 5 
2.3 Recurrent Neural Network ………………………………………………… 7 Chapter 3 Methodology …………………………………………………………… 9 
3.1 Problem Definition………………………………………………………… 9 
3.1.1 Dynamic Network ………………………………………………….. 9 
3.1.2 Dynamic Network Link Prediction ……………………………… 9 
3.2 E-TLSTM-D Framework …………………………………………………. 10 
3.2.1 Cluster ……………………………………………………………... 11 
3.2.2 Autoencoder ……………………………………………………….. 11 
3.2.3 Long Short-Term Memory (LSTM) ……………………………….. 12 
3.3 Training Process …………………………………………………………... 14 
Chapter 4 Experiments …………………………………………………………… 15 
4.1 Datasets…………………………………………………………………… 15 
4.2 Baselines …………………………………………………………………... 16
4.3 Evaluation Metrics………………………………………………………... 17 
4.4 Experiment Results……………………………………………………….. 19 
4.5 Parameter Setting …………………………………………………………. 20 
Chapter 5 Conclusion……………………………………………………………... 24 Reference…………………………………………………………………………... 25

List of Figures 
Figure 1: The illustration shows the evolution of the network. … 10 
Figure 2: The structure of E-TLSTM-D. …………………………………………10 
Figure 3: Data pre-processing. ……………………………………………………11 
Figure 4: TP and FP rate at different classification thresholds.……………… 18 
Figure 5: AUC (Area under the ROC curve). ……………………………… 18 
Figure 6: AUC performance of E-TLSTM-D models on different optimizer.  21 
Figure 7: AUC performance of E-TLSTM-D models on different sliding window size. …………………………………………………………………......... 21 
Figure 8: AUC performance of E-TLSTM-D models on different number of LSTM layer. ……………………………………………………………………... 22 
Figure 9: AUC performance of E-TLSTM-D models on different learning rate.  22 
Figure 10: AUC performance of E-TLSTM-D models on different epoch.…… 23

List of Table 
Table 1. Basic statistics of seven datasets. ………………………………… 16 
Table 2. ROC confusion matrix. ………………………………………………… 17 
Table 3. AUC performance of different on small datasets. ………………… 19 
Table 4. AUC performance of different on large datasets. ……………………20

[1] H. Maserrat and J. Pei, "Community Preserving Lossy Compression of Social Networks," 2012 IEEE 12th International Conference on Data Mining, Brussels, 2012, pp. 509-518, doi: 10.1109/ICDM.2012.14.
[2] Z. Liu, Y. Ma and X. Wang, "A Compression-Based Multi-Objective Evolutionary Algorithm for Community Detection in Social Networks," in IEEE Access, vol. 8, pp. 62137-62150, 2020, doi: 10.1109/ACCESS.2020.2984638.
[3] C. Leung, F. Jiang and Y. Zhang, "Flexible Compression of Big Data," 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Vancouver, BC, Canada, 2019, pp. 741-748, doi: 10.1145/3341161.3343512.
[4] S. Das, J. Leopold, S. Ghosh and S. K. Das, "Graph compaction in analyzing large scale online social networks," 2017 IEEE International Conference on Communications (ICC), Paris, 2017, pp. 1-6, doi: 10.1109/ICC.2017.7996910.
[5] Hossein Maserrat and Jian Pei. 2010. Neighbor query friendly compression of social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '10). Association for Computing Machinery, New York, NY, USA, 533–542. DOI:https://doi.org/10.1145/1835804.1835873
[6] M. Nelson, S. Radhakrishnan, A. Chatterjee and C. N. Sekharan, "On compressing massive streaming graphs with Quadtrees," 2015 IEEE International Conference on Big Data (Big Data), Santa Clara, CA, 2015, pp. 2409-2417, doi: 10.1109/BigData.2015.7364035.
[7] Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A. & Raghavan, P. (2009). On compressing social networks.. In J. F. E. IV, F. Fogelman-Soulié, P. A. Flach & M. J. Zaki (eds.), KDD (p./pp. 219-228), : ACM. ISBN: 978-1-60558-495-9
[8] M. Nelson, S. Radhakrishnan, A. Chatterjee and C. N. Sekharan, "Queryable compression on streaming social networks," 2017 IEEE International Conference on Big Data (Big Data), Boston, MA, 2017, pp. 988-993, doi: 10.1109/BigData.2017.8258020.
[9] M. Nelson, S. Radhakrishnan and C. N. Sekharan, "Queryable Compression on Time-Evolving Social Networks with Streaming," 2018 IEEE International Conference on Big Data (Big Data), Seattle, WA, USA, 2018, pp. 146-151, doi: 10.1109/BigData.2018.8622386.
[10] Adamic, Eytan and Adar, Lada A.. "Friends and neighbors on the web." , no. 3 (2003): 211-230.
[11] M. Marjan, N. Zaki and E. A. Mohamed, "Link Prediction in Dynamic Social Networks: A Literature Review," 2018 IEEE 5th International Congress on Information Science and Technology (CiSt), Marrakech, 2018, pp. 200-207, doi: 10.1109/CIST.2018.8596511.
[12] H. Wang, W. Hu, Z. Qiu and B. Du, "Nodes' Evolution Diversity and Link Prediction in Social Networks," in IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 10, pp. 2263-2274, 1 Oct. 2017, doi: 10.1109/TKDE.2017.2728527.
[14] K. Zhu and M. Cao, "A Semantic Subgraphs Based Link Prediction Method for Heterogeneous Social Networks with Graph Attention Networks," 2020 International Joint Conference on Neural Networks (IJCNN), Glasgow, United Kingdom, 2020, pp. 1-8, doi: 10.1109/IJCNN48605.2020.9207586.
[15] T. Murata and S. Moriyasu, "Link Prediction of Social Networks Based on Weighted Proximity Measures," IEEE/WIC/ACM International Conference on Web Intelligence (WI'07), Fremont, CA, 2007, pp. 85-88, doi: 10.1109/WI.2007.52.
[16] Mohammad Al Hasan and Vineet Chaoji and Saeed Salem and Mohammed Zaki,” Link prediction using supervised learning,” In Proc. of SDM 06 workshop on Link Analysis, Counterterrorism and Security,2006.
[17] C. Fu et al., "Link Weight Prediction Using Supervised Learning Methods and Its Application to Yelp Layered Network," in IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 8, pp. 1507-1518, 1 Aug. 2018, doi: 10.1109/TKDE.2018.2801854.
[18] K. Zhu, M. Cao and H. Lu, "MALP: A More Effective Meta-Paths Based Link Prediction Method in Partially Aligned Heterogeneous Social Networks," 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), Portland, OR, USA, 2019, pp. 644-651, doi: 10.1109/ICTAI.2019.00095.
[19] Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. 2020. NHP: Neural Hypergraph Link Prediction. Proceedings of the 29th ACM International Conference on Information & Knowledge Management. Association for Computing Machinery, New York, NY, USA, 1705–1714.
[20] Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS'18). Curran Associates Inc., Red Hook, NY, USA, 5171–5181.
[21] K. Selvarajah, K. Ragunathan, Z. Kobti and M. Kargar, "Dynamic Network Link Prediction by Learning Effective Subgraphs using CNN-LSTM," 2020 International Joint Conference on Neural Networks (IJCNN), 2020, pp. 1-8, doi: 10.1109/IJCNN48605.2020.9207301.
[22] P. V. Tran, "Learning to Make Predictions on Graphs with Autoencoders," 2018 IEEE 5th International Conference on Data Science and Advanced Analytics (DSAA), 2018, pp. 237-245, doi: 10.1109/DSAA.2018.00034.
[23] Alex Graves. 2008. Supervised Sequence Labelling with Recurrent Neural Networks. Studies in Computational Intelligence 385 (2008).
[24] S, Hochreiter, and J. Schmidhuber, “LONG SHORT-TERM MEMORY”, Neural Computation 9(8):1735-1780, November 1997. 
[25] Chung, J., Gulcehre, C., Cho, K., & Bengio, Y. (2014). Empirical evaluation of gated recurrent neural networks on sequence modeling. In NIPS 2014 Workshop on Deep Learning, December 2014.
[26] I. Baytas, C. Xiao, X. Zhang, F. Wang, A. Jain, and J. Zhou, “Patient Subtyping via Time-Aware LSTM Networks,” Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2017), pp. 65-74, 2017. 
[27] Y. Zhu, H. Li, Y. Liao, B. Wang, Z. Guan, H. Liu, and D. Cai, “What to Do Next: Modeling User Behaviors by Time-LSTM,” Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), pp. 3602-3608, 2017. 
[28] Y. -C. Chen, T. Thaipisutikul and T. K. Shih, "A Learning-Based POI Recommendation With Spatiotemporal Context Awareness," in IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2020.3000733.
[29] J. Chen et al., "E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, doi: 10.1109/TSMC.2019.2932913.
[30] Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. 2018. Continuous-Time Dynamic Network Embeddings. In Companion Proceedings of the The Web Conference 2018 (WWW '18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 969–976. DOI :https://doi.org/10.1145/3184558.3191526
[31] L. Zhao et al., "T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction," in IEEE Transactions on Intelligent Transportation Systems, vol. 21, no. 9, pp. 3848-3858, Sept. 2020, doi: 10.1109/TITS.2019.2935152.
[32]W. Yuan, K. He, D. Guan and G. Han, "Edge-Dual Graph Preserving Sign Prediction for Signed Social Networks," in IEEE Access, vol. 5, pp. 19383-19392, 2017, doi: 10.1109/ACCESS.2017.2746258.