至今有關解決影響力最大化問題已經有許多的方法及文獻，這些方法和文獻都是基於貪婪演算法。不過，因為社群網路規模日趨龐大，因此使得演算法的效率及可擴展性越來越重要。近年來有關影響力最大化問題的研究也都著重於演算法的效率，但這些方法都是以分析靜態的資料(社群網路)為主。然而現今的社群網路成長速度非常快速，在社群網絡上每分每秒都有新的關係或互動產生，我們將之稱為動態社群網路。因此在本文中我們分析的對象主要是以動態社群網路為主，藉由觀察動態社群網路結構的變化，找出變化的規則並建構出一個模型，來預測未來的社群結構，最後利用有效率的演算法來解決影響力最大化問題。我們的實驗也證實了我們的預測模型有很高的精准度，並且藉由觀察動態社群網路所預測得到未來網路結構上能得到與靜態網路不同的使用者集合，並且能得到更大的影響力散播。

Up to now, much literature has focused on influence maximization problem. These methods and literature are all based on the greedy algorithm. However, social networks are growing rapidly, so the efficiency and scalability of the algorithm have become more important. In recent years, the study on the issue of influence maximization has also focused on the efficiency of the algorithm, but these studies are all based on the analysis of the static social network. However, every minute and second has new relationships or interaction on the social network, we describe this status as the dynamic social network. Therefore, in this paper, we focus on the analysis of the dynamic social network. By observing the changes in the dynamic social network structure, we can find out the pattern of variation and build a model to predict the future network structure. Eventually, using an efficient algorithm to solve the influence maximization problem based on the dynamic social network. The experimental results show that our prediction model has a high accuracy, we also can obtain a seed set different from the analysis of static social network and get more influence spreads.

Table of Contents
Chinese Abstract  I
Abstract  II
Table of Contents  IV
List of Figures  V
List of Tables  VI
List of Algorithms  VII
Chapter 1	p.1
Introduction	p.1
Chapter 2	p.5
Preliminaries	p.5
2.1 Link Prediction	p.5
2.1.1 Unsupervised Learning	p.6
2.1.2 Supervised Learning	p.7
2.2 Influence Maximization Problem	p.8
Chapter 3	p.11
Proposed Methods	p.11
3.1 Link Prediction	p.11
3.2 Novel IC Model with Decay function	p.13
3.3 Two-phase Influence Maximization (TIM)	p.14
3.4 Influence Maximization on Predicted Network	p.16
Chapter 4	p.17
Experiments	p.17
4.1 Experiment Settings	p.17
4.2 Experiment Result	p.18
4.2.1 Different parameter setting	p.22
Chapter 5	p.25
Related Work	p.25
5.1 Link Prediction	p.25
5.2 Influence Maximization Algorithms	p.25
Chapter 6	p.27
Conclusions	p.27
Reference	p.28

List of Figures 
Figure 1: Link Prediction task	p.5
Figure 2: Schema of our method	p.11
Figure 3: Decay function	p.13
Figure 4: IC model with decay function	p.14
Figure 5: Influence spread of different seed sets on Bitcoin OTC	p.19
Figure 6: Influence spread of different seed sets on Cit-HepTh	p.21
Figure 7: Influence spread of different seed sets on Cit-HepPh	p.22
Figure 8: Influence spread of different γ on Bitcoin OTC	p.23
Figure 9: Influence spread of different γ on Cit-HepTh	p.23
Figure 10: Influence spread of different γ on Cit-HepPh	p.24

List of Table
Table 1: Properties of datasets	p.18
Table 2: Results for link prediction on Bitcoin OTC	p.19
Table 3: Network graphs on Bitcoin OTC	p.19
Table 4: Results for link prediction on Cit-HepTh	p.20
Table 5: Network graphs on Cit-HepTh	p.20
Table 6: Results for link prediction on Cit-HepPh	p.21
Table 7: Network graphs on Cit-HepPh	p.22

List of Algorithms
Algorithm 1: Greedy Algorithm	p.8
Algorithm 2: Link Prediction	p.12

[1] Y.C Chen, W.Y Zhu, W.C Peng, W.C Lee, and S.Y Lee, “CIM: Community-Based Influence Maximization in Social Networks,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, issue 2, article 25, 2014.
[2] W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’10), pp. 1029-1038, 2010.
[3] D. Kempe, J. M. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03), pp. 137-146, 2003.
[4] P. Domingos and M. Richardson, “Mining the network value of customers,” Proceedings of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57-66, 2001.
[5] C. Chang, P. Yang, M. Lyu, and K. Chuang, “Influence Sustainability on Social Networks,” 2015 IEEE International Conference on Data Mining (ICDM), 2015.
[6] W. Chen W. Lu, and N. Zhang, “Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process,” Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12), pp. 592-598, 2012.
[7] C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, “Maximizing social influence in nearly optimal time,” Proceedings of the 25th annual ACM-SIAM symposium on Discrete algorithms (SODA’14), pp. 946-957, 2014.
[8] Y. Tang, X. Xiao, and Y. Shi, “Influence Maximization: Near-optimal Time Complexity Meets Practical Efficiency,” Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD’14), pp. 75-86, 2014.
[9] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, “Cost-effective outbreak detection in networks,” Proceedings of the 13th ACM SIGKDD International Conference on Knowledge discovery and data mining (KDD’07), pp. 420-429, 2007.
[10] G. Song, X. Zhou, Y. Wang and K. Xie, “Influence Maximization on Large-Scale Mobile Social Network: A Divide-and-Conquer Method,” IEEE Transactions on Parallel and Distributed System (TPDS), vol. 26, issue 5, pp. 1379-1392,2015.
[11] A. Khan, “Towards Time-Discounted Influence Maximization,” Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM’16), pp.1873-1876, 2016.
[12] D. Liben-Nowell, and J. Kleinbergm, “The Link Prediction Problem for Social Networks,” Proceedings of the twelfth International Conference on Information and Knowledge Management (CIKM’03), pp. 556-559, 2003.
[13] M. AI Hasan, V. Chaoji, S. Salem, and M. Zaki, “Link Prediction using Supervised Learning,” In Proceedings of the Workshop on Link Discovery: Issues, Approaches and Applications, 2005.
[14] R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla, “New Perspectives and Methods in Link Prediction,” Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data mining (KDD’10), pp. 243-252, 2010.
[15] G. M. Weiss, AT&T Laboratories, Piscataway and NJ, “Mining with rarity: a unifying framework,” ACM SIGKDD Explorations Newsletter- Special issue on learning from imbalanced datasets, vol. 6, issue 1, pp. 7-19, 2004.
[16] S. Feng, X. Chen, G. Cong, Y. Zeng, Y. M. Chee, and Y. Xiang, “Influence Maximization with Novelty Decay in Social Networks,” Proceedings of the 28th AAAI Conference on Artificial Intelligence, 2014.
[17] C. Chang, P. Yang, M. Lyu and K. Chuang, “Influential Sustainability on Social Networks,” 2015 IEEE International Conference on Data Mining (ICDM), 2015.
[18] H. Zhuang, Y. Sun, J. Tang, J. Zhang and X. Sun, “Influence maximization in dynamic social networks,” 2013 IEEE 13th International Conference on Data Mining (ICDM), 2013
[19] F. Lu, W. Zhang, L. Shao, X. Jiang, P. Xu, and H. Jin, “Scalable influence maximization under independent cascade model,” Journal of Network and Computer Applications, vol. 86, issue C, pp. 15-26, 2017.
[20] https://snap.stanford.edu/data/