隨著使用智慧型手機的人口快速增長，以及社群網路的蓬勃發展，病毒式行銷 以及社群網路行銷受到許多公司企業的愛戴，行銷人員常常需要尋找社群網路中具有影響力的個體來進行行銷，希望這些具影響力的人能將產品資訊傳遞給周圍的使用者，進而使整體的影響力最大化，如何找到有影響力的種子使用者成為時下熱門的議題，本論文提出了一套以社群結構為基礎的影響力最大化演算法，有效的減少影響力重疊的問題，同時加速演算法的執行，在真實的社群網路實驗結果中證實了此方法不僅能有效的保證結果的準確度，在執行效率以及擴展性上有著優越的表現。

Since the surge of the popularity of social network, recently, there has been a tremendous wave of interest in the investigation of influence maximization problem. Given a social network structure, the problem of influence maximization is to determine a minimum set of nodes that could maximize the spread of influences. Nowadays, due to the dramatic size growing of social network, the efficiency and scalability of algorithms for influence maximization become more and more crucial. Although many recent studies have focused on the problem of influence maximization, these works, in general, are time consuming when a large-scale social network is given. In this paper, by exploiting potential community structure, we develop an efficient algorithm EIM (standing for Efficient Influence Maximization) that reduces the execution time and memory usage while guarantee the accuracy of results. The experimental results on real datasets indicate that our algorithms not only significantly outperform state-of-the-art algorithms in efficiency but also possess graceful scalability.

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       1  
Introduction	1
Chapter 2       5
Preliminaries	5
2.1 Problem Formulation	5
Definition 1 (Social Network)	5
Definition 2 (Influence Maximization Problem)	6
2.2 Reverse Reachable Sampling(RRS)	6
Definition 3 (Reverse Reachable Set)	6
2.3 Tang et.al.’s enhancement on RRS	8
2.4 Observations	9
Chapter 3      11
Related Work	11
3.1 Diffusion Models	11
3.2 Influence Maximization Algorithms	12
Chapter 4               16  
Proposed Solution	16
4.1 Graph partition	16
Definition 4 (Similarities Scores)	17
Definition 5 (Modularity)	18
4.2 Quota Allocation	18
4.3 Seed set generation	20
4.4 Performance Analytics	21
Chapter 5      22  
Experiments	22
5.1 Experiment Settings	22
5.2 Experiment Result	23
Chapter 6  Conclusions	28
Reference	29
 

 
List of Figures 

Fig. 1: An example of Reverse Reachable Sampling	7
Fig. 2: The Algorithm Flow.	16
Fig. 3: Influence spread on Epinions..	23
Fig. 4: Running time on Epinions	24
Fig. 5: Influence spread on DBLP	24
Fig. 6: Running time on DBLP.	25
Fig. 7: Influence spread on LiveJournal.	26
Fig. 8: Running time on LiveJournal	27

  
List of Table 

Tab. 1: Dataset characteristic	22


List of Algorithms 

Algorithm. 1: Quota Allocation	19

[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, no.2,
[2] 	D. Kempe, J. Kleinberg, and E. Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data
[3] 	Domingos. 2005. Mining social networks for viral marketing. IEEE Intell. Syst. 20, 1, 80–93.
[4] 	Domingos and M. Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01). 57–66.
[5] 	Domingos and M. Richardson. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’02).61–70.
[6] 	Gomez-Rodriguez, J. Leskovec, and A. Krause. 2010. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD’10). 1019–1028.
[7] 	Honglei Zhuang. Influence Maximization in Dynamic Social Networks
[8] 	Chayant Tantipathananandh, Tanya Berger-Wolf, David Kempe. A Framework For Community Identification in Dynamic Social Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’07).
[9] 	Guangmo Tong, Student Member, IEEE. Adaptive Influence Maximization in Dynamic Social Networks
[10] 	Su-Chen Lin, Shou-De Lin, Ming-Syan 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).
[11] 	A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model.  In IEEE International Conference on Data Mining, 2011.
[12] 	Wen-Yuan Zhu, Wen-Chih Peng, Ling-Jyh Chen, Kai Zheng and Xiaofang 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).
[13] 	Yu Wang, Gao Cong, Guojie Song, Kunqing Xie. Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD’10).
[14] 	U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. In Phys.Rev.E76, 2007.
[15] 	Brendan Lucier , Joel Oren , Yaron 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).
[16] 	C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, Portland, Oregon, USA
[17] 	Y. Tang, X. Xiao, and Y. Shi. Influence maximization. Near-optimal time complexity meets practical efficiency. In SIGMOD, 2014.
[18] 	Manuel Gomez-Rodriguez. Influence Maximization in Continuous Time Diffusion Networks. In Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012.
[19] 	Yajun Yang, Jeffrey Xu Yu, Hong Gao, Jian Pei, Jianzhong Li. Mining most frequently changing component in evolving graphs. World Wide Web (2014)
[20] 	Yu Yang, Zhefeng Wang, Jian Pei and Enhong Chen. Tracking Influential Nodes in Dynamic Networks
[21] 	ROGERS. 2003. Diffusion of Innovations. 5th Ed., Free Press, New York, NY.
[22] 	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.
[23] 	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.
[24] 	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.
[25] 	Valente. 1995. Network Models of the Diffusion of Innovations. Hampton Press.
[26] 	Young. 2000. The diffusion of innovations in social networks. Economics Working Paper 437, Johns Hopkins University.
[27] 	Myers and J. Leskovec. 2010. On the convexity of latent social network inference. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS’10). 1741–1749.
[28] 	Wang and X. Feng. 2009. A potential-based node selection strategy for influence maximization in a social network. In Proceedings of the 5th International Conference on Advanced Data Mining and Applications (ADMA’09). 350–361.
[29] 	https://snap.stanford.edu/data/