成本受限条件下的社交网络影响最大化方法

doi:10.11896/jsjkx.210300228

计算机科学 ›› 2022, Vol. 49 ›› Issue (4): 100-109.doi: 10.11896/jsjkx.210300228

• 数据库&大数据&数据科学 • 上一篇下一篇

成本受限条件下的社交网络影响最大化方法

左园林, 龚月姣, 陈伟能

华南理工大学计算机科学与工程学院广州 510006

收稿日期:2021-03-24 修回日期:2021-08-12 发布日期:2022-04-01
通讯作者: 龚月姣(gongyuejiao@gmail.com)
基金资助:
科技部科技创新2030重大项目(2018AAA0101300); 国家自然科学基金面上项目(61873095); 中央高校基本科研业务费专项

Budget-aware Influence Maximization in Social Networks

ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng

School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China

Received:2021-03-24 Revised:2021-08-12 Published:2022-04-01
About author:CAO He-xin,born in 1994,postgra-duate.His main research interests include natural language processing and know-ledge graph.LI Xue-feng,born in 1975,Ph.D,asso-ciate professor.His main research interests include NDT,pattern recognition algorithm and signal processing.作者简介：(zuoyuanlin0712@qq.com)
Supported by:
This work was supported by the Key Project of Science and Technology Innovation 2030 of Ministry of Science and Technology of China(2018AAA0101300),National Natural Science Foundation of China(61873095) and Fundamental Research Funds for the Central Universities.

摘要/Abstract

摘要： 社交网络的影响力最大化是网络分析领域的关键问题,在广告宣传、舆情控制等场景有着诸多应用。该问题指在一个社交图中选取一组源节点,使得所选取的节点集合能够在某种传播模型中形成最大的影响力。由于节点选取问题是典型的NP-hard问题,在大型网络中会遭遇组合爆炸。近些年来,国内外学者一般采用启发式算法求得问题的近似解。然而,现有工作鲜有考虑到节点选取的成本,所得到的解无法满足实际应用中的预算条件。针对此问题,首先考虑节点选取的成本约束,并对成本受限条件下的社交网络影响最大化问题进行数学建模;其次为节约源节点的冗余覆盖成本,使用快速贪婪模块度最大化算法对网络进行社区聚类;然后根据社区聚类结果在蚂蚁游走过程中引入跨社区游走因子,以增强蚂蚁在网络上的全局游走能力;最后,在蚁群系统中设计了新的启发式信息和信息素形式,并将评估函数设计为罚函数的形式以控制节点的选取成本,提出了基于社区发现的蚁群系统算法(Community Detection-based Ant Colony System,CDACS)。在真实数据集上的实验结果表明,CDACS算法比未加入跨社区因子的蚁群算法取得的覆盖率平均提高了15%左右,运行时间平均减少了约20%。在覆盖效果上相比其他现有的影响力最大化算法都取得了显著的改进。此外,CDACS在不同数据集上所产生的解均满足不同的成本限制,体现了CDACS算法在成本控制上的可靠性。

关键词: 成本控制, 社交网络, 社区聚类, 蚁群系统, 影响最大化

Abstract: The influence maximization of social networks is a crucial problem in the field of network science, which has wide applications from advertising to public opinion control.This problem refers to selecting a set of source nodes in a social graph to achieve the greatest influence under a certain propagation model.Since the node selection problem is a typical NP-hard problem, it will encounter the combinatorial explosion when facing large-scale networks.Hence, in recent years, heuristic algorithms are ge-nerally adopted to obtain approximate solutions to the problems in acceptable time.However, the existing work rarely considers the cost of selected nodes, and hence the solutions obtained cannot meet the budget limitations in practical applications.This paper aims to solve the influence maximization problem of social networks under cost-constrained conditions.By fully considering the costs, we build a budget-aware influence maximization model and propose a node selection algorithm named community detection-based ant colony system (CDACS) to deal with it.First, in order to save the unnecessary expenditure coming from the redundant coverage of source nodes, we use the fast greedy modularity maximization algorithm to cluster the network, and introduce a cross-community walking factor in the state transition process of ants to enhance the global exploration ability of the ant colony on the network.Second, we specifically design a penalty-based evaluation function to guide the search towards budget-feasible region as well as developing new heuristic and pheromone forms to enhance the search efficiency.Experimental results on real datasets show that the CDACS algorithm enhances the traditional ant colony algorithm by achieving a 15% improvement in the average coverage rate and a 20% reduction in the running time overhead.Compared with other existing influence maximization algorithms, the coverage effect has also been significantly improved.Moreover, the reliability of the CDACS algorithm in cost control has been validated by experiments.

Key words: Ant colony system, Community clustering, Cost control, Influence maximization, Social network

中图分类号:

TP391

左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法[J]. 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228

ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks[J]. Computer Science, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228

参考文献

[1] LBAIK C,JAGADISH H V,LI Y Y.Bridging the semantic gap with SQL query logs in natural language interfaces to databases[J].arXiv:1902.00031,2019.
[2] WU Z,PAN S,CHEN F,et al.A Comprehensive Survey onGraph Neural Networks[J].IEEE Transactions on Neural Networks and Learning Systems,2020(99):1-21.
[3] ANDROUTSOPOULOS I,RITCHIE G D,THANISCH P.Na-tural Language Interfaces to Databases-An Introduction[J].Natural Language Engineering,1995,1(1):29-81.
[4] POPESCU A M, ARMANASU A, ETZIONI O,et al.Modern natural language interfaces to databases:Composing statistical parsing with semantic tractability[C]//COLING.2004.
[5] UNGER C,BÜHMANN L,LEHMANN J,et al.Template- based question answering over RDF data[C]//Proceedings of the 21st World Wide Web Conference.New York:ACM,2012:639-648.
[6] LI F,JAGADISH H V.Constructing an interactive natural language interface for relational databases[J].Proceedings of the VLDB Endowment,2014,8(1):73-84.
[7] ZHONG V,XIONG C,SOCHER R.Seq2SQL:GeneratingStructured Queries from Natural Language using Reinforcement Learning[J].arXiv:1709.0010.3v7.
[8] YU T,LI Z F,ZHANG Z L,et al.TypeSQL:Knowledge-Based Type-Aware Neural Text-to-SQL Generation[J].arXiv:1804.09769v1,2018.
[9] YU T,MICHIHIRO Y,KAI Y,et al.SyntaxSQLNet:Syntax Tree Networks for Complex and Cross-DomainText-to-SQL Task[J].arXiv:1810.05237v1,2018.
[10] YU T,ZHANG R,YANG K,et al.Spider:A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task [J].arXiv:1809.08887v5,2019.
[11] CAO J C,HUANG T,CHEN G,et al.Research on Natural Language Generating Multi-table SQL Query Statement Technology[J].Journal of Computer Science and Research,2020(7):1133-1141.
[12] ZHANG R,YU T,ER H Y,et al.Editing-Based SQL QueryGeneration for Cross-Domain Context-Dependent Questions[C]//Proceedings of the2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).2019.
[13] BOGIN B, GARDNER M, BERANT J.Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing[J].arXiv:1905,06241v2,2019.
[14] BOGIN B,GARDNER M,BERANT J.Global Reasoning overDatabase Structures for Text-to-SQL Parsing[J].arXiv:1908.11214v1,2019.
[15] XIE J X,GAN Y J,YU G J.Design and Implementation of Algorithms for Converting SQL Query Statements into Graph Structures[J].Electromechanical Information,2020(17):120-123.
[16] GUO J,ZHAN Z,GAO Y,et al.Towards Complex Text-to-SQL in Cross-Domain Database with Intermediate Representation[C]//Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics.2019.
[17] ASHISH V, NOAM S, NIKI P,et al.Attention is All YouNeed[J].arXiv:1706.03762.
[18] KIPF T N,WELLING M.Variational Graph Auto-Encoders[J].arXiv:1611.07308v1.
[19] YUAN Z X,REN D D,HONG X D,et al.Research on Question Understanding Method Combining Database Structure and Content[J].Computer Engineering,2021,47(3):71-76,82.

相关文章 15

[1]	王剑, 彭雨琦, 赵宇斐, 杨健. 基于深度学习的社交网络舆情信息抽取方法综述 Survey of Social Network Public Opinion Information Extraction Based on Deep Learning 计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099
[2]	魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究 Study on Temporal Influence Maximization Driven by User Behavior 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145
[3]	余皑欣, 冯秀芳, 孙静宇. 结合物品相似性的社交信任推荐算法 Social Trust Recommendation Algorithm Combining Item Similarity 计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217
[4]	畅雅雯, 杨波, 高玥琳, 黄靖云. 基于SEIR的微信公众号信息传播建模与分析 Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR 计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169
[5]	郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[6]	王剑, 王玉翠, 黄梦杰. 社交网络中的虚假信息:定义、检测及控制 False Information in Social Networks:Definition,Detection and Control 计算机科学, 2021, 48(8): 263-277. https://doi.org/10.11896/jsjkx.210300053
[7]	谭琪, 张凤荔, 王婷, 王瑞锦, 周世杰. 融入结构度中心性的社交网络用户影响力评估算法 Social Network User Influence Evaluation Algorithm Integrating Structure Centrality 计算机科学, 2021, 48(7): 124-129. https://doi.org/10.11896/jsjkx.200600096
[8]	张人之, 朱焱. 基于主动学习的社交网络恶意用户检测方法 Malicious User Detection Method for Social Network Based on Active Learning 计算机科学, 2021, 48(6): 332-337. https://doi.org/10.11896/jsjkx.200700151
[9]	鲍志强, 陈卫东. 基于最大后验估计的谣言源定位器 Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation 计算机科学, 2021, 48(4): 243-248. https://doi.org/10.11896/jsjkx.200400053
[10]	张少杰, 鹿旭东, 郭伟, 王世鹏, 何伟. 供需匹配中的非诚信行为预防 Prevention of Dishonest Behavior in Supply-Demand Matching 计算机科学, 2021, 48(4): 303-308. https://doi.org/10.11896/jsjkx.200900090
[11]	袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法 Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game 计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079
[12]	谭琪, 张凤荔, 张志扬, 陈学勤. 社交网络用户影响力的建模方法 Modeling Methods of Social Network User Influence 计算机科学, 2021, 48(2): 76-86. https://doi.org/10.11896/jsjkx.191200102
[13]	郁友琴, 李弼程. 基于多粒度文本特征表示的微博用户兴趣识别 Microblog User Interest Recognition Based on Multi-granularity Text Feature Representation 计算机科学, 2021, 48(12): 219-225. https://doi.org/10.11896/jsjkx.201100128
[14]	马理博, 秦小麟. 话题-位置-类别感知的兴趣点推荐 Topic-Location-Category Aware Point-of-interest Recommendation 计算机科学, 2020, 47(9): 81-87. https://doi.org/10.11896/jsjkx.191100120
[15]	陈晋音, 张敦杰, 林翔, 徐晓东, 朱子凌. 基于影响力最大化策略的抑制虚假消息传播的方法 False Message Propagation Suppression Based on Influence Maximization 计算机科学, 2020, 47(6A): 17-23. https://doi.org/10.11896/JsJkx.190900086

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

成本受限条件下的社交网络影响最大化方法

Budget-aware Influence Maximization in Social Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0