Community-Detection-Based Influence Blocking Maximization Algorithm in Social Network

doi:10.3969/j.issn.1671-1122.2023.01.006

Abstract

Abstract:

With the increasing popularity of social networks, social networks have become the main platform for information dissemination. The relative difficulty of regulating the content of social networks has led to some negative messages spreading easily and producing large adverse effects. The influence blocking maximization aims to find the set of nodes that need to adopt positive influence to minimize the number of nodes affected by negative messages in the process of information dissemination. To address the problem of high running time complexity of existing social network influence blocking algorithms, in this paper, we proposed an influence blocking maximization algorithm based on community detection, which first utilized the extended h-index centrality of social network nodes to select candidate seed nodes, and then used these seed nodes as the starting point to discover communities in social networks with a label propagation algorithm, followed by calculating the social network communities by of the relationship matrix and the modularity of the current relationship matrix to merge the communities, and finally, the labeling metric rank of the initial seed nodes was calculated and the top k nodes were selected as the members with the maximum blocking influence. The experimental results show that the algorithm has good blocking performance and low time complexity.

Key words: influence blocking, community detection, label propagation, community merging

CLC Number:

TP309

MU Zhiying, XU Jiaquan, LI Xiaoyu. Community-Detection-Based Influence Blocking Maximization Algorithm in Social Network[J]. Netinfo Security, 2023, 23(1): 44-56.

Figures/Tables 9

References 39

