一种基于节点特性的影响力最大化初始节点选取方法

摘要

本发明提出了一种基于节点特性的在线社会网络影响力最大化初始节点选取方法。首先在网络中，基于用户活跃度、用户敏感度和用户亲密度三方面因素，对节点特性进行评价，并以此为依据对节点之间的信用值进行重新定义和分配，节点之间的信用值大小体现节点之间的影响力，如果两个相邻节点相继执行相同的行为，则认为后者被前者影响，为前者分配信用，之后我们结合网络结构和用户行为日志，计算网络中任意两节点之间的信用值大小，并通过贪心算法，递归选取边际收益最大的节点组成影响力最大化初始节点集合。本发明改进了以往仅依据节点度值评价节点影响力规则的弊端，减少了运算时间和内存消耗，能更真实有效地描述并预测影响力的传播过程。

说明书

技术领域

本发明属于计算机技术领域，涉及一种基于节点特性的影响力最大化初始节点选取方法。

背景技术

互联网的发展不仅为我们带来了便捷生活方式，还使我们交流与沟通的方式发生了巨大的变化。我们交友与分享智慧的途径也随着在线社会网络的发展变得更加丰富多样。随着越来越多的人使用诸如移动终端等更加便捷的数据交换服务，我们的社会结构和社会关系网络变得更加复杂和紧密。一般情况下，我们使用图结构对社会群体中的人与人之间的关系进行建模，节点代表个体，而边或者弧代表个体之间的关系。通过在线社会网络中用户之间的关系，信息可以以极快的速度和极小的代价进行传播，正因为如此，影响力在社会网络中的传播和分布为病毒式营销带来了前所未有的机遇和挑战，如何找到初始用户群体使得信息最终的影响传播范围最大已成为热点研究领域之一。

对于影响力最大化问题，当前大部分的研究工作都是基于对传统经典影响力级联模型的优化，或者对启发式算法的准确度进行改进，对于影响力的评估则主要基于网络结构和节点度值，用户自身的特性和用户与用户之间的行为相似性很少被挖掘并被应用于对节点影响力的评估中。

针对上述不足，我们提出一种对于节点初始影响力的评估方案，这种方法结合了用户特性，用户与行为之间关联关系以及用户之间行为相似度对节点之间的影响力进行评价。同时，我们依据提出的节点之间的影响力评价标准对信用进行分配，并结合贪心算法得到初始影响力最大化节点集合。

发明内容

本发明提出了一种更加真实有效的基于节点特性的影响力最大化初始节点选取方法，在评价节点之间影响力的过程中结合用户活跃度，用户敏感度以及用户亲密度对节点之间的影响力进行评价，根据时间特性计算节点之间的用户影响力大小，并且结合网络结构和用户行为日志对信用分布和影响力的传播过程进行构建，最后结合贪心算法选取边际收益最大的节点得到初始影响力最大化节点集合。具体步骤如下：

步骤1：对在线社会网络数据集进行处理，得到真实的用户行为日志和网络结构文件；

步骤2：遍历用户行为日志，对网络中的每一个节点，分别计算用户活跃度，用户敏感度和用户亲密度，对u节点，用户活跃度act(u)定义为：

代表节点u执行的行为的个数，代表节点u受到邻居节点影响而被动执行的行为个数，代表训练集中记录的行为总个数，参数λ对两种行为数量指标进行控制，取值范围为(0,1)，用户敏感度定义如下：

记录节点u的所有邻居节点中首次执行行为a的时刻，t_u(a)代表节点u最终被影响而执行相同行为a的时刻，τ_u代表节点u与其邻居节点之间的平均延迟时间；当两个时刻的时间跨度越长，的值就越小，用户亲密度p_v，u计算公式如下：

表示节点u和节点v执行行为种类集合的并集，表示节点u和节点v执行行为种类集合的交集；

