摘要
社交网络的影响力最大化是网络分析领域的关键问题,在广告宣传、舆情控制等场景有着诸多应用。该问题指在一个社交图中选取一组源节点,使得所选取的节点集合能够在某种传播模型中形成最大的影响力。由于节点选取问题是典型的NP-hard问题,在大型网络中会遭遇组合爆炸。近些年来,国内外学者一般采用启发式算法求得问题的近似解。然而,现有工作鲜有考虑到节点选取的成本,所得到的解无法满足实际应用中的预算条件。针对此问题,首先考虑节点选取的成本约束,并对成本受限条件下的社交网络影响最大化问题进行数学建模;其次为节约源节点的冗余覆盖成本,使用快速贪婪模块度最大化算法对网络进行社区聚类;然后根据社区聚类结果在蚂蚁游走过程中引入跨社区游走因子,以增强蚂蚁在网络上的全局游走能力;最后,在蚁群系统中设计了新的启发式信息和信息素形式,并将评估函数设计为罚函数的形式以控制节点的选取成本,提出了基于社区发现的蚁群系统算法(Community Detection-based Ant Colony System,CDACS)。在真实数据集上的实验结果表明,CDACS算法比未加入跨社区因子的蚁群算法取得的覆盖率平均提高了15%左右,运行时间平均减少了约20%。在覆盖效果上相比其他现有的影响力最大化算法都取得了显著的改进。此外,CDACS在不同数据集上所产生的解均满足不同的成本限制,体现了CDACS算法在成本控制上的可靠性。
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.
作者
左园林
龚月姣
陈伟能
ZUO Yuan-lin;GONG Yue-jiao;CHEN Wei-neng(School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,China)
出处
《计算机科学》
CSCD
北大核心
2022年第4期100-109,共10页
Computer Science
基金
科技部科技创新2030重大项目(2018AAA0101300)
国家自然科学基金面上项目(61873095)
中央高校基本科研业务费专项。
关键词
社交网络
影响最大化
成本控制
蚁群系统
社区聚类
Social network
Influence maximization
Cost control
Ant colony system
Community clustering
