影響最大化係指於給定社群網路中識別預定數量之種子點，透過選定的種子點，其目在於最大化影響力的傳播。雖然這個問題在過去已經被廣泛的研究，然而，之前的研究大多在非極性網路下探討這個問題，這意味著極性關係仍然在很大的程度上被忽略。而於極性網路中基於正負面關係的影響力最大化問題依舊存在著許多挑戰。在本研究中，我們對極性感知影響力最大化問題進行定義，該問題涉及了種子點的識別，其中種子點將同時最大化正面影響力並最小化負面影響力。透過結合二元意見和極性關係兩項重要的特徵，我們對經典獨立串聯模型進行擴增，此外，更針對極性感知競爭影響力模型(SCIC)探討不同主宰機制下的競爭型態影響力傳遞。而後，我們證明了極性感知影響力最大化問題(SIM)於極性感知獨立串連模型下具有非單調性及非子模性的特性，基於這項證明，貪婪爬山演算法在解決極性感知影響力最大化問題時將無法達到達到 $1-1/e$ 的近似最佳解的保證，這也凸顯出了在這個問題下效率及效能間的取捨。為了解決這個問題，我們接著提出了極性感知競爭影響力最大化樹突 (S-CMIA) 演算法，該演算法透過模擬局部區域內的影響力傳播來衡量每個節點的重要性。實驗結果證明了在解決極性感影響力最大化問題時我們所提出的演算法優於現存方法。

Influence maximization refers to the process of identifying a predefined number of nodes within a given social network with the aim of maximizing the spread of influence. This problem has been widely studied; however, most previous work has focused on unsigned networks, which means the existence of polarity relationships has largely been disregarded. Influence maximization based on positive and negative relationships in signed networks still poses many challenges. In this paper, we define a Sign-aware Influence Maximization (SIM) problem, which involves identification of the seed set that would simultaneously maximize positive influence and minimize negative influence. We begin by considered competitive influence under various dominance mechanisms on SCIC model, which extends the classic Independent Cascade (IC) model by incorporating binary opinions and signed relationships. We then proved that the influence of SIM under the SCIC model is non-monotonic and non-submodular, which implies that simple greedy hill-climbing would be unable to achieve an approximation ratio of $1-1/e$ in seeking to resolve the SIM problem. This indicates a trade off between efficiency and effectiveness. We then developed a simulation-based algorithm called Sign-aware Competitive Maximum Influence Arborescence (S-CMIA) to simulate the propagation of influence within a local region. Experiment results demonstrate the superiority of the proposed algorithm over existing methods in resolving the SIM problem in terms of reward

