CAJ | 학술논문

影响力最大化问题是如何在社会网络中选择k个种子节点，使得在特定传播模型下的影响范围达到最大。已有的经典算法虽然有较好的影响范围，但其时间复杂度过高，不适用于大型社交网络的影响力分析，也不能保证很好的影响效果。提出一种基于潜在影响力的集合覆盖贪心算法，每次计算所有未覆盖节点的未覆盖度数，选择未覆盖度数最大的节点作为下一个种子节点。如果未覆盖度数最大的节点数不止一个，则选择这些节点中潜在影响力最大的节点作为下一个种子节点。实验结果表明，改进的算法相对于已有算法在最终影响范围和时间复杂度上都有明显的提高。
영향력최대화문제시여하재사회망락중선택k개충자절점，사득재특정전파모형하적영향범위체도최대。이유적경전산법수연유교호적영향범위，단기시간복잡도과고，불괄용우대형사교망락적영향력분석，야불능보증흔호적영향효과。제출일충기우잠재영향력적집합복개탐심산법，매차계산소유미복개절점적미복개도수，선택미복개도수최대적절점작위하일개충자절점。여과미복개도수최대적절점수불지일개，칙선택저사절점중잠재영향력최대적절점작위하일개충자절점。실험결과표명，개진적산법상대우이유산법재최종영향범위화시간복잡도상도유명현적제고。
Influence maximization is a problem of finding a small subset of nodes in a social network that could maximize the spread of influence under a given diffusion model. Although the existing classical algorithms have large spread of influence, they are very costly and cannot be applied to large social networks, also, they could not guarantee the best influence spread. A set covering greedy algorithm based on potential is proposed, calculating the“uncovered degree”of every uncovered node, choosing the node with largest“uncovered degree”as the next seed node. If the number of the nodes with largest”uncovered degree”is more than one, then, choosing the node with the largest potential as the next seed node. Experimental results show that, with respect to the exiting algorithms, the proposed algorithm has significant performance both in influence scope and time complexity.