步骤3：分别对用户敏感度和用户亲密度进行归一化处理，节点u的用户平均敏感度和用户平均亲密度计算规则如下：

$p_u^{^}=\frac{1}{\left|N\left(u\right)\right|}\underset{v\in N\left(u\right)}{\Sigma }{p}_{v,u}$

代表训练集中记录的行为，N(u)表示节点u的邻接节点集合，v∈N(u)，初始用户影响力定义为：

给定节点u与其邻居节点v之间的平均延迟时间τ_v，u和节点u的初始用户影响力iniful(u)，使用连续衰减函数对邻接节点v和节点u之间的影响力进行变换，计算公式如下：

${\psi }_{{u\in N}_{\mathrm{out}}\left(v\right)}^{v,u}\left(a\right)=\mathrm{iniful}\left(v\right)·\exp (-\frac{{(t_u\left(a\right)-t_v^0\left(a\right))}^2}{\sqrt{4\pi }·{\tau }_{v,u}})$

代表节点v对节点u对于行为a的用户影响力，是节点v执行行为a的时刻，N_out(u)表示节点v的出邻居节点集合，u∈N_out(v)，t_u(a)代表节点u最终被影响而执行相同行为a的时刻；

步骤4：定义分配给节点v让其影响节点u的信用，对于任意的两个节点v和节点u，给予节点v让其影响节点u的总信用定义为：

${\Gamma }_{v,u}\left(a\right)=\underset{w\in N_{\mathrm{in}}\left(u\right)}{\Sigma }{\Gamma }_{v,w}\left(a\right)·{\gamma }_{w,u}\left(a\right)$

其中，N_in(u)表示节点u的入邻居节点集合，节点w为节点u的入邻居， w∈N_in(u)，γ_w，u(a)代表给予节点w让其影响邻接节点u的直接信用，公式表示对于任意的两个节点v和节点u，给予节点v让其影响节点u的总信用等于以节点u的所有入邻居为中间节点，给予节点v让其影响节点u的信用乘积之和，令γ_w，u(a)等于节点w对节点u对于行为a的用户影响力，即相似地，给予一个节点集合S让其影响节点u的总信用计算公式如下：

${\Gamma }_{S,u}\left(a\right)=\underset{w\in N_{\mathrm{in}}\left(u\right)\cap w\in S}{\Sigma }{\Gamma }_{S,w}\left(a\right)·{\gamma }_{w,u}\left(a\right)$

步骤5：通过遍历用户行为传播日志，沿着行为传播路径逆向进行信用分配,计算节点x对于所有行为的边际收益：

${\sigma }_{\mathrm{cd}}(S+x)-{\sigma }_{\mathrm{cd}}\left(S\right)=\underset{u\in V}{\Sigma }\frac{1}{A_u}\underset{a\in A_u}{\Sigma }({\Gamma }_{S+x,u}\left(a\right)-{\Gamma }_{S,u}\left(a\right))=\underset{a\in A_u}{\Sigma }\{(1-{\Gamma }_{S,x}\left(a\right))·\underset{u\in V}{\Sigma }(\frac{1}{A_u}·{\Gamma }_{x,u}^{V-S}\left(a\right))\}$

σ_cd(x)为对于节点x的影响力传播函数，S为当前初始节点集合，V代表网络中全体节点的总集，为通过行为a在节点集合V-S中给予节点x让其影响节点u的信用，为给予节点v让其影响除当前初始节点集合S之外的其他节点的总信用，Γ_S，x(a)代表对于行为a，给予当前初始节点集合的S的信用值，节点的信用值越高代表影响力越大，结合贪心算法递归选取边际收益最大的节点插入初始节点集合S；

步骤6：判断初始节点集合中元素的个数是否已经达到要求的个数k，如果已经达到，则得到最终的初始节点集合，如果未达到，则对除当前初始节点集合之外的节点之间的信用分布进行更新，并重新回到步骤5。

