由於社群網路日漸普遍，這也引起了學術界對尋找影響力最大化問題的風潮。最早的影響力最大化問題是由Kempe.Kleinberg和Tardosy在2003提出。給定一個社群網路G和常數k，在G中找出k個點，可以在擴散模型下去影響最多的使用者。由於社群網路越來越龐大，先前的演算法在這種情形下，不論在IC或LT 模型都需耗費較多的時間來執行，而且這些演算法並沒有良好的可擴展性。本篇方法透過給定邊一個確定性的值(α)，並開發出一個有效率的演算法，不但可以減少執行所需要的時間，同時也保證結果的準確性，並且在實驗結果上表明，我們的演算法優於先前的演算法，並且具有良好的可擴展性。

The Social Network is becoming more and more common. This has also caused the wave to find influence maximization problem by the academic community. The earliest Influence maximization problem was proposed by Kempe.Kleinberg and Tardosy in 2003. Given a social network G and a constant k, finding k nodes in G which can influence most nodes in the diffusion model. As the Social Network is getting larger, the previous algorithms in this case, whether in the IC or the LT Model, take more time to execute, and these algorithms do not have good Scalability. The method in this paper given a deterministic value for edges and develops an efficient algorithm. It not only can reduce the time required for implementation, but also ensures the accuracy of results. And the experimental results show that our algorithm is better than the previous algorithm, and has good scalability.

Table of Contents
Chapter 1	1
Introduction	1
Chapter 2	5
Preliminaries	5
2.1 Problem Formulation	5
2.2 Reverse Reachable Sampling(RRS)	7
2.3 Tang et.al.’s enhancement on RRS	9
2.4 Chen et al.’s MIA Model	11
2.5 Observations	12
Chapter 3	14
Related Work	14
3.1 Diffusion Models	14
3.2 Influence Maximization Algorithms	15
Chapter 4	17
Proposed Solution	17
4.1 Graph partition	18
4.2 Quota Allocation	20
4.3 Calculateα	22
4.4 Seed Set Generation	23
Chapter 5	25
Experiments	25
5.1 Experiment Settings	25
5.2 Experiment Result	26
Chapter 6	31
Conclusions	31
References	32

List of Figures 

FIGURE 1：CASES OF REVERSE REACHABLE SAMPLES	8
FIGURE 2：THE ALGORITHM FLOW.	17
FIGURE 3：RUNNING TIME VS. K ON EMAIL-EU-CORE.	26
FIGURE 4：RUNNING TIME VS. K ON EPINIONS.	28
FIGURE 5：RUNNING TIME VS. K ON YOUTUBE.	29

List of Table

TABLE 1：PROPERTIES OF SOCIAL NETWORK DATASETS	26
TABLE 2：RUNNING TIME ON EMAIL-EU-CORE	27
TABLE 3：INFLUENCE SPREAD ON EMAIL-EU-CORE	27
TABLE 4：RUNNING TIME ON EPINIONS	28
TABLE 5：INFLUENCE SPREAD ON EPINIONS	28
TABLE 6：RUNNING TIME ON YOUTUBE	29
TABLE 7：INFLUENCE SPREAD ON YOUTUBE	30

List of Algorithm

Algorithm 1 : Quota Allocation	21
Algorithm 2 : ap(u,S,MIIA(v,θ))	22
Algorithm 3 : Compute α(v,u)	22
Algorithm 4 : Proposed	24

[1] 	D. Kempe, J. M. Kleinberg, and É. Tardos. “Maximizing the spread of influence through a social network”. In KDD, pages 137–146, 2003.
[2] 	S.C Lin, S.D Lin, M.S Chen. “A Learning-based 
Framework to Handle Multi-round Multi-party Influence Maximization on Social Networks”. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15).
[3] 	W.Y Zhu, W.C Peng, L.J Chen, K. Zheng and X. Zhou. “Modeling User Mobility for Location Promotion in Location-based Social Networks”.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15).
[4] 	B. Lucier , J. Oren , Y. Singer. “Influence at Scale: Distributed Computation of Complex Contagion in Networks”. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’15).
[5] 	Y. Yang, Z. Wang, J. Pei, E. Chen."Tracking influential nodes in dynamic networks",Proceedings of the 2015 SIAM international conference on data mining, Canada, Vancouver (2015).
[6] 	C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. “Maximizing social influence in nearly optimal time”. In SODA, Portland, Oregon, USA.
[7] 	Y. Tang, X. Xiao, and Y. Shi. “Influence maximization. Near-optimal time complexity meets practical efficiency”. In SIGMOD, 2014.
[8] 	Estevez, P. Vera, and K. Saito. 2007. “Selecting the most influential nodes in social network”. In Proceedings of the International Joint Conference on Neural Networks (IJCNN’07). 2397–2402.
[9] 	Goldenberg, B. Libai, and E. Muller. 2001. “Talk of network: A complex systems look at the underlying process of word-of-mouth”. Market. Lett. 12, 3, 211–223.
[10] 	Ma, H. Yang, M. Lyu, and I. King. 2008. “Mining social networks using heat diffusion processes for marketing candidates selection”. In Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM’08). 233–242.
[11] 	Valente. 1995. “Network Models of the Diffusion of Innovations”. Hampton Press, 2015.
[12] 	H. P Young. “The diffusion of innovation in social networks”. Sante Fe Institute Working Paper 02-04-018, 2002. ROGERS. 2003. Diffusion of Innovations. 5th Ed., Free Press, New York, NY.
[13] 	M. Kimura and K. Saito. “Tractable models for information diffusion in social networks”. In Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 259–271, 2006.
[14] 	W. Chen , Y. Wang , S. Yang, “Efficient influence maximization in social networks”, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
[15] 	W. Chen, C. Wang, Y. Wang, “Scalable influence maximization for prevalent viral marketing in large scale social networks”, KDD, 2010.
[16] 	C. Long , Raymond C.W Wong, “Minimizing Seed Set for Viral Marketing”, Proceedings of the 2011 IEEE 11th International Conference on Data Mining, p.427-436, December 11-14, 2011
[17] 	P. Zhang, W. Chen, X. Sun, Y. Wang, J. Zhang, “Minimizing seed set selection with probabilistic coverage guarantee in a social network”, KDD, pp. 1306-1315, 2014.
[18] 	A. Goyal, F. Bonchi, L. V. S. Lakshmanan, and S. Venkatasubramanian. “On minimizing budget and time in influence propagation over social networks”. Social Network Analysis and Mining, 2(1), 2012.
[19] 	Zheng, D., Liu, J., Li, R., Aslay, Ç., Chen, Y., Huang, X.: “Querying intimate-core groups in weighted graphs”. In: 11th IEEE International Conference on Semantic Computing, ICSC 2017, San Diego, CA, USA, 30 January–1 February 2017 (2017)
[20] 	J. Leskovec , A. Krause , C. Guestrin , C. Faloutsos , J. VanBriesen , N. Glance, “Cost-effective outbreak detection in networks”, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA 
[21] 	Z. Yu et al., “Who should I invite for my party?: Combining user preference and influence maximization for social events”, Proc. ACM Int. Joint Conf. Pervasive Ubiquitous Comput., pp. 879-883, 2015.
[22] 	A. Goyal, F. Bonchi, L. V. Lakshmanan, “A data-based approach to social influence maximization”, PVLDB, 2012.
[23] 	https://snap.stanford.edu/data/