Influence maximization algorithm based on structure hole and degree discount

doi:10.11772/j.issn.1001-9081.2018040920

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (12): 3419-3424.DOI: 10.11772/j.issn.1001-9081.2018040920

Previous Articles Next Articles

Influence maximization algorithm based on structure hole and degree discount

LI Minjia, XU Guoyan, ZHU Shuai, ZHANG Wangjuan

College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China

Received:2018-05-04 Revised:2018-07-02 Online:2018-12-10 Published:2018-12-15
Contact: 李敏佳
Supported by:
This work is partially supported by the Science and Technology Research Project of Water Resources Department of Jiangsu Province (2017065, 2016023).

基于结构洞和度折扣的影响力最大化算法

李敏佳, 许国艳, 朱帅, 张网娟

河海大学计算机与信息学院, 南京 211100

通讯作者: 李敏佳
作者简介:李敏佳(1994-),女,河南周口人,硕士研究生,主要研究方向:社交网络、数据管理;许国艳(1971-),女,内蒙古赤峰人,副教授,博士,CCF会员,主要研究方向:大数据、数据起源、数据管理;朱帅(1992-),男,江苏扬州人,硕士研究生,主要研究方向:社会网络、数据管理;张网娟(1992-),女,江苏盐城人,硕士研究生,主要研究方向:大数据、数据管理。
基金资助:
江苏省水利科技科研项目（2017065，2016023）。

Abstract

Abstract: The existing Influence Maximization (IM) algorithms of social network have the problem of low influence range caused by only selecting local optimal nodes at present. In order to solve the problem, considering the propagation advantage of core node and structure hole node, a maximization algorithm based on Structure Hole and Degree Discount (SHDD) was proposd. Firstly, the ideas of structure hole and centrality degree were integrated and applied to the influence maximization problem, and the factor α combining the structure hole node and the core node was found out to play the maximum propagation function, which made the information spread more widely to increase the influence of the whole network. Then, in order to highlight the advantages of the integration of two ideas, the influence of second-degree neighbor was added to the evaluation criteria of structure hole to select the structure hole node. The experimental results on data sets of different scales show that, compared with DegreeDiscount algorithm, SHDD can increase the influence range without consuming too much time, and compared with the Structure-based Greedy (SG) algorithm, SHDD can expand the influence range and reduce the time cost in the network with large clustering coefficient. The proposed SHDD algorithm can maximize the advantages of structure hole node and core node fusion when factor α is 0.6, and it can expand the influence range more steadily in the social network with large clustering coefficient.

Key words: social network, Influence Maximization (IM), Independent Cascade model (IC), structure hole, degree discount

摘要： 在社会网络影响力最大化（IM）算法中，针对目前仅选取局部最优节点造成的影响范围较小的问题，综合考虑核心节点和结构洞节点的传播优势，提出了一种基于结构洞和度折扣的最大化算法（SHDD）。首先，该算法将结构洞思想和中心度思想互相融合应用到影响力最大化问题中，并找出能将结构洞节点和核心节点综合发挥最大传播作用的α因子，使得信息更大范围地扩散从而扩大整个网络的影响范围。其次，为突出两个思想融合的优势，将二度邻居的影响添加到结构洞评价标准中来选取结构洞节点。在不同规模的数据集上实验结果表明，与DegreeDiscount算法相比，SHDD在没有增加过多时间开销的同时扩大了影响范围；与基于结构的贪心（SG）算法相比，在聚类系数较大的网络中SHDD扩大了影响范围并降低了时间开销。SHDD在α因子取0.6时能最大限度地发挥结构洞节点和核心节点融合的作用并且在聚类系数较大的社交网络中能更加稳定地扩大影响范围。

关键词: 社交网络, 影响力最大化, 独立级联模型, 结构洞, 度折扣

CLC Number:

TP391
TP312

LI Minjia, XU Guoyan, ZHU Shuai, ZHANG Wangjuan. Influence maximization algorithm based on structure hole and degree discount[J]. Journal of Computer Applications, 2018, 38(12): 3419-3424.

李敏佳, 许国艳, 朱帅, 张网娟. 基于结构洞和度折扣的影响力最大化算法[J]. 计算机应用, 2018, 38(12): 3419-3424.

References