本发明是一种基于节点特性的影响力最大化初始节点的选取评估方案，这种方法结合了用户特性，用户与行为之间关联关系以及用户之间行为相似度更加真实地评价节点之间的影响力。同时，依据时间特性对影响力和信用值的 评价标准进行改进，符合节点之间影响力随时间衰减的特性，并且结合网络结构和用户行为日志对信用分布和影响力的传播过程进行构建，通过学习用户真实的行为记录，本发明方法能够更加准确有效地选取初始节点，并获得更好的影响力传播效果。

附图说明

图1是本发明提出的一种基于节点特性的影响力最大化初始节点选取方法流程图；

图2是本发明提出的一种基于节点特性的影响力最大化初始节点选取方法的关键步骤；

图3是实施例1中不同的方法对于初始节点选取所消耗的运行时间对比图，左图为4种方法在0到160分钟时间跨度内运行时间实验结果对比，右图为2种方法在1到3分钟的时间跨度内运行时间实验结果对比；

图4是实施例1中不同的方法对于初始节点选取所消耗的内存空间对比图，左图为4种方法在0到100MB空间跨度中消耗内存的实验结果对比，右图为2种方法在0到50MB的空间跨度中消耗内存的实验结果对比；

图5是实施例2中不同的方法对于初始节点集合的影响力传播效果对比图，左图为4种方法对于选取的初始节点集合影响力传播的实验结果曲线表示形式，右图为2种方法对于选取的初始节点集合影响力传播实验结果的柱状图表示形式。

图6是实施例2中对于测试集用户行为的影响力预测结果对比图，左图为2种方法对测试集行为影响力预测结果的散点图表示形式，右图为2种方法对行为影响力预测结果的柱状图表示形式。

具体实施方式

下面将结合附图、理论分析和仿真实验对本发明作进一步的详细说明。

本发明将社会网络构造为一个无向图G＝(V,E)，其中V表示图中全体节点的集合，E代表不同个体之间关系的集合，S代表初始节点集合，σ(S)表示影响力传播函数，在本发明中将影响力体现为赋予节点的信用值的大小，节点被分配的信用值越高代表节点的影响力越大，所以σ_cd(S)定义为给予当前节点集合S让其影响其余节点的总信用,即影响力最大化问题就是找到个数为k的初始节点集合，使得最终在整个网络中被成功影响的节点个数的期望值最大。

节点的权值体现节点的特异性。一方面，不同的个体往往有不同的兴趣爱好和不同的偏好取向，当不同的人面对相同的事物的时候，是否接受该事物取决与个体对其内在的评价和认知接受阈值大小。另一方面，每一个个体对他人的影响力也是不同的，例如，一般情况下，来自朋友或者亲人的推荐相比于陌生人会产生更强的影响力，我们使用评价个体之间的亲密程度或信任程度来体现这种特性。本发明方法提出一种通过信息在真实网络中传播记录来创建和模拟行为传播过程，同时结合用户活跃度、用户敏感度和用户亲密度3方面对邻接节点之间的影响力进行评估。图1和图2分别为本发明提出的一种基于节点特性的影响力最大化初始节点选取方法流程图和关键步骤，具体实施步骤如下。

步骤1：对在线社会网络数据集进行处理，得到真实的用户行为日志和网络结构文件；

步骤2：遍历用户行为日志，对网络中的每一个节点，分别计算用户活跃 度，用户敏感度和用户亲密度，对u节点，用户活跃度act(u)定义为：

代表节点u执行的行为的个数，代表节点u受到邻居节点影响而被动执行的行为个数，代表训练集中记录的行为总个数，参数λ对两种行为数量指标进行控制，取值范围为(0,1)，用户敏感度定义如下：

记录节点u的所有邻居节点中首次执行行为a的时刻，t_u(a)代表节点u最终被影响而执行相同行为a的时刻，τ_u代表节点u与其邻居节点之间的平均延迟时间；当两个时刻的时间跨度越长，的值就越小，用户亲密度p_v，u计算公式如下：

