论文部分内容阅读
互联网技术的发展推动了各种社交网络(Facebook,Twitter,新浪微博等)的蓬勃发展,社会网络中丰富的信息数据的挖掘以及通过社会网络进行的营销活动都给社会网络的研究带来了前所未有的挑战和机遇。网络营销是基于个人通过社会关系对周围朋友,家人或者同事进行影响力扩散而产生的“口碑”营销模式,在影响力扩散过程中,挖掘社会网络中最有影响力的用户变得十分关键。在这个背景下,影响最大化问题的研究变得炙手可热。影响最大化问题就是从社会网络中选出少量节点作为种子节点,从种子节点开始传播,在社会网络中获得最大的影响收益。目前已经提出很多社交网络中的影响最大化算法,例如各种贪心算法,启发式算法等,目的都是降低影响最大化算法的时间开销,提高算法的结果精度。然而,现有算法中鲜有考虑社会网络中节点的结构特征,例如结构洞节点具有鲜明的结构特征,与普通节点相比传播能力更强。忽略节点的结构特征的影响最大化算法的结果精度不够理想,而且利用结构特征可以有效的降低算法的时间开销。针对上述影响最大化研究中的挑战和问题,本文从以下两个方面进行研究:(1)研究基于结构洞理论的影响最大化算法。提出SG(Structure-based Greedy)算法降低影响最大化算法的时间开销,改善影响传播范围。SG算法的基本思想是为原始社会网络建立拉普拉斯矩阵,通过求解费德勒向量确定结构洞节点。本文综合考虑节点的结构特征和影响力,采用过滤的方式筛除非结构洞节点和影响力特别小的节点,缩小种子选取的候选集空间。在缩小的候选集中贪心的选取能够获得最大传播范围的种子节点。本文通过实验验证,本文提出的基于结构洞理论的影响最大化算法和现有算法相比,在算法时间开销和算法结果质量方面都具有明显的优势。(2)研究高效的结构洞发现算法和社团划分的关系。已有的结构洞发现算法主要开销在于计算节点的结构洞值,在大规模社交网络中,结构洞值的计算开销相当可观。本文提出借助社团划分的思想降低结构洞值的计算开销。首先将原始社会网根据节点的相似度进行粗糙划分得到简单社团结构,然后根据社团结构确定结构洞节点,最后计算结构洞节点与已有社团的相似度值作为节点的结构洞值。此外,在已知社会网结构洞节点的前提下,本文提出基于“二步”信息流理论的新的社团划分方法 SCD(Structure-based Community Detection)。SCD 算法的基本思想是首先将原始的社会网根据节点相似度获得粗糙社团结构,然后在粗糙社团中确定网络中的结构洞节点,最后从结构洞节点出发,根据“二步”信息流理论检测潜在社团,根据潜在社团与粗糙社团的相似度对比发现新社团。本文通过真实实验验证了提出的基于结构洞的社团检测算法的正确性和精确性都有很大的改进。