[1] 夏涛,陈云芳,张伟,等.社会网络中的影响力综述[J].计算机应用,2014, 34(4):980-985.(XIA T, CHEN Y F, ZHANG W, et al. Survey of influence in social networks[J]. Journal of Computer Applications, 2014, 34(4):980-985.)
[2] 李阅志,祝园园,钟鸣.基于k-核过滤的社交网络影响最大化算法[J].计算机应用,2018,38(2):464-470.(LI Y Z, ZHU Y Y, ZHONG M. k-core filtered influence maximization algorithm in social networks[J]. Journal of Computer Applications, 2018, 38(2):464-470.)
[3] 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. New York:ACM, 2003:137-146.
[4] CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2009:199-208.
[5] ESTEVEZ P A, VERA P, SAITO K. Selecting the most influential nodes in social networks[C]//Proceedings of the 2007 International Joint Conference on Neural Networks. Piscataway, NJ:IEEE, 2007:2397-2402.
[6] 曹玖新,董丹,徐顺,等.一种基于k-核的社会网络影响最大化算法[J].计算机学报,2015,38(2):238-248.(CAO J X, DONG D, XU S, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2):238-248.)
[7] 苏晓萍,宋玉蓉.利用邻域"结构洞"寻找社会网络中最具影响力节点[J].物理学报,2015,64(2):1-11.(SU X P, SONG Y R. Leveraging neighborhood "structure holes" to identifying key spreaders in social networks[J]. Acta Physica Sinica. 2015, 64(2):1-11.)
[8] 韩忠明,陈炎,刘雯,等.社会网络节点影响力分析研究[J].软件学报,2017,28(1):84-104.(HAN Z M, CHEN Y, LIU W,et al. Research on node influence analysis in social network[J]. Journal of Software, 2017, 28(1):84-104.)
[9] ZHU J H, LIU Y, YIN X M. A new structure-hole-based algorithm for influence maximization in large online social networks[J]. IEEE Access, 2017, 5:23405-23412.
[10] GOLDENBERG J, LIBAI B, MULLER E. Talk of the network:a complex systems look at the underlying process of word-of-mouth[J]. Marketing Letters, 2001, 12(3):211-223.
[11] YOUNG H P. The diffusion of innovations in social networks[J]. General Information, 2000, 413(1):2329-2334.
[12] LOU T, TANG J. Mining structural hole spanners through information diffusion in social networks[C]//Proceedings of the 22nd International Conference on World Wide Web. New York:ACM, 2013:825-836.
[13] 韩忠明,吴杨,谭旭升,等.面向结构洞的复杂网络关键节点排序[J].物理学报,2015,64(5):058902-1-058902-9.(HAN Z M, WU Y, TAN X S, et al. Ranking key nodes in complex networks by considering structural holes[J]. Acta Physica Sinica, 2015, 64(5):058902-1-058902-9.)
[14] 刘院英,郭景峰,魏立东,等.成本控制下的快速影响最大化算法[J].计算机应用,2017,37(2):367-372.(LIU Y Y, GUO J F, WEI L D, et al. Fast influence maximization algorithm in social network under budget control[J]. Journal of Computer Applications, 2017, 37(2):367-372.)

[1]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[2]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[3]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.
[4]	Xujian ZHAO, Chongwei WANG. Storyline extraction method from Weibo news based on graph convolutional network [J]. Journal of Computer Applications, 2021, 41(11): 3139-3144.
[5]	LI Xiangkun, JIA Caiyan. Collaborative filtering method fusing overlapping community regularization and implicit feedback [J]. Journal of Computer Applications, 2021, 41(1): 53-59.
[6]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[7]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[8]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[9]	YI Dongyi, DENG Genqiang, DONG Chaoxiong, ZHU Miaomiao, LYU Zhouping, ZHU Suisong. Medical insurance fraud detection algorithm based on graph convolutional neural network [J]. Journal of Computer Applications, 2020, 40(5): 1272-1277.
[10]	FENG Liping, HAN Qi, ZHOU Zhigang, BAI Zengliang. Bad information diffusion modeling and optimal control strategy influenced by social networks [J]. Journal of Computer Applications, 2020, 40(3): 735-739.
[11]	SHAN Xiaohuan, ZHANG Zhiguo, SONG Baoyan, REN Chenglin. Activity recommendation method based on directed label graph and user feedback in event-based social network [J]. Journal of Computer Applications, 2020, 40(2): 448-453.
[12]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Social event participation prediction based on event description [J]. Journal of Computer Applications, 2020, 40(11): 3101-3106.
[13]	HE Haochen, ZHANG Danhong. Recommendation method based on multidimensional social relationship embedded deep graph neural network [J]. Journal of Computer Applications, 2020, 40(10): 2795-2803.
[14]	QIN Haiyan, ZHANG Yonglong, LI Bin. Truthful mechanism for crowdsourcing task assignment in social network [J]. Journal of Computer Applications, 2020, 40(10): 3019-3024.
[15]	SUN Heli, HE Liang, HE Fang, SUN Miaomiao, JIA Xiaolin. Network embedding based tenuous subgraph finding [J]. Journal of Computer Applications, 2020, 40(10): 2929-2935.

Influence maximization algorithm based on structure hole and degree discount

基于结构洞和度折扣的影响力最大化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics