Please wait a minute...
Data Analysis and Knowledge Discovery  2022, Vol. 6 Issue (12): 80-89    DOI: 10.11925/infotech.2096-3467.2022.0144
Current Issue | Archive | Adv Search |
Identifying Influential Nodes in Social Networks by Overlapping Community Structure
Wang Yetong,Jiang Tao()
Key Laboratory of China’s Ethnic Languages and Information Technology of Ministry of Education, Northwest Minzu University, Lanzhou 730030, China
Download: PDF (1247 KB)   HTML ( 11 ) 
Export: BibTeX | EndNote (RIS)      
Abstract  

[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.
Key words： Social Networks      Overlapping Communities      Influence Maximization      Information Dissemination     
Received: 23 February 2022      Published: 03 February 2023
ZTFLH:  TP393  
  G206  
Fund:Natural Science Foundation of Gansu Province(21JR1RA1999);Fundamental Research Funds for the Central Universities(31920210083)
Corresponding Authors: Jiang Tao，ORCID：0000-0002-6938-8918     E-mail: xinxiyuanjt@126.com
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Yetong Wang
Tao Jiang

Cite this article:

Wang Yetong, Jiang Tao. Identifying Influential Nodes in Social Networks by Overlapping Community Structure. Data Analysis and Knowledge Discovery, 2022, 6(12): 80-89.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2022.0144     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2022/V6/I12/80

Overlapping Community Division
数据集 节点数 连边数 平均度 平均聚类系数
Facebook 4 039 88 234 43.691 0.617
LastFM_Asia 7 624 27 806 7.293 0.285
Git_web_ml 37 700 289 003 15.331 0.193
CA-AstroPh 18 771 198 110 21.107 0.631
Basic Information About the Dataset
Comparison of Parameter ε
Comparison of Parameter b
Dissemination Range
Running Time
[1] 段金发, 邹乾友, 付松涛. 传播模型分析及应用研究进展[J]. 信息工程大学学报, 2020, 21(2): 172-181.
[1] (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
[14] 曹玖新, 董丹, 徐顺, 等. 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015, 38(2): 238-248.
[14] (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
[32] 吴信东, 李毅, 李磊. 在线社交网络影响力分析[J]. 计算机学报, 2014, 37(4): 735-752.
[32] (Wu Xindong, Li Yi, Li Lei. Influence Analysis of Online Social Networks[J]. Chinese Journal of Computers, 2014, 37(4): 735-752.)
[1] Lu Yingjie, Zhang Yinglong. Review of Structural Diversity Studies on Social Networks[J]. 数据分析与知识发现, 2022, 6(8): 1-11.
[2] Cao Guang, Shen Lining. Modelling and Simulating Medical Crowdfunding with SEIR[J]. 数据分析与知识发现, 2022, 6(1): 80-90.
[3] Ma Yingxue,Zhao Jichang. Patterns and Evolution of Public Opinion on Weibo During Natural Disasters： Case Study of Typhoons and Rainstorms[J]. 数据分析与知识发现, 2021, 5(6): 66-79.
[4] Zhang Yipeng,Ma Jingdong. Analyzing Sentiments and Dissemination of Misinformation on Public Health Emergency[J]. 数据分析与知识发现, 2020, 4(12): 45-54.
[5] Yan Wen,Lijian Ma,Qingtian Zeng,Wenyan Guo. POI Recommendation Based on Geographic and Social Relationship Preferences[J]. 数据分析与知识发现, 2019, 3(8): 30-39.
[6] Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
[7] Xiaolan Wu,Chengzhi Zhang. Analysis of Knowledge Flow Based on Academic Social Networks:
A Case Study of ScienceNet.cn[J]. 数据分析与知识发现, 2019, 3(4): 107-116.
[8] Xinrui Wang,Yue He. Predicting Stock Market Fluctuations with Social Media Behaviors: Case Study of Sina Finance Blog[J]. 数据分析与知识发现, 2019, 3(11): 108-119.
[9] Qian Xiaodong,Li Min. Identifying E-commerce User Types Based on Complex Network Overlapping Community[J]. 数据分析与知识发现, 2018, 2(6): 79-91.
[10] Wang Xiwei,Zhang Liu,Li Shimeng,Wang Nan’axue. The Dissemination of Online Public Opinion on Social Welfare Issues via New Media: Case Study of “Draw up the Lifeline” in Sina Weibo[J]. 数据分析与知识发现, 2017, 1(6): 93-101.
[11] Haihan Liao, Yuefen Wang. Public Opinion Dissemination over Social Media: Case Study of Sina Weibo and “8.12 Tianjin Explosion”[J]. 数据分析与知识发现, 2016, 32(12): 85-93.
[12] He Jianmin, Wang Zhe. The Pedigree Method to Mine Influential Clusters of Topic Information in Social Network[J]. 现代图书情报技术, 2015, 31(5): 65-72.
[13] Liu Haoxia, Peng Shanglian. A Community Detection Algorithm via Neighborhood Node Influence Based Label Propagation[J]. 现代图书情报技术, 2015, 31(4): 58-64.
[14] Tan Xueqing, Huang Cuicui, Luo Lin. A Review of Research on Trust Recommendation in Social Networks[J]. 现代图书情报技术, 2014, 30(11): 10-16.
[15] Yu Yan, Qiu Guanghua, Chen Aiping. Friend Recommendation Algorithm Based on Mixed Graph in Online Social Networks[J]. 现代图书情报技术, 2011, (11): 54-59.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626，82624938   E-mail:jishu@mail.las.ac.cn