表示节点u和节点v执行行为种类集合的并集，表示节点u和节点v执行行为种类集合的交集；

步骤3：分别对用户敏感度和用户亲密度进行归一化处理，节点u的用户平均敏感度和用户平均亲密度计算规则如下：

$p_u^{^}=\frac{1}{\left|N\left(u\right)\right|}\underset{v\in N\left(u\right)}{\Sigma }{p}_{v,u}$

代表训练集中记录的行为，N(u)表示节点u的邻接节点集合，v∈N(u)，初始用户影响力定义为：

给定节点u与其邻居节点v之间的平均延迟时间τ_v，u和节点u的初始用户影响力iniful(u)，使用连续衰减函数对邻接节点v和节点u之间的影响力进行变换，计算公式如下：

${\psi }_{{u\in N}_{\mathrm{out}}\left(v\right)}^{v,u}\left(a\right)=\mathrm{iniful}\left(v\right)·\exp (-\frac{{(t_u\left(a\right)-t_v^0\left(a\right))}^2}{\sqrt{4\pi }·{\tau }_{v,u}})$

代表节点v对节点u对于行为a的用户影响力，是节点v执行行为a的时刻，N_out(v)表示节点v的出邻居节点集合，u∈N_out(v)，t_u(a)代表节点u最终被影响而执行相同行为a的时刻；

步骤4：定义分配给节点v让其影响节点u的信用，对于任意的两个节点v和节点u，给予节点v让其影响节点u的总信用定义为：

${\Gamma }_{v,u}\left(a\right)=\underset{w\in N_{\mathrm{in}}\left(u\right)}{\Sigma }{\Gamma }_{v,w}\left(a\right)·{\gamma }_{w,u}\left(a\right)$

其中，N_in(u)表示节点u的入邻居节点集合，节点w为节点u的入邻居，w∈N_in(u)，γ_w，u（a)代表给予节点w让其影响邻接节点u的直接信用，公式表示对于任意的两个节点v和节点u，给予节点v让其影响节点u的总信用等于以节点u的所有入邻居为中间节点，给予节点v让其影响节点u的信用乘积之和，令γ_w，u(a)等于节点w对节点u对于行为a的用户影响力，即相似地，给予一个节点集合S让其影响节点u的总信用计算公式如下：

${\Gamma }_{S,u}\left(a\right)=\underset{w\in N_{\mathrm{in}}\left(u\right)\cap w\in S}{\Sigma }{\Gamma }_{S,w}\left(a\right)·{\gamma }_{w,u}\left(a\right)$

步骤5：通过遍历用户行为传播日志，沿着行为传播路径逆向进行信用分配,计算节点x对于所有行为的边际收益：

${\sigma }_{\mathrm{cd}}(S+x)-{\sigma }_{\mathrm{cd}}\left(S\right)=\underset{u\in V}{\Sigma }\frac{1}{A_u}\underset{a\in A_u}{\Sigma }({\Gamma }_{S+x,u}\left(a\right)-{\Gamma }_{S,u}\left(a\right))=\underset{a\in A_u}{\Sigma }\{(1-{\Gamma }_{S,x}\left(a\right))·\underset{u\in V}{\Sigma }(\frac{1}{A_u}·{\Gamma }_{x,u}^{V-S}\left(a\right))\}$

σ_cd(x)为对于节点x的影响力传播函数，S为当前初始节点集合，V代表网络中全体节点的总集，为通过行为a在节点集合V-S中给予节点x让其影响节点u的信用，为给予节点v让其影响除当前初始节点集合S之外的其他节点的总信用，Γ_S，x(a)代表对于行为a，给予当前初始节点集合的S的信用值，节点的信用值越高代表影响力越大，结合贪心算法递归选取边际收益最大的节点插入初始节点集合S；

