線上社交網路的蓬勃發展讓人們很容易分享自己的意見和觀點，但也引發一些負面影響。有些人利用社交網路散播負面思想，阻礙社會發展。為了對抗這些影響，有學者利用正向影響支配集方法尋找關鍵節點並採取相應的措施，遏止負面影響的擴散。

過去正向影響支配集的研究主要是針對無向社交網路，並且以節點的分支度決定節點是否加入正向影響支配集。但是現實中社交網路平台的用戶之間存在有向關係，使得許多社交網路沒辦法使用正向影響支配集演算法來尋找關鍵節點，因此本研究提出一個尋找有向社交網路圖中正向影響支配集的方法。首先，透過預處理事先將部分特徵明顯顯示必須加入正向影響支配集的節點固定下來。接著不同於過去方法，本研究使用新的節點排序方式，並且依節點的被需求程度定義新的衡量標準來決定節點是否加入正向影響支配集，使節點的選擇可以更貼近節點的需求。最後，以頻繁出現的節點為基礎再繼續後續迭代搜尋動作，使本篇論文有別與以往單純重複迭代搜尋，可以讓下一次產生的結果吸取前幾次迭代的優點，提升搜尋的準確度。

根據實驗的分析，證實本研究的方法在無向社交網路中可以有效的縮短正向影響支配集的長度高達6%，在有向社交網路中相較於過去的方法更能夠找到縮小20%的正向影響支配集。

The flourishing development of online social networks has made it easy for people to share their opinions and perspectives, but it has also led to some negative impacts. Some individuals utilize social networks to spread negative ideas, hindering societal progress. To combat these influences, scholars have employed the Positive Influence Dominating Set (PIDS) to identify critical vertices and take appropriate measures to curtail the spread of negativity.

Previous research on PIDS primarily focused on undirected social networks, deciding whether to join the PIDS according to the degree of the vertex. However social networks often involve directed relationships among users, making it challenging to apply PIDS algorithm to identify critical vertices. Therefore, this study proposes an algorithm to identify the PIDS in directed social networks. Firstly, a preprocessing step is conducted to predefine certain vertices that must be included in the PIDS based on specific characteristics. Subsequently, unlike previous approaches, this study introduces a new vertex sorting method and defines a new measure of vertex demand to determine vertex inclusion in the PIDS, aiming to better align with the needs of individual vertices. Finally, the iteration search process is based on frequently occurring vertices, which allows the subsequent iterations to incorporate the advantages of previous iterations, enhancing the accuracy of the search.

Experimental analysis confirms that the proposed method in this study effectively reduces the length of the PIDS by up to 6% in undirected social networks, and in directed social networks, it outperforms previous methods by achieving a reduction of up to 20% in the PIDS.