[1] P. Domingos and M. Richardson, “Mining the network value of customers,” in Proceedings
of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining. ACM Press, 2001, pp. 57–66.
[2] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a
social network,” in KDD ’03, 2003.
[3] W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral
marketing in large-scale social networks.” in KDD, B. Rao, B. Krishnapuram, A. Tomkins,
and Q. Yang, Eds. ACM, 2010, pp. 1029–1038.
[4] W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximization in social networks
under the linear threshold model.” in ICDM, G. I. Webb, B. Liu, C. Zhang, D. Gunopulos,
and X. Wu, Eds. IEEE Computer Society, 2010, pp. 88–97.
[5] Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang, “Influence diffusion dynamics and influence
maximization in social networks with friend and foe relationships,” CoRR, vol.
abs/1111.4729, 2011.
[6] A. Srivastava, C. Chelmis, and V. K. Prasanna, “Social influence computation and maximization
in signed networks with competing cascades.” in ASONAM, J. Pei, F. Silvestri,
and J. Tang, Eds. ACM, 2015, pp. 41–48.
[7] W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rinc´on, X. Sun, Y. Wang, W. Wei,
and Y. Yuan, “Influence maximization in social networks when negative opinions may
emerge and propagate.” in SDM. SIAM / Omnipress, 2011, pp. 379–390.
[8] D. Li, C. Wang, S. Zhang, G. Zhou, D. Chu, and C. Wu, “Positive influence maximization
in signed social networks based on simulated annealing.” Neurocomputing, vol. 260, pp.
69–78, 2017.
[9] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance,
“Cost-effective outbreak detection in networks.” in KDD, P. Berkhin, R. Caruana, and
X. Wu, Eds. ACM, 2007, pp. 420–429.
[10] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in
KDD, 2009, pp. 199–208.
[11] J. Kim, S.-K. Kim, and H. Yu, “Scalable and parallelizable processing of influence maximization
for large-scale social networks?” in ICDE, C. S. Jensen, C. M. Jermaine, and
X. Zhou, Eds. IEEE Computer Society, 2013, pp. 266–277.
[12] S. Cheng, H. Shen, J. Huang, W. Chen, and X. Cheng, “Imrank: influence maximization
via finding self-consistent ranking.” in SIGIR, S. Geva, A. Trotman, P. Bruza, C. L. A.
Clarke, and K. J¨arvelin, Eds. ACM, 2014, pp. 475–484.
[13] A. Goyal, W. Lu, and L. V. S. Lakshmanan, “Simpath: An efficient algorithm for influence
maximization under the linear threshold model.” in ICDM, D. J. Cook, J. Pei, W. Wang,
O. R. Za¨ıane, and X. Wu, Eds. IEEE Computer Society, 2011, pp. 211–220.
[14] A. Bozorgi, H. Haghighi, M. S. Zahedi, and M. Rezvani, “Incim: A community-based algorithm
for influence maximization problem under the linear threshold model.” Inf. Process.
Manage., vol. 52, no. 6, pp. 1188–1199, 2016.
[15] X. He, G. Song, W. Chen, and Q. Jiang, “Influence blocking maximization in social networks
under the competitive linear threshold model.” in SDM. SIAM / Omnipress, 2012,
pp. 463–474.
[16] P. Wu and L. Pan, “Scalable influence blocking maximization in social networks under
competitive independent cascade models.” Computer Networks, vol. 123, pp. 38–50, 2017.
[17] S. Chen and K. He, “Influence maximization on signed social networks with integrated
pagerank.” in SmartCity. IEEE Computer Society, 2015, pp. 289–292.
[18] D. Li, Z.-M. Xu, N. Chakraborty, A. Gupta, K. Sycara, and S. Li, “Polarity related
influence maximization in signed social networks,” PLOS ONE, vol. 9, no. 7, pp. 1–12, 07
2014.
[19] M. Hosseini-Pozveh, K. Zamanifar, A. R. Naghsh-Nilchi, and P. Dolog, “Maximizing the
spread of positive influence in signed social networks.” Intell. Data Anal., vol. 20, no. 1,
pp. 199–218, 2016.
[20] C. Shen, R. Nishide, I. Piumarta, H. Takada, and W. Liang, “Influence maximization in
signed social networks.” in WISE (1), ser. Lecture Notes in Computer Science, J. Wang,
W. Cellary, D.Wang, H.Wang, S.-C. Chen, T. Li, and Y. Zhang, Eds., vol. 9418. Springer,
2015, pp. 399–414.
[21] N. P. Nguyen, G. Yan, M. T. Thai, and S. Eidenbenz, “Containment of
misinformation spread in online social networks.” in WebSci, N. S. Contractor, B. Uzzi,
M. W. Macy, and W. Nejdl, Eds. ACM, 2012, pp. 213–222. [Online]. Available:
http://dblp.uni-trier.de/db/conf/websci/websci2012.html#NguyenYTE12
[22] C. Budak, D. Agrawal, and A. E. Abbadi, “Limiting the spread of misinformation
in social networks.” in WWW, S. Srinivasan, K. Ramamritham, A. Kumar, M. P.
Ravindra, E. Bertino, and R. Kumar, Eds. ACM, 2011, pp. 665–674. [Online]. Available:
http://dblp.uni-trier.de/db/conf/www/www2011.html#BudakAA11
[23] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for
maximizing submodular set functions—i,” Mathematical Programming, vol. 14, no. 1, pp.
265–294, Dec 1978.
[24] C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier, “Maximizing social influence in
nearly optimal time.” in SODA, C. Chekuri, Ed. SIAM, 2014, pp. 946–957. [Online].
Available: http://dblp.uni-trier.de/db/conf/soda/soda2014.html#BorgsBCL14
[25] W. Liu, X. Chen, B. Jeon, L. Chen, and B. Chen, “Influence maximization on signed
networks under independent cascade model.” Appl. Intell., vol. 49, no. 3, pp. 912–928,
2019.
[26] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing
order to the web,” Stanford Digital Library Technologies Project, Tech. Rep., 1998.