基于文化基因算法的社交网络影响最大化方法

摘要

本发明公开了一种基于文化基因算法的社交网络影响最大化方法，主要解决现有技术在处理社交网络影响最大化时难以找出可使信息传播最广的初始激活节点集合问题。其实现步骤为：1.确定目标函数，并构造初始种群；2.开始进化过程，从种群中选择出父代个体，并依次进行交叉及变异操作得到子代个体；3.选出子代最优个体，对其进行局部搜索；4.根据父代和子代个体更新种群,并选出种群最优个体；5.判断是否终止：如果进化次数满足预先设定次数，则输出种群最优个体，否则，返回步骤2。本发明能有效地从大规模社交网络中挖掘出信息传播最广的初始激活节点集合，有效地解决了社交网络信息影响最大化的问题，可用于研究社交网络的信息传播机制。

说明书

技术领域

本发明属于社交网络技术领域，特别涉及一种找出社交网络中具有最佳影响力个体 组合的方法，可用于分析和研究社交网络的信息传播机制。

背景技术

社交网络是现代生活中最为常见的也是最为直观的复杂社会网络，它由网络中每个 个体的人际关系网络构成。其中，网络中的每个节点代表社会生活中的每一个个体，而 网络的边就是个体相对应的人际关系，常见的社交网络有合作网络、信任网络以及交友 网络等。由于个体之间的相互交流和人际关系与我们的生活、学习以及工作密切联系， 因此对社交网络进行分析对人类社会有着重要的研究意义和价值。

近年来，随着Web 2.0的出现和互联网信息技术的迅猛发展，一系列的在线交友网 络出现在人们的生活当中，具有代表性的有Facebook、Twitter、QQ以及目前快速发展 的微博社交网络平台等。这些在线社交网络不受空间和时间的限制，能够使人们交流越 来越频繁，联系也越来越紧密，极大地推动了社交网络的发展。社交网络的共同特点就 是规模庞大，使用人群的年龄、行业等复杂多样，且设计的话题覆盖面广，信息量大。

社交网络的信息传播，作为社会网络的热点研究话题，是理解、获取和预测市场营 销、社会安全以及Web搜索等领域中信息传播过程的基础和依据。目前，众多企业已 经广泛地利用社交网络的信息传播机制，将社交网络视为市场营销的平台，进行新产品 和新服务的推广。相比于传统的方法，这种市场营销手段往往能够以很小的代价，达到 以一传百甚至传千的效果，从而使企业获得极大的利润。社交网络影响最大化问题就可 以具体解释为，在社交网络中推广某种新型产品或者服务时，如何选择首次推广的用户 从而使得该产品或服务由其推广到网络中更多的个体，或者将“种子短信”发给哪些手 机用户可以获得更大范围的转发；从另一个角度来讲，当传染病来临时，应该采取何种 接种免疫策略来避免和控制传染病的传播，或者根据网络的信息传播机制，如何有效地 控制在线社交网络中的谣言传播，维护网络安全等。

目前，社交网络信息影响最大化的研究已经涉及到社会学、经济学、信息传播学、 统计学以及计算机网络学等多个领域，其中较为典型的社交网络包括科学家合作网络、 电子邮件网络、金融信任网络以及复杂多样的在线交友网络等。关于如何去定量地分析 和理解以及如何有效地解决社交网络信息影响最大化问题，目前也已经引起科学界的广 泛关注和研究。除此之外，其背后蕴藏的深刻的社会意义和巨大的商业价值也在很大的 程度上促进了该问题的研究和发展。

在现有的针对社交网络信息影响最大化问题的研究中，其内容主要分为两个方面， 分别是如何建立合理的动力学模型去分析和模拟真实的社交网络信息传播机制以及在 此基础上，如何挖掘网络中可以使得信息传播最大化的种子节点集合。目前，在网络信 息传播领域中，较为常用的两种基本动力学分析模型分别称为独立级联模型和线性阈值 模型，其根据网络的不同特征，分别从不同地角度分析了信息如何在网络中进行传播。 除了上述的两种传播机制，还有最初针对传染病传播机制的SIR模型和SIS模型。