步骤6：判断初始节点集合中元素的个数是否已经达到要求的个数k，如果已经达到，则得到最终的初始节点集合，如果未达到，则对除当前初始节点集合之外的节点之间的信用分布进行更新，并重新回到步骤5。

为了验证本发明的有效性，下面就根据影响力函数对节点的边际收益进行理论推导分析。

给予一个节点集合S让其影响节点u的总信用Γ_S，u(a)等于给予集合S让其先影响所有节点u的直接入邻居节点w，再影响节点u的信用之和，即表示为：

${\Gamma }_{S,u}\left(a\right)={\Sigma }_{w\in N_{\mathrm{in}}\left(u\right)\cap \in S}{\Gamma }_{S,w}\left(a\right)·{\gamma }_{w,u}\left(a\right)---\left(1\right)$

节点u的入邻居集合表示为N_in(u)，节点w为节点u的入邻居，w∈N_in(u)∩w∈S，Γ_S，w(a)为针对行为a给予集合S让其影响w的信用，γ_w，u(a)为给予w让其影响直接邻居节点u的信用。

当一个节点x因为边际收益最大而被插入初始节点集合S后，需要对网络中其他节点的信用分布进行更新，因为将节点x选为初始节点后，在初始时刻他将做为信息的发送者，并屏蔽做为中继功能的影响力的传播，所以在计算除当前初始节点集合S之外任意两点之间的信用分布时需要减去所有通过节点x的路径分配的信用值

${\Gamma }_{v,u}^{V-S-x}\left(a\right)={\Gamma }_{v,u}^{V-S}\left(a\right)-{\Gamma }_{v,x}^{V-S}\left(a\right)·{\gamma }_{x,u}^{V-S}\left(a\right)---\left(2\right)$

则将节点x插入初始集合S后，信用的差值为

${\Gamma }_{S+x,u}\left(a\right)-{\Gamma }_{S,u}\left(a\right)={\Sigma }_{v\in S+x}{\Gamma }_{v,u}^{V-S-x+v}\left(a\right)-{\Sigma }_{v\in S}{\Gamma }_{v,u}^{V-S+v}\left(a\right)---\left(3\right)$

因为已知节点x并不在原先初始节点集合中，所以信用差值为给予x的节点为给予节点x让其影响节点u的信用与不经过节点x的分配路径给予S的总信用只差，即

${\Gamma }_{S+x,u}\left(a\right)-{\Gamma }_{S,u}\left(a\right)={\Gamma }_{x,u}^{V-S}\left(a\right)-{\Sigma }_{v\in S}({\Gamma }_{v,u}^{V-S+v}\left(a\right)-{\Gamma }_{v,u}^{V-S-x+v}\left(a\right))---\left(4\right)$

根据公式(2)可将化简为因为行为传播路径服从时序特性，不可能存在回路，所以节点v不可能在节点x与节点u的分配路径中，故将公式(4)化简为

${\Gamma }_{S+x,u}\left(a\right)-{\Gamma }_{S,u}\left(a\right)={\Gamma }_{x,u}^{V-S}\left(a\right)-{\Gamma }_{x,u}^{V-S}\left(a\right)·{\Sigma }_{v\in S}\left({\Gamma }_{v,x}^{V-S+v}\left(a\right)\right)---\left(5\right)$

根据公式(5)可以得到节点x对于所有行为的边际收益计算公式：

${\sigma }_{\mathrm{cd}}(S+x)-{\sigma }_{\mathrm{cd}}\left(S\right)={\Sigma }_{u\in V}\frac{1}{A_u}{\Sigma }_{a\in A_u}({\Gamma }_{x,u}^{V-S}\left(a\right)-{\Gamma }_{x,u}^{V-S}\left(a\right)·{\Sigma }_{v\in S}\left({\Gamma }_{v,x}^{V-S+v}\left(a\right)\right))---\left(6\right)$