[1] F. N. Abu-Khzam and K. Lamaa, "Efficient heuristic algorithms for positive-influence dominating set in social networks," in IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 610-615, 2018.
[2] S. Bouamama and C. Blum, "An improved greedy heuristic for the minimum positive influence dominating set problem in social networks”, Algorithms, Vol. 14, No. 3, pp. 79, 2021.
[3] S. Bouamama, C. Blum, and J.-G. Fages, "An algorithm based on ant colony optimization for the minimum connected dominating set problem”, Applied Soft Computing, Vol. 80, pp. 672-686, 2019.
[4] D. Chalupa, "An order-based algorithm for minimum dominating set with application in graph mining”, Information Sciences, Vol. 426, pp. 101-116, 2018.
[5] J. Chen, S. Cai, Y. Wang, W. Xu, J. Ji, and M. Yin, "Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism”, Artificial Intelligence, Vol. 314, pp. 103819, 2023.
[6] F. Dai and J. Wu, "An extended localized algorithm for connected dominating set formation in ad hoc wireless networks”, IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 10, pp. 908-920, 2004.
[7] M. M. Daliri Khomami, A. Rezvanian, N. Bagherpour, and M. R. Meybodi, "Minimum positive influence dominating set and its application in influence maximization: a learning automata approach”, Applied Intelligence, Vol. 48, pp. 570-593, 2018.
[8] E. DeLaViña, W. Goddard, M. A. Henning, R. Pepper, and E. R. Vaughan, "Bounds on the k-domination number of a graph”, Applied Mathematics Letters, Vol. 24, No. 6, pp. 996-998, 2011.
[9] M. Fei and C. Weidong, "An improved algorithm for finding minimum positive influence dominating sets in social networks”, 华南师范大学学报 (自然科学版), Vol. 48, No. 3, pp. 59-63, 2016.
[10] M. Girvan and M. E. Newman, "Community structure in social and biological networks”, Proceedings of the National Academy of Sciences, Vol. 99, No. 12, pp. 7821-7826, 2002.
[11] M. Gong, C. Song, C. Duan, L. Ma, and B. Shen, "An efficient memetic algorithm for influence maximization in social networks”, IEEE Computational Intelligence Magazine, Vol. 11, No. 3, pp. 22-33, 2016.
[12] D. Günneç, S. Raghavan, and R. Zhang, "Least-cost influence maximization on social networks”, INFORMS Journal on Computing, Vol. 32, No. 2, pp. 289-302, 2020.
[13] M. A. Henning, "Dominator and total dominator colorings in graphs”, Structures of Domination in Graphs, pp. 101-133, 2021.
[14] J. Kazemi Kordestani, M. Razapoor Mirsaleh, A. Rezvanian, and M. R. Meybodi, "An Introduction to Learning Automata and Optimization," in Advances in Learning Automata and Intelligent Optimization, pp. 1-50, 2021.
[15] J. Kunegis, "KONECT: the Koblenz network collection," in Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil, 2013.
[16] J. Leskovec and A. Krevl, "SNAP Datasets: Stanford large network dataset collection," ed: Ann Arbor, MI, USA, 2014.
[17] R. Li, S. Hu, P. Zhao, Y. Zhou, and M. Yin, "A novel local search algorithm for the minimum capacitated dominating set”, Journal of the Operational Research Society, Vol. 69, No. 6, pp. 849-863, 2018.
[18] G. Lin, J. Guan, and H. Feng, "An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks”, Physica A: Statistical Mechanics and its Applications, Vol. 500, pp. 199-209, 2018.
[19] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, "The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait?”, Behavioral Ecology and Sociobiology, Vol. 54, pp. 396-405, 2003.
[20] P. Moscato, "On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms”, Caltech Concurrent Computation Program, C3P Report, Vol. 826, No. 1989, pp. 37, 1989.
[21] J. Pan and T.-M. Bu, "A fast greedy algorithm for finding minimum positive influence dominating sets in social networks," in IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 360-364, 2019.
[22] S. Pan et al., "An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem”, Frontiers of Computer Science, Vol. 17, No. 4, pp. 174326, 2023.
[23] H. Raei, N. Yazdani, and M. Asadpour, "A new algorithm for positive influence dominating set in social networks," in 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 253-257, 2012.
[24] Y. Ran, Z. Zhang, H. Du, and Y. Zhu, "Approximation algorithm for partial positive influence problem in social network”, Journal of Combinatorial Optimization, Vol. 33, pp. 791-802, 2017.
[25] R. Rossi and N. Ahmed, "The network data repository with interactive graph analytics and visualization," in Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 29, No. 1, 2015.
[26] C. Shen and T. Li, "Multi-document summarization via the minimum dominating set," in Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pp. 984-992, 2010.
[27] F. Wang, E. Camacho, and K. Xu, "Positive Influence Dominating Set in Online Social Networks”, International Conference on Combinatorial Optimization and Applications (COCOA), Vol. 9, pp. 313-321, 2009.
[28] X. Yao, H. Huang, and H. Du, "Connected positive influence dominating set in k-regular graph”, Discrete Applied Mathematics, Vol. 287, pp. 65-76, 2020.