网络信息影响最大化问题最早为经济市场学领域的产品推广问题。商家为了广泛推 广其产品，如何有选择地去推广给一些有影响的人群，从而使产品达到最大范围的推广。 Domingos和Richardson在“Mining the network value of customers”(《Processdings of the  ASM SIGKDD Conference on Knowledge Discovery and Data Mining》，2001，page 57-66) 中第一次将这个问题以一个算法问题提出来，并且通过使用一种基于概率模型的方法去 尝试解决它。在“Maximizing the spread of influence through a social network” (《Processdings of the ASM SIGKDD Conference on Knowledge Discovery and Data  Mining》，2003，pages 137-146)一文中Kempe等人将该问题阐述为一个组合优化问题， 称之为网络影响最大化问题，并通过提出一种基于爬山策略的贪婪算法对其进行了求 解。

基于上述基础，近年来越来越多的针对网络影响最大化问题的方法被提出来。传统 的基于网络邻域和距离特性的方法，如最大度中心性方法、最短距离中心性方法以及介 数中心性方法等，一般具有较低的运行时间复杂度，但是上述方法根本无法完全有效地 挖掘出网络中最具影响力的节点组合。而Kempe等人提出的贪婪算法，找出的个体组 合可以达到接近63％的最大影响范围，但是该算法在每确定一个节点时都要遍历网络中 所有的节点，并且必须通过上万次迭代来计算初始激活节点的平均影响范围。这使得贪 婪算法在解决社交网络影响最大化问题时，必须付出了高昂的运算时间复杂度，致使其 应用受到极大的限制。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种基于文化基因算法的社交网络 影响最大化方法，以减小运算时间复杂度，挖掘出具有最大影响力的节点组合，应用于网 络信息的传播过程中，实现网络的影响最大化。

本发明的技术思路是：将社交网络影响最大化问题看作是一个组合优化问题，其中将 期望传播函数作为目标函数，利用基于文化基因的进化方法来优化目标函数，并通过利用 网络邻域信息引入邻域局部搜索策略，从而找到更好的节点组合，其实现步骤包括如下：

(1)输入目标网络G＝(V,E)，其中，V表示网络中的节点集合，E为网络中边的集合；

(2)设定传播概率p和初始激活节点数目K，对于初始激活节点集合A，根据独立级联 信息传播形式构建期望传播值函数EDV，作为待优化的目标函数：

$\mathrm{EDV}\left(A\right)=K+\underset{\mu \in {\mathrm{Neighbor}}_A}{\Sigma }(1-{(1-p)}^{{\sigma }_{\mu }}),$

其中，表示初始激活节点集合A的邻居节点集合，μ 为初始激活节点集合A的某一邻居节点，σ_μ＝|{ω|ω∈A,ωμ∈E}|表示邻居节点μ连接初始 激活节点集合A中的节点个数；

(3)种群初始化：

(3a)设定种群大小为N，对于指定的初始激活节点数目K，根据最大度启发式方法选 出前K个具有最大度的节点，并将其赋给前N/2个个体X₁......X_N/2，每一个体表示为 X_i＝{x_i1,x_i2,...x_ij,...,x_iK}，其中x_ij代表第i个个体的第j个元素所选定节点的编号， i∈[1,N/2]，j∈[1,K]；

(3b)从个体X₂到个体X_N/2，对个体中的每一位生成一个随机概率p_d∈[0,1]，如果 p_d＞0.5，则将个体中的该位变换为在这个个体内不重复的节点编号；否则，不进行变换；

(3c)利用随机方法对后N/2个个体X_N/2+1......X_N进行初始化；

(3d)利用上述步骤(2)中的待优化的目标函数EDV，计算每个个体的期望传播值，并将 拥有最大期望传播值的个体作为种群的最优个体；

(4)通过进化获得具有最大优化目标函数值的初始激活节点集合：

(4a)设定种群进化迭代次数T，个体交叉变换概率p_c和变异概率p_m，并令当前迭代次 数t＝0；

(4b)选择父代个体：采用锦标赛竞争机制进行父代个体的选择，每一次从种群中随机 选择两个个体，比较两个个体的期望传播值EDV，选择EDV值较大的个体作为一个父代 个体，重复N次上述的选择过程，选出N个父代个体；

(4c)交叉变换操作：随机从父代个体中选择两个个体，对其进行单点交叉变换操作， 从父代个体1中随机选择一个节点，对于该节点以及之后的节点均产生一个介于[0,1]之间 的随机概率，如果随机概率小于交叉变换概率p_c且父代个体1中不包含父代个体2中的对 应节点，则进行对位交叉交换，产生两个子代个体；否则，不进行交叉变换；