[1]	KEMPE D, KLEINBERG J, TARDOS É. Maximizing the Spread of Influence Through a Social Network[C]// ACM. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146.
[2]	HE X, SONG G, CHEN W, et al. Influence Blocking Maximization in Social Networks Under the Competitive Linear Threshold Model[C]// SIAM. Proceedings of the 2012 Siam International Conference on Data Mining. New York: SIAM, 2012: 463-474.
[3]	CHEN W, YUAN Y, ZHANG L. Scalable Influence Maximization in Social Networks Under the Linear Threshold Model[C]// IEEE. 2010 IEEE International Conference on Data Mining. New York: IEEE, 2010: 88-97.
[4]	BORGS C, BRAUTBAR M, CHAYES J, et al. Maximizing Social Influence in Nearly Optimal Time[C]// ACM. Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2014: 946-957.
[5]	TANG Y, XIAO X, SHI Y. Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency[C]// ACM. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2014: 75-86.
[6]	NGUYEN H T, THAI M T, DINH T N. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-Scale Networks[EB/OL]. [2022-06-20]https://dblp.uni-trier.de/rec/journals/corr/NguyenTD16.html.
[7]	BU Z, ZHANG C, XIA Z, et al. A Fast Parallel Modularity Optimization Algorithm (FPMQA) for Community Detection in Online Social Network[J]. Knowledge-Based Systems, 2013, 50: 246-259. doi: 10.1016/j.knosys.2013.06.014 URL
[8]	DOMINGOS P, RICHARDSON M. Mining the Network Value of Customers[C]// ACM. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2001: 57-66.
[9]	CHEN W, LAKSHMANAN L V S, CASTILLO C. Information and Influence Propagation in Social Networks[J]. Synthesis Lectures on Data Management, 2013, 5(4): 170-177.
[10]	CHEN W, COLLINS A, CUMMINGS R, et al. Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate[C]// SIAM. Proceedings of the 2011 Siam International Conference on Data Mining. Society for Industrial and Applied Mathematics. New York: SIAM, 2011: 379-390.
[11]	CARNES T, NAGARAJAN C, WILD S M, et al. Maximizing Influence in a Competitive Social Network: A Follower’s Perspective[EB/OL]. [2022-06-25]. http://www.xueshufan.com/publication/2105509646.
[12]	GOMEZ-RODRIGUEZ M, BALDUZZI D, SCHÖLKOPF B. Uncovering the Temporal Dynamics of Diffusion Networks[EB/OL]. [2022-06-28]. https://ui.adsabs.harvard.edu/abs/2011arXiv1105.0697G/abstract.
[13]	GOMEZ-RODRIGUEZ M, SCHOLKOPF B. Inf luence Maximization in Continuous Time Diffusion Networks[C]// ACM. Proceedings of the 29th International Conference on Machine Learning. New York: ACM, 2012: 313-320.
[14]	DU N, SONG L, GOMEZ-RODRIGUEZ M, et al. Scalable Influence Estimation in Continuous-Time Diffusion Networks[J]. Advances in Neural Information Processing Systems, 2013, 26: 3147-3155. pmid: 26752940
[15]	SAITO K, KIMURA M, OHARA K, et al. Selecting Information Diffusion Models over Social Networks for Behavioral Analysis[C]// Springer. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2010: 180-195.
[16]	GOMEZ-RODRIGUEZ M, SONG L, DU N, et al. Influence Estimation and Maximization in Continuous-Time Diffusion Networks[J]. ACM Transactions on Information Systems (TOIS), 2016, 34(2): 1-33.
[17]	NEWMAN M E J. Spread of Epidemic Disease on Networks[J]. Physical Review E, 2002, 66(1): 180-195.
[18]	LI Y, CHEN W, WANG Y, et al. Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships[C]// ACM. Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. New York: ACM, 2013: 657-666.
[19]	CLARK A, POOVENDRAN R. Maximizing Influence in Competitive Environments: A Game-Theoretic Approach[C]// Springer. International Conference on Decision and Game Theory for Security. Berlin: Springer, 2011: 151-162.
[20]	WANG F, JIANG W, LI X, et al. Maximizing Positive Influence Spread in Online Social Networks via Fluid Dynamics[J]. Future Generation Computer Systems, 2018, 86: 1491-1502. doi: 10.1016/j.future.2017.05.050 URL
[21]	RAGHAVAN U N, ALBERT R, KUMARA S. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J]. Physical Review E, 2007, 76(3): 106-117.
[22]	ZHAO Y, LI S, JIN F. Identification of Influential Nodes in Social Networks with Community Structure Based on Label Propagation[J]. Neurocomputing, 2016, 210: 34-44. doi: 10.1016/j.neucom.2015.11.125 URL
[23]	SALAVATI C, ABDOLLAHPOURI A, MANBARI Z. Ranking Nodes in Complex Networks Based on Local Structure and Improving Closeness Centrality[J]. Neurocomputing, 2019, 336: 36-45. doi: 10.1016/j.neucom.2018.04.086 URL
[24]	BERAHMAND K, BOUYER A, SAMADI N. A New Local and Multidimensional Ranking Measure to Detect Spreaders in Social Networks[J]. Computing, 2019, 101(11): 1711-1733. doi: 10.1007/s00607-018-0684-8 URL
[25]	RUI X, MENG F, WANG Z, et al. A Reversed Node Ranking Approach for Influence Maximization in Social Networks[J]. Applied Intelligence, 2019, 49(7): 2684-2698. doi: 10.1007/s10489-018-01398-w URL
[26]	WEN T, DENG Y. Identification of Influencers in Complex Networks by Local Information Dimensionality[J]. Information Sciences, 2020, 512: 549-562. doi: 10.1016/j.ins.2019.10.003 URL
[27]	HUANG H, SHEN H, MENG Z, et al. Community-Based Influence Maximization for Viral Marketing[J]. Applied Intelligence, 2019, 49(6): 2137-2150. doi: 10.1007/s10489-018-1387-8
[28]	BHARATHI S, KEMPE D, SALEK M. Competitive Influence Maximization in Social Networks[C]// Springer. International Workshop on Web and Internet Economics. Berlin: Springer, 2007: 306-311.
[29]	HIRSCH J E. An Index to Quantify an Individual's Scientific Research Output[J]. Proceedings of the National Academy of Sciences, 2005, 102(46): 16569-16572. doi: 10.1073/pnas.0507655102 URL
[30]	LÜ L, ZHOU T, ZHANG Q M, et al. The H-Index of a Network Node and Its Relation to Degree and Coreness[J]. Nature Communications, 2016, 7(1): 1-7.
[31]	LIU Q, ZHU Y X, JIA Y, et al. Leveraging Local H-Index to Identify and Rank Influential Spreaders in Networks[J]. Physica A: Statistical Mechanics and its Applications, 2018, 512: 379-391. doi: 10.1016/j.physa.2018.08.053 URL
[32]	ZAREIE A, SHEIKHAHMADI A. EHC: Extended H-Index Centrality Measure for Identification of Users’ Spreading Influence in Complex Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2019, 514: 141-155. doi: 10.1016/j.physa.2018.09.064 URL
[33]	RUI X, YANG X, FAN J, et al. A Neighbour Scale Fixed Approach for Influence Maximization in Social Networks[J]. Computing, 2020, 102(2): 427-449. doi: 10.1007/s00607-019-00778-5 URL
[34]	LI X, ZHOU S, LIU J, et al. Communities Detection in Social Network Based on Local Edge Centrality[EB/OL]. [2022-06-25]. https://www.sciencedirect.com/science/article/abs/pii/S0378437119309173.
[35]	NEWMAN M E. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582. doi: 10.1073/pnas.0601602103 URL
[36]	NGUYEN H T, THAI M T, DINH T N. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-Scale Networks[EB/OL]. [2022-06-29]. https://xueshu.baidu.com/usercenter/paper/show?paperid=cead64288e71fe041608ecc9cd3a6d8e.
[37]	ARAZKHANI N, MEYBODI M R, REZVANIAN A. Influence Blocking Maximization in Social Network Using Centrality Measures[C]// IEEE. 2019 5th Conference on Knowledge Based Engineering and Innovation (KBEI). New York: IEEE, 2019: 492-497.
[38]	SU S, LI X, CHENG X, et al. Location-Aware Targeted Influence Maximization in Social Networks[J]. Journal of the Association for Information Science and Technology, 2018, 69(2): 229-241. doi: 10.1002/asi.23931 URL
[39]	PAGE L, BRIN S, MOTWANI R, et al. The PageRank Citation Ranking: Bringing Order to the Web[M]. Stanford: Stanford InfoLab, 1999.

数据集名称	节点数/个	边数/条	平均度数
Football	115	613	10.7
Jazz Musicians	198	2742	27.7
C.Elegans	297	2148	14.5
Facebook	4039	88234	43.7
p2p-Gnutella08	6301	20777	6.6