在社群網路中，影響力最大化是一個重要的議題。當多家公司推出類似的產品或服務時，由於資源有限，公司必須擬定一個策略，盡可能佔據最大的市佔率。在本文中，我們提出了一個通用的決定性網路自適應（DNA）框架來解決多回合多方的影響力最大化問題。為了獲得最大的市佔率，從長遠來看，使用單一策略來決定傳遞種子是不夠的。因為在多回合的過程中，網路狀態會隨著影響力的傳遞情形而變化，因此每一回合的策略需因應網路狀態的變化而改變。DNA框架利用增強式學習以最大化多回合後累積的影響力。此外，學習過程是決定性的，也就是說我們不花時間探索不重要的可能性。我們還進一步設計一個相似度函式來衡量兩個網路的傳遞傾向的相似度，因此可以避免多餘的計算，而直接使用過去生成過的策略。此外，我們提出基於DNA框架的競合策略決策方法，已達到影響力最大化的目的。實驗部份使用模擬生成的資料以及真實的社群網路資料進行評估。實驗結果證實了DNA框架優於現有影響力最大化演算法，在大多數情況下都表現最好。

The influence maximization problem has been considered a vital problem when companies provide similar products or services. Since there are limited resources, companies must determine a strategy to occupy as much market share as possible. In this paper, we propose a general Deterministic Network Adaptive (DNA) framework to solve the multi-round multi-party influence maximization problem. To obtain the most market share, using one single strategy to determine seed nodes is not sufficient in the long term. The reason is that the network status changes during the multi-round procedure. The strategies of selecting seed nodes in each round should depend on the current status of influence diffusion in the network. DNA framework leverages the concept of reinforcement learning to maximize the expected cumulative influence. In addition, the learning process is deterministic, so that we do not spend time exploring the spaces that are less important. We further design a similarity function to measure the similarity between the propagation tendencies of two networks. DNA framework can avoid redundant computation when the networks whose propagation tendency are similar have been trained before. Moreover, we propose the method to make policy decision to maximize the influence spread in coopetition scenario based on DNA framework. The proposed framework is evaluated with synthetic data and real-world data. From the experimental results, DNA framework outperforms the existing works in influence maximization problems. The coopetition policy which is generated by DNA has the best performance in most cases.

[1] P. Domingos and M. Richardson, “Mining the network value of customers,” in ACM SIGKDD international conference on Knowledge discovery and data mining, 2001, pp. 57–66.
[2] M. Richardson and P. Domingos, “Mining knowledge-sharing sites for viral marketing,” in ACM SIGKDD international conference on Knowledge discovery and data mining, 2002, pp. 61–70.
[3] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in ACM SIGKDD international conference on Knowledge discovery and
data mining, 2003, pp. 137–146.
[4] S. Bharathi, D. Kempe, and M. Salek, “Competitive influence maximization in social networks,” in WINE international conference on Internet and network economics, 2007, pp. 306–311.
[5] X. He, G. Song, W. Chen, and Q. Jiang, “Influence blocking maximization in social networks under the competitive linear threshold model,” in SIAM International Conference on Data Mining, 2012, pp. 463–474.
[6] W. Lu, W. Chen, and L. V. Lakshmanan, “From competition to complementarity: Comparative influence diffusion and maximization,” in VLDB Endowment, vol. 9, 2015.
[7] H.-C. Ou, C.-K. Chou, and M.-S. Chen, “Influence maximization for complementary goods: Why parties fail to cooperate?” in ACM International on Conference on Information and Knowledge Management, 2016, pp. 1713–1722.
[8] A. Brandenburgur and B. Nalebuff, “Co-opetition,” in Co-opetition, Crown Business, 1996.
[9] S.-C. Lin, S.-D. Lin, and M.-S. Chen, “A learning-based framework to handle multi-round multi-party influence maximization on social networks,” in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 695–704.
[10] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, pp. 199–208.
[11] W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” in ACM SIGKDD international conference on
Knowledge discovery and data mining, 2010, pp. 1029–1038.
[12] W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximization in social networks under the linear threshold model,” in IEEE International Conference on Data Mining,
2010, pp. 88–97.
[13] A. Borodin, Y. Filmus, and J. Oren, “Threshold models for competitive influence in social networks,” in WINE international conference on Internet and network economics, 2010, pp. 539–550.
[14] C. Budak, D. Agrawal, and A. E. Abbadi, “Limiting the spread of misinformation in social networks,” in International Conference on World Wide, 2011, pp. 665–674.
[15] M. Kimura, K. Saito, and H. Motoda, “Blocking links to minimize contamination spread in a social network,” in ACM TKDD Transactions on Knowledge Discovery from Data, vol. 3, 2009, pp. 9:1–9:23.
[16] R. Sutton and A. Barto, “Reinforcement learning,” in Reinforcement Learning, MIT Press, 1998.
[17] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. Driessche, T. Graepei, and D. Hassabis, “Mastering the game of go without human knowledge,” in Nature 550, 2017, pp. 354–359.
[18] A. Lancichinetti and S. Fortunato, “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,” in Physical Review E80, 016118, 2009.
[19] J. Leskovec, “[online]. available: http://snap.stanford.edu/data/.”