重复N/2次上述交叉变换过程，产生N个子代个体；

(4d)对于上述子代种群中的每一个个体，对其每一位生成一个介于[0,1]之间随机概率， 如随机概率小于p_m，则将个体中的该位变换为这个个体内不重复的节点编号；如果随机概 率大于p_m，则该位不进行变换；

(4e)从经过上述(4c)和(4d)操作后的子代种群中选择出具有最大EDV值的个体作为最 优的子代个体，对其进行局部搜索，产生新的最优子代个体；

(4f)从父代种群和子代种群中选择前N个最大EDV值的个体作为下一代的种群，用来 进行下一次的迭代；比较种群最优个体与上述(4e)过程中产生的新的最优子代个体的EDV 值，选择具有较大EDV值的个体作为当前种群最优个体，令t＝t+1；

(4g)判断是否终止：如果迭代次数t满足预先设定的次数T，即获得了具有最大优化目 标函数值的初始激活节点集合，并执行步骤(5)；否则，重复步骤(4b)至步骤(4f)；

(5)输出步骤(4f)中的种群最优个体所包含的K个节点。

本发明与现有技术相比具有如下优点：

第一，本发明由于采用了一种基于种群的进化方法，能够在影响最大化这类组合优化 问题中找到全局最优解，克服了传统方法在解决该问题中易陷入局部最优的这一问题；

第二，本发明由于选取期望传播值函数作为优化的目标方程，能够快速地计算出初始 激活节点集合的影响传播范围，减小了时间复杂度，克服了现有技术具有较高时间复杂度 的问题；

第三，本发明由于引入了针对于网络影响最大化这一特定问题的局部搜索策略，能够 更加有效地搜索出影响力较好的节点组合。

附图说明

图1为本发明的实现流程图；

图2为本发明与现有方法在广义相对论与量子宇宙论科学合作网络中找出的初始激活 节点集合的影响传播范围比较图；

图3为本发明与现有方法在高能物理科学合作网络中找出的初始激活节点集合的影响 传播范围比较图。

具体实施方式

参照图1，本发明的实现步骤如下：

步骤1：输入目标网络G＝(V,E)，其中，V表示网络中的节点集合，E表示网络中边 的集合。

步骤2：确定目标函数。

(2a)设定传播概率p和初始激活节点数目K；

(2b)根据目标网络G的连接形式，找出初始激活节点集合A的邻居节点集合 ${\mathrm{Neighbor}}_A=\left\{\omega \right|\exists \omega \in A,\mu \notin A,\mathrm{\omega \mu }\in E\};$

(2c)对于邻居节点集合Neighbor_A中的每个邻居节点μ，计算其与初始激活节点集合A 连接的节点个数σ_μ＝|{ω|ω∈A,ωμ∈E}|；

(2d)构建期望传播值函数EDV，并将其确定为待优化的目标函数：

$\mathrm{EDV}\left(A\right)=K+\underset{\mu \in {\mathrm{Neighbor}}_A}{\Sigma }(1-{(1-p)}^{{\sigma }_{\mu }}).$

步骤3：利用最大度启发式方法对种群进行初始化。

(3a)设定种群大小为N；

(3b)利用最大度启发式方法找出网络中具有前K个最大度的节点，并将其编号赋给初 始种群的前N/2个个体；

(3c)从第2个个体到第N/2个个体，对个体中的每一位生成一个随机概率p_d∈[0,1]， 如果p_d＞0.5，则将个体中的该位变换为在这个个体内不重复的节点编号；否则，不进行变 换；

(3d)利用随机方法对后N/2个个体进行初始化；

(3e)利用上述步骤2中待优化的目标函数EDV(A)，计算种群中每个个体的期望传播 值，并将拥有最大期望传播值的个体作为种群的最优个体。

步骤4：通过进化获得具有最大优化目标函数值的初始激活节点集合。

(4a)参数初始化：设定种群进化迭代次数T，个体交叉变换概率p_c和变异概率p_m，并 令当前迭代次数t＝0；

(4b)采用锦标赛竞争机制选择父代种群：

(4b1)从种群中随机选择出两个个体，比较两个个体的期望传播值，选择期望传播值较 大的那个个体作为一个父代个体；

