异质信息网络中基于网络嵌入的影响力最大化

杨宇迪，周丽华,2，杜国王，邹星竹，丁海燕

（1.云南大学 信息学院，云南 昆明 650504;2.云南大学 滇池学院，云南 昆明 650228）

影响力最大化问题是指在特定的扩散模型下，寻找一组初始扩散节点使影响扩散范围最大的优化问题。目前，影响力最大化算法主要分为两类：贪心算法[1-3]和启发式算法[4-6]，其中贪心算法主要用于提高算法的精确度；启发式算法主要用于解决实际问题以提高算法效率。Kempe 等[7]首次形式化定义了影响力最大化问题，并提出了一个贪心算法，其近似值约为 1−/e−ε，但是该算法的效率较低。Leskovec 等[8]提出了CELF 算法，Goyal 等[9]提出了CELF++算法，通过实验发现该算法比CELF 快35%～55%。接着，为了解决贪心算法的效率问题，Tang 等[10]提出一种基于跳的算法，该算法可以在常用的扩散模型(独立级联模型和线性阈值模型)下轻松应用于十亿规模的网络。Peng 等[11]认为个体之间的影响有直接影响和间接影响，社会影响力的强弱取决于个体之间的关系、网络距离、时间、网络和个体的复杂性和不确定性。但这些算法通常仅将社会网络看作同质网络，忽略了社会网络的异质性，即网络中包含不同类型的对象和链接。在异质信息网络(heterogeneous information network，HIN)中，影响力可以通过不同的对象和链接进行扩散，从而获得更广泛的影响范围。

尽管异质信息网络丰富的结构和语义信息有助于实现影响力扩散范围最大化，但也给影响力的分析带来了挑战。目前，HIN 中的数据挖掘任务主要集中于相似性搜索[12-13]、聚类[14-15]、分类[16-17]等，很少有研究者关注HIN 中的社会影响力分析。……