[Objective] This paper proposes IMtoc model to maximize influences with the help of overlapping community structure, aiming to quickly identify the most influential nodes in the social networks. [Methods] First, we divided the whole social network into several overlapping communities. Then, we selected the candidates from the nodes with the largest feature vector centrality and the overlapping ones. Finally, we identified the optimal nodes from the candidates with greedy algorithm. [Results] We examined the proposed IMtoc algorithm model with the large social network Git_web_ml dataset. Its running speed was about 91% and 65% faster than the CELF and IMRank algorithms. [Limitations] There is a large overlap between the influential nodes and overlapping nodes. [Conclusions] The IMtoc algorithm could more effectively identify influencing nodes in social networks.
王烨桐, 江涛. 通过重叠社区结构识别社交网络中的影响力节点*[J]. 数据分析与知识发现, 2022, 6(12): 80-89.
Wang Yetong, Jiang Tao. Identifying Influential Nodes in Social Networks by Overlapping Community Structure. Data Analysis and Knowledge Discovery, 2022, 6(12): 80-89.
(Duan Jinfa, Zou Qianyou, Fu Songtao. Research on Propagation Model Analysis and Application[J]. Journal of Information Engineering University, 2020, 21(2): 172-181.)
[2]
Bajpai P, Singh A, Shankhwar A K. Performance Analysis of Neighbour Centrality Method Based Rumor Spread Control with Variable Spreading Rate[C]// Proceedings of the 2019 International Conference on Electrical, Electronics and Computer Engineering. IEEE, 2019: 1-6.
[3]
Hu X H, Xiang Y, Li Y F, et al. Trident: Efficient and Practical Software Network Monitoring[J]. Tsinghua Science and Technology, 2021, 26(4): 452-463.
doi: 10.26599/TST.2020.9010018
[4]
Chang B, Xu T, Liu Q, et al. Study on Information Diffusion Analysis in Social Networks and Its Applications[J]. International Journal of Automation and Computing, 2018, 15(4): 377-401.
doi: 10.1007/s11633-018-1124-0
[5]
Domingos P, Richardson M. Mining the Network Value of Customers[C]// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2001: 57-66.
[6]
Kempe D, Kleinberg J, Tardos É. Maximizing the Spread of Influence Through a Social Network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2003: 137-146.
[7]
Leskovec J, Krause A, Guestrin C, et al. Cost-Effective Outbreak Detection in Networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2007: 420-429.
[8]
Chen W, Wang Y J, Yang S Y. Efficient Influence Maximization in Social Networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2009: 199-208.
[9]
Liu W, Li Y, Chen X, et al. Maximum Likelihood-Based Influence Maximization in Social Networks[J]. Applied Intelligence, 2020, 50(10): 3487-3502.
doi: 10.1007/s10489-020-01747-8
[10]
Samadi N, Bouyer A. Identifying Influential Spreaders Based on Edge Ratio and Neighborhood Diversity Measures in Complex Networks[J]. Computing, 2019, 101(8): 1147-1175.
doi: 10.1007/s00607-018-0659-9
[11]
Ahajjam S, Badir H. Identification of Influential Spreaders in Complex Networks Using HybridRank Algorithm[J]. Scientific Reports, 2018, 8: 11932.
doi: 10.1038/s41598-018-30310-2
pmid: 30093716
[12]
Li X H, Guo J Y, Gao C, et al. A Hybrid Strategy for Network Immunization[J]. Chaos, Solitons & Fractals, 2018, 106: 214-219.
doi: 10.1016/j.chaos.2017.11.029
[13]
Xin Y C, Gao C, Wang Z, et al. Discerning Influential Spreaders in Complex Networks by Accounting the Spreading Heterogeneity of the Nodes[J]. IEEE Access, 2019, 7: 92070-92078.
doi: 10.1109/ACCESS.2019.2927775
(Cao Jiuxin, Dong Dan, Xu Shun, et al. A k-Core Based Algorithm for Influence Maximization in Social Networks[J]. Chinese Journal of Computers, 2015, 38(2): 238-248.)
[15]
Cheng S Q, Shen H W, Huang J M, et al. IMRank: Influence Maximization via Finding Self-Consistent Ranking[C]// Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval. ACM, 2014: 475-484.
[16]
Borgs C, Brautbar M, Chayes J, et al. Maximizing Social Influence in Nearly Optimal Time[C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2014: 946-957.
[17]
Halappanavar M, Sathanur A V, Nandi A K. Accelerating the Mining of Influential Nodes in Complex Networks Through Community Detection[C]// Proceedings of the 2016 ACM International Conference on Computing Frontiers. ACM, 2016: 64-71.
[18]
Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. PNAS, 2002, 99(12): 7821-7826.
doi: 10.1073/pnas.122653799
pmid: 12060727
[19]
Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2): 026113.
doi: 10.1103/PhysRevE.69.026113
[20]
Newman M E J. Modularity and Community Structure in Networks[J]. PNAS, 2006, 103(23): 8577-8582.
doi: 10.1073/pnas.0601602103
pmid: 16723398
[21]
Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(6): 066133.
doi: 10.1103/PhysRevE.69.066133
[22]
Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of Communities in Large Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10): 10008.
[23]
Raghavan U N, Albert R, Kumara S. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2007, 76(3): 036106.
doi: 10.1103/PhysRevE.76.036106
[24]
Huang L, Liu F Y, Zhang Y. Overlapping Community Discovery for Identifying Key Research Themes[J]. IEEE Transactions on Engineering Management, 2021, 68(5): 1321-1333.
doi: 10.1109/TEM.2020.2972639
[25]
Gupta S, Kumar P. An Overlapping Community Detection Algorithm Based on Rough Clustering of Links[J]. Data & Knowledge Engineering, 2020, 125: 101777.
doi: 10.1016/j.datak.2019.101777
[26]
Coscia M, Rossetti G, Giannotti F, et al. Uncovering Hierarchical and Overlapping Communities with a Local-First Approach[J]. ACM Transactions on Knowledge Discovery from Data, 2014, 9(1): 1-27.
[27]
Banerjee S, Jenamani M, Pratihar D K. ComBIM: A Community-Based Solution Approach for the Budgeted Influence Maximization Problem[J]. Expert Systems with Applications, 2019, 125: 1-13.
doi: 10.1016/j.eswa.2019.01.070
[28]
Atif Y, Al-Falahi K, Wangchuk T, et al. A Fuzzy Logic Approach to Influence Maximization in Social Networks[J]. Journal of Ambient Intelligence and Humanized Computing, 2020, 11(6): 2435-2451.
doi: 10.1007/s12652-019-01286-2
[29]
Ye F H, Liu J H, Chen C, et al. Identifying Influential Individuals on Large-Scale Social Networks: A Community Based Approach[J]. IEEE Access, 2018, 6: 47240-47257.
doi: 10.1109/ACCESS.2018.2866981
[30]
Bonacich P. Factoring and Weighting Approaches to Status Scores and Clique Identification[J]. The Journal of Mathematical Sociology, 1972, 2(1): 113-120.
doi: 10.1080/0022250X.1972.9989806
[31]
Bonacich P. Some Unique Properties of Eigenvector Centrality[J]. Social Networks, 2007, 29(4): 555-564.
doi: 10.1016/j.socnet.2007.04.002