(4b2)重复步骤(4b1)共N次，选择出N个父代个体。

(4c)交叉变换操作：

(4c1)从N个父代个体中随机选择出两个父代个体；

(4c2)从选择出的两个父代个体的第一个个体中随机地选择一个节点i；

(4c3)对节点i产生一个介于[0,1]之间的随机概率p_i；

(4c4)将随机概率p_i与交叉概率p_c进行比较，如果p_i＜p_c，且被选择出的第一个父代个 体中不包含被选择出的第二个父代个体中的第i位节点，被选择出的第二个父代个体中也不 包含被选择出的第一个父代个体中的第i位节点，则将这两个父代个体的第i位节点进行对 位交叉交换；否则，不进行交叉变换；

(4c5)将节点i与初始激活节点数目K进行比较，如果i＝K，则执行步骤(4c6)；否则， 令i＝i+1，重复上述步骤(4c3)至步骤(4c4)；

(4c6)将经过上述交叉变换后的两个父代个体分别作为两个子代个体；

(4c7)重复上述步骤(4c1)至步骤(4c6)共N/2次，产生N个子代个体。

(4d)变异操作：

(4d1)对上述N个子代个体的每一个个体的每一位，生成一个介于[0,1]之间的随机概率 值，并用s_a,b表示第a个个体的第b个位的随机概率，a∈[1,N]，b∈[1,K]；

(4d2)将上述产生随机概率s_a,b与变异概率p_m进行比较，如果s_a,b＜p_m，则将第a个个 体的第b位变换为第a个个体所包含节点以外的一个随机节点；否则，该位不进行变换。

(4e)进行局部搜索：

(4e1)利用待优化的目标函数计算每个个体的期望传播值，并选择出具有最大期望传播 值的个体作为子代最优个体；

(4e2)设定搜索标志位m，并令m＝1；

(4e3)将子代最优个体的第m位变换为一个邻居节点，生成一个新个体；

(4e4)利用待优化的目标函数重新计算新个体的期望传播值，如果期望传播值大于原个 体的期望传播值，则表示邻域搜索成功，则对新个体重复上述步骤(4e3)；如果新个体的期 望传播值小于等于原个体的期望传播值，表示邻域搜索失败，则原个体的第m位节点保持 不变；

(4e5)将搜索标志位m与初始激活节点数目K进行比较，如果m＝K，则局部搜索操作 完成；否则，令m＝m+1，重复上述步骤(4e3)至步骤(4e4)；

(4f)更新种群和精英保留：

(4f1)从N个父代个体和N个子代个体中选择拥有前N个最大期望传播值的个体作为 下一代种群；

(4f2)将种群最优个体与子代最优个体的期望传播值进行比较，保留期望传播值较大的 那个作为下一代种群的最优个体，并令t＝t+1。

(4g)判断进化是否终止。

如果种群当前迭代次数t满足预先设定的进化次数T，即获得了具有最大优化目标函数 值的初始激活节点集合，并进行步骤5；否则，重复步骤(4b)至步骤(4f)。

步骤5：将最后一代种群的最优个体所包含的K个节点，作为最佳初始激活节点集合 并输出。

本发明的效果可以通过以下仿真进一步说明：

1.仿真条件与参数。

本实例在Intel(R)Core(TM)2Duo CPU 2.33GHz Windows 7系统下，Matlab R2012a运 行平台上，完成本发明与现有最大度启发式方法和最短距离启发式方法的仿真实验。

参数设置：种群大小N＝300，种群进化迭代次数T＝300，交叉概率为p_c＝0.9，变异概 率为p_m＝0.1。本实验针对初始激活节点个数K取1～30的情况，分别进行了实验。每个算 法选出的K个初始激活节点在独立级联信息传播形式下进行10000次独立传播，利用其平 均值作为该激活节点集合的平均影响范围，用于评价初始激活节点集合的影响传播能力。 平均影响范围越大，则代表初始激活节点集合的影响传播能力越大，即对于影响最大化问 题，该初始激活节点集合选取的越有效。

2.仿真实验内容。

仿真实验1，广义相对论与量子宇宙论科学合作网络仿真实验。

