社交网络中一种快速精确的节点影响力排序算法

摘要

在大规模在线社交网络中,通过对用户影响力进行排序找出其中最具影响力的节点(集合)是一个很重要的研究方向,对于有效控制信息扩散、舆情分析和控制、精准营销等均有重要的作用.已有的节点影响力排序算法或者需要网络的全局拓扑信息来计算单个节点影响力(如基于介数中心性的算法)而时间开销过大,不适用于大规模网络;或者基于传统的网页排序算法(如PageRank)而不能很好地处理社交网络中存在着大量“末梢”节点的问题以及不同用户之间的联系强度不同的问题.在传统的PageRank算法的基础上做出了两点改进.首先,通过在PageRank算法的权值回收步骤中考虑对不同的连接赋予不同的权值,有效避免了末梢节点带来的影响.其次,在PageRank算法的投票过程中考虑邻居个体的差异性,提出了一种基于半邻域信息的节点权值分配方法,有效提高了节点排序的准确度.在一个包含大约15 000个用户的样本网络中,我们所提出的改进算法能够找出前1 000个最有影响力的节点中的40％以上的节点,而传统的PageRank算法仅能找出其中11％的节点.同时,相比于基于介数中心性的算法,所提出的改进算法以小得多的时间开销达到了相近甚至更好的排序准确度.