社会网络是由个体以及个体间的社会关系构成的一种社会结构,当下十分流行的各类在线社交网络即为此类社会结构的典型代表。各式各样的信息经由这些社交网络得到高效的传播与扩散。有一个现象值得引起注意:有些个体通过社交网络肆意扩散负面信息,如吹捧消极避世观、倡导不健康行为等,此类行为势必会阻碍社会的稳定和谐发展。给定一个社交网络,如何从中选定尽可能少的用户作为正面信息源,来使得该网络中每个用户接收到的正面影响高于负面影响,这即为最小正影响支配集问题。本文重点研究了用于求解该问题的贪心算法,通过对该问题本质的重新认识设计出全新的贪心算法,提升了该问题的求解效率。本文主要工作包括以下三方面:·基于个体需求的正影响支配集求解算法为了解决传统正影响支配集求解算法在节点选取过程中搜索开销过大的问题,本文提出了一种基于个体需求的正影响支配集求解算法Locally Greedy。该算法采用优先满足低度节点正影响需求的原则来缩小节点选取过程的搜索范围,从而提升了求解效率。本文证明了该算法的正确性,并分析了该算法的效率。·算法性能对比本文复现了其他正影响支配集求解算法,并在Stanford Large Network Dataset Collection、Network Repository和Network data等公开数据源的数据集上开展了大量实验,结果表明Locally Greedy算法比现有工作求解速度更快、求解质量更好,验证了该算法在最小正影响支配集问题上的高效性。·其他类型网络中的正影响支配集求解算法本文针对有向无权网络以及无向加权网络中的正影响支配集求解问题,提出了基于Locally Greedy的各类算法。公开数据集上的实验表明,这些算法能够高效地求解出正影响支配集。