本仿真中使用斯坦福大学收集的大规模网络数据集中的广义相对论与量子宇宙论科学 合作网络作为实验对象。该网络一共包含有5242个节点，28980条边。其中每一个节点代 表一位广义相对论与量子宇宙论领域的学者，连接每两个节点的每一条边代表这两个节点 所对应的两个学者合著过一篇相关领域的论文。该网络涵盖了Arxiv电子数据库中，从1993 年1月至2003年4月，共124个月的所有相关领域的论文。该网络属于典型的社交网络， 具有社交网络的所有相关特征。

在本实验中，利用本发明方法和现有度最大启发式方法以及最短距离启发式方法这三 种方法分别仿真当传播概率p＝0.01和p＝0.05时，初始激活节点集合个数K为1～30的情 况；每种方法分别独立运行30次并取其各自的平均值，仿真实验结果如图2所示。其中图 2(a)和图2(b)分别显示了p＝0.01和p＝0.05时，这三种方法找出的初始激活节点集合的平均 影响范围比较。

从图2(a)中可以看出，当传播概率p＝0.01时，最大度启发式方法和最短距离启发式方 法找出的初始激活节点集合的平均传播影响范围相当。而本发明方法找出的初始激活节点 集合的平均传播影响范围要大于最大度启发式方法、最短距离启发式方法找出的初始激活 节点集合的平均传播影响范围。当初始激活节点数目K＝30时，本发明方法找出的初始激活 节点集合比最大度启发式方法、最短距离启发式方法找出的初始激活节点集合的平均传播 影响范围增大了30％。这说明本发明在解决影响最大化问题时更加有效。

从图2(b)中可以看出，当传播概率p＝0.05时，与最大度启发式方法以及最短距离启发 式方法相比，本发明的更加具有优势。当初始激活节点数目K＝30时，本发明方法找出的初 始激活节点集合比最大度启发式方法、最短距离启发式方法找出的初始激活节点集合的平 均传播影响范围增大了45％左右。显然，本发明方法在解决影响最大化问题中有着明显的 优势。

仿真实验2，高能物理科学合作网络仿真实验。

本仿真中使用陈伟等人在“Efficient influence maximization in social networks” (《Processdings of the 15th ASM SIGKDD International Conference on Knowledge  Discovery and Data Mining》，2009)中使用的高能物理科学合作网络作为实验对象。该网 络统计了自1991年至2003年以来，高能物理领域论文的合著情况，共含有15233个节点， 58891条边。高能物理科学网络中每一个节点代表一个高能物理领域的科学家，每条边表示 两个科学家合著过一篇论文。如果两个科学家共同合著了N篇论文，则其对应的两个节点 之间有N条并行的边连接。

在本实验中，利用本发明方法和度最大启发式方法以及最短距离启发式方法分别仿真 了当传播概率p＝0.01以及p＝0.05时，初始激活节点集合个数K为1～30的情况，每种方 法分别独立运行30次并取其各自的平均值，仿真实验结果如图3所示。其中图3(a)和图3(b) 分别显示了p＝0.01和p＝0.05时，所述三种方法找出的初始激活节点集合的平均影响范围 比较。

从图3(a)可以看出，当传播概率p＝0.01，K＝1～30时，本发明找出的初始激活节点集 合的平均影响范围均优于最大度启发式方法、最短距离启发式方法找出的初始激活节点集 合的平均影响范围，这说明本发明方法可以从高能物理科学合作网络中找出比最大度启发 式方法、最短距离启发式方法影响传播能力更好的初始激活节点集合。

从图3(b)可以看出，当传播概率p＝0.05，K＝1～30时，本发明方法找出的初始激活节 点集合的平均传播影响范围仍优于最大度启发式和最短距离启发式两种方法。这充分说明 本发明的方法能有效地解决大规模社交网络影响最大化问题。

在上述两个实验中，当K＝30时，本发明方法找出初始激活节点集合仅需要900秒左右， 而传统的贪婪算法需要几个甚至十几个小时才能找到有效的初始激活节点集合，这充分说 明了本发明算法能够大大地减小时间复杂度。

综上所述，本发明将期望传播值作为进行优化的目标函数，采用基于文化基因的进化 算法来优化目标函数，并针对影响最大化问题引入了特定的局部搜索策略，构造出基于文 化基因算法的社交网络影响最大化方法，与现有最大度启发式方法和最短距离启发式方法 对比不仅可以找出平均影响范围更大的初始激活节点集合，而且大大地缩短了时间复杂度， 这使得本发明方法能够更加有效地用于解决社交网络的影响最大化问题。