提取公式右边的可以化简为 将公式中的参数位置进行变换，可以得到

${\sigma }_{\mathrm{cd}}(S+x)-{\sigma }_{\mathrm{cd}}\left(S\right)={\Sigma }_{a\in A_u}\{(1-{\Gamma }_{S,s}\left(a\right))·{\Sigma }_{u\in V}(\frac{1}{A_u}·{\Gamma }_{x,u}^{V-S}\left(a\right))\}---\left(7\right)$

由上述理论分析可知，计算节点x的边际收益只需计算给予节点x让其影响除当前初始节点集合S之外的其他节点的总信用以及对于行为a，给予当前初始节点集合的S的信用值Γ_S，x(a)即可，验证了本发明方法的准确性和真实性。

在实验中，我们获取的数据集是从真实的照片分享网站Flickr采集的，总 数据集包含105938张照片。根据照片的来源共分为4个部分，我们选择其中之一作为实验对象，包含2602个节点和222292条边和24648张照片。因为信用分布服从时间约束和网络结构，所以我们对原始数据进行处理，得到两个文件，其中图文件记录照片的作者之间的关联关系，用户行为日志文件包含以时间顺序记录的用户行为记录。我们又将用户行为记录分成两部分，即包含2724种行为的训练集用户行为记录和包含1816种行为的测试集用户行为记录。用户行为日志文件中包含75269条记录。

实施例1：

在该实施例中，我们令参数λ＝0.5，这样做的目的是为了均衡节点u主动发起的行为与受到邻居节点影响而被动执行的行为所占的比重。

由图3可知，通过本发明方法(CD2)选取初始节点所需的运行时间略高于在传统信用分布模型(CD)上对节点的选取，从图中记录的运行时间分布可以看出，随着初始节点的增加，运行时间的增长趋势是线性的，并且明显少于在独立级联模型(IC)和线性阈值模型(LT)上选取同等数量初始节点的执行时间。实验结果证明本发明方法在运行时间方面具有高效性和可扩展性。

由图4可知，随着初始集合节点的增加，本发明方法(CD2)对于初始节点选取所消耗的内存空间略高于传统信用分布模型(CD)，这是因为加入了节点特性的评估和用户影响力的计算工作，但本发明方法在选取同等数量初始节点的情况下内存空间消耗要低于独立级联模型(IC)和线性阈值模型(LT)的，这种优势随着初始节点选取的增多而更加明显。实验结果表明，对于影响力最大化初始节点选取的工作，本发明方法无论是在时间运行方面还是在内存空间消耗方面均表现出更高的优势和效率。

实施例2：

由图5可知，本实验方法(CD2)相比与传统模型(CD)对影响力具有更强的描述和传播能力。相比于独立级联模型(IC)和线性阈值模型(LT)，本发明方法的另一个优势在于它是对用户真实的行为记录进行学习，并结合用户特征而不是仅仅依据网络结构对用户影响力进行评价，所以能够更加真实地反映用户行为和影响力传播，具有更高的真实性和可靠性。

对比使用本发明方法(CD2)和CD两种方法针对测试集中记录的行为进行影响力传播预测，测试集包含全部1816种行为，实验结束后我们按照真实的影响力传播结果对不同的行为进行排序，并将实验预测结果与真实值进行对比。如图6所示，本发明方法和传统方法对测试集行为样本的影响力传播预测结果均低于真实的影响力传播值，但是从对比结果可以看出，相比于传统方法(CD)，本发明方法对用户行为预测效果有一定程度的优化和提升，并具有更高的影响力预测精确度。

从以上实验可知，本发明方法无论从运行时间还是内存空间消耗方面均表现出高效的特性，通过学习真实行为传播记录，能够更加真实地反映用户行为和影响力的传播，除此之外，实验证明本发明方法对初始节点的选取具有更高的准确性和可靠性。