[0005] 发明目的：针对上述问题，本发明提供一种节约时间和人力成本，并且降低 了时间复杂度的线上产品推销选取初始用户的方法。
[0006] 技术方案：本发明提出一种线上产品推销选取初始用户的方法，包括如下步 骤：
[0007] 步骤1：对线上产品的数据集进行处理，得到真实的拓扑结构图G(V,E)； 其中，V表示G中的节点集合，E表示G中的边的集合，输入P,P是独立级联 模型中一个被激活节点v激活其未激活的出度邻居节点的概率，输入S，S是选 取种子节点的个数,具体方法为：
[0008] 步骤1.1：删除线上产品的数据集中存在的自环，得到真实的拓扑结构图 G(V,E)，G是邻接矩阵；
[0009] 步骤1.2：节点的势就是G中有多少个节点，边的势就是G中有多少条边， 求得节点的势m和边的势n；
[0010] 步骤1.3：独立级联是一种概率模型，当一个节点v被激活时，它会以概率P 对它未激活的出边邻居节点w尝试激活，这种尝试仅仅进行一次，而且这些尝试 之间是相互独立的，即v对w的激活不会受到其他节点的影响。概率P是实验一 开始定义的，因此在根据社交网络中用户邻居选取影响力最大化初始节点中， P＝1/degree。degree是节点的度，计算邻接矩阵G的每一行的和记为矩阵Degree， 是节点对应的度。
[0011] 步骤2：计算每个节点的t阶邻居，把求得的每个节点的t阶邻居放在一个 大集合SubList里，t＝1，2，3，4，5，6，7，8，9，10，具体方法为：
[0012] 步骤2.1：对步骤1.1中的邻接矩阵G的行/列进行编号，第一行/列是1，第 二行/列是2…依次标号；
[0013] 步骤2.2：求节点i的1阶邻居，设定一个m行m列的空矩阵D，m是步骤 1.2中求得的节点的势。把矩阵D的第i行第i列的0改为1，计算矩阵D*G， 求得的是节点i的1阶邻居的子图，定义为J1；
[0014] 步骤2.3：求节点i的2阶邻居，取邻接矩阵G的第i行，设为矩阵A，把 矩阵A的第i个数改为1，生成一个矩阵B，对角线是矩阵A，其余都为0；计 算矩阵B*G，求得的是节点i的2阶邻居的子图，定义为J2；
[0015] 步骤2.4：求节点i的3阶邻居，首先计算G+G*G，记为矩阵F1，把矩阵 F1中不是0的数都置为1，并且把对角线上的数都置为0；取矩阵F1的第i行， 设为矩阵C1，把矩阵C1的第i个数改为1，生成一个矩阵E1，对角线是矩阵 C1，其余数都为0；计算矩阵E1*G，求得的是节点i的3阶邻居的子图，定义 为J3；
[0016] 步骤2.5：求节点i的4阶邻居，首先计算G+G2+G3，设定为矩阵F2，把 矩阵F2中不是0的数都置为1，并且把对角线上的数都置为0；取矩阵F2的第 i行，设为矩阵C2，把矩阵C2的第i个数改为1，生成一个矩阵E2，对角线是 矩阵C2，其余数都为0；计算矩阵E2*G，求得的是节点i的4阶邻居的子图， 定义为J4；
[0017] 步骤2.6：求节点i的5阶邻居，首先计算G+G2+G3+G4，设定为矩阵F3， 把矩阵F3中不是0的数都置为1，并且把对角线上的数都置为0；取矩阵F3的 第i行，设为矩阵C3，把矩阵C3的第i个数改为1，生成一个矩阵E3，对角线 是矩阵C3，其余数都为0；计算矩阵E3*G，求得的是节点i的5阶邻居的子图， 定义为J5；
[0018] 步骤2.7：求节点i的6阶邻居，首先计算G+G2+G3+G4+G5，设定为矩 阵F4，把矩阵F4中不是0的数都置为1，并且把对角线上的数都置为0；取矩 阵F4的第i行，设为矩阵C4，把矩阵C4的第i个数改为1，生成一个矩阵E4， 对角线是矩阵C4，其余数都为0；计算矩阵E4*G，求得的是节点i的6阶邻居 的子图，定义为J6；
[0019] 步骤2.8：求节点i的7阶邻居，首先计算G+G2+G3+G4+G5+G6，设定 为矩阵F5，把矩阵F5中不是0的数都置为1，并且把对角线上的数都置为0； 取矩阵F5的第i行，设为矩阵C5，把矩阵C5的第i个数改为1，生成一个矩阵 E5，对角线是矩阵C5，其余数都为0；计算矩阵E5*G，求得的是节点i的7阶 邻居的子图，定义为J7；
[0020] 步骤2.9：求节点i的8阶邻居，首先计算G+G2+G3+G4+G5+G6+G7， 设定为矩阵F6，把矩阵F6中不是0的数都置为1，并且把对角线上的数都置为 0；取矩阵F6的第i行，设为矩阵C6，把矩阵C6的第i个数改为1，生成一个 矩阵E6，对角线是矩阵C6，其余数都为0；计算矩阵E6*G，求得的是节点i 的8阶邻居的子图，定义为J8；
[0021] 步骤2.10：求节点i的9阶邻居，首先计算 G+G2+G3+G4+G5+G6+G7+G8，设定为矩阵F7，把矩阵F7中不是0的数 都置为1，并且把对角线上的数都置为0；取矩阵F7的第i行，设为矩阵C7， 把矩阵C7的第i个数改为1，生成一个矩阵E7，对角线是矩阵C7，其余数都为 0；计算矩阵E7*G，求得的是节点i的9阶邻居的子图，定义为J9；
[0022] 步骤2.11：求节点i的10阶邻居，首先计算 G+G2+G3+G4+G5+G6+G7+G8+G9设定为矩阵F8，把矩阵F8中不是0的 数都置为1，并且把对角线上的数都置为0；取矩阵F8的第i行，设为矩阵C8， 把矩阵C8的第i个数改为1，生成一个矩阵E8，对角线是矩阵C8，其余数都为 0；计算矩阵E8*G，求得的是节点i的10阶邻居的子图，定义为J10.
[0023] 步骤2.12：所有节点i∈V的1阶节点的子图都在J1中，所有节点i∈V的2 阶节点的子图都在J2中，所有节点i∈V的3阶节点的子图都在J3中，所有节点 i∈V的4阶节点的子图都在J4中，所有节点i∈V的5阶节点的子图都在J5中， 所有节点i∈V的6阶节点的子图都在J6中，所有节点i∈V的7阶节点的子图都 在J7中，所有节点i∈V的8阶节点的子图都在J8中，所有节点i∈V的9阶节点 的子图都在J9中，所有节点i∈V的10阶节点的子图都在J10中，把J1、J2、J3、 J4、J5、J6、J7、J8、J9、J10放在矩阵SubList中。
[0024] 步骤3：把每个节点都当成初始用户，把每个节点的t阶邻居都当成是一个 网络，让每个节点对他的t阶邻居进行R次独立级联模型传播，R是自己定义的 正整数，计算每个节点对他的t阶邻居的平均影响力,t＝1，2，3，4，5，6，7，8， 9，10，具体方法为：
[0025] 步骤3.1：定义一个正整数R，空矩阵In；
[0026] 步骤3.2：计算矩阵G的每一行的和，放在矩阵degree中，矩阵degree中存 放的是每个节点的度；定义循环变量m,m∈[1,R]；
[0027] 步骤3.3：如果m≤R,则跳转到步骤3.4，不然跳转到步骤3.10；
[0028] 步骤3.4：把节点i当成活跃节点，对它的邻居节点v产生影响，使v激活 的概率是p,且机会只有一次；p＝1/degree,degree是步骤302中求得的节点i的度； v属于节点i的t阶邻居，t＝1,2,3,4,5,6,7,8,9,10；
[0029] 步骤3.5：如果节点v被激活成功，那么节点v转为活跃状态，将对其邻接 非活跃节点产生影响；否则，节点v不发生变化；
[0030] 步骤3.6：重复步骤3.3和3.4，直到不能再激活新的节点，传播过程结束；
[0031] 步骤3.7：每个节点在t阶邻居中激活的节点的个数就是它的影响力；
[0032] 步骤3.8：每个节点在它的1阶邻居中的影响力存在矩阵In1中，在它的2 阶邻居中的影响力存在矩阵In2中，在它的3阶邻居中的影响力存在矩阵In3中， 在它的4阶邻居中的影响力存在矩阵In4中，在它的5阶邻居中的影响力存在矩 阵In5中，在它的6阶邻居中的影响力存在矩阵In6中，在它的7阶邻居中的影 响力存在矩阵In7中，在它的8阶邻居中的影响力存在矩阵In8中，在它的9阶 邻居中的影响力存在矩阵In9中，在它的10阶邻居中的影响力存在矩阵In10中；
[0033] 步骤3.9：m＝m+1；
[0034] 步骤3.10：把R次求得的影响力累加起来，然后除以R，求每个节点在其t 阶邻居中的平均影响，放在矩阵In中。
[0035] 步骤4：把节点t阶邻居按照影响力从大到小进行排序，选取每阶邻居中影 响力最大的50个节点，通过比较，发现节点的t'阶邻居影响力最大，t＝1，2，3， 4，5，6，7，8，9，10，且t'∈t，具体方法为：
[0036] 步骤4.1：对矩阵In1,In2,In3,In4,In5,In6,In7,In8,In9,In10里面的值进行从大到 小排序；
[0037] 步骤4.2：选取矩阵In1，In2,In3,In4,In5,In6,In7,In8,In9,In10中的前50个数 值，按顺序放在矩阵Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9,Z10中；
[0038] 步骤4.3：画图，横轴是1到10，是10个数，纵轴是矩阵Z1,Z2,Z3,Z4,Z5,Z6,Z7, Z8,Z9,Z10中的数，发现在t＝t'时,纵轴上的数最大，也就是节点的t'邻居影响力 最大；
[0039] 步骤5：对节点的阶邻居中所有的节点在整个网络中进行K次独立级联模型 传播，t'是步骤5个求到的值，K是自己定义的正整数，在节点的t'阶邻居中选 取最大的S个节点作为初始用户，具体方法为：
[0040] 步骤5.1：定义一个正整数M，从步骤2.12中取出矩阵SubList，并从矩阵 SubList中取出矩阵Jt'，t'∈[1,10]；
[0041] 步骤5.2：定义循环变量n,n∈[1,M],计算矩阵Jt'每一行的和，记为矩阵De， 矩阵De中存放的是节点t'阶邻居的度；
[0042] 步骤5.3：如果n≤M,则跳转到步骤5.4，不然跳转到步骤5.9；
[0043] 步骤5.4：把矩阵Jt'中的节点当成活跃节点，对它的邻居节点w产生影响， 使w激活的概率是p,且机会只有一次；p＝1/degree,degree是步骤5.2中求得的矩 阵De中的数；
[0044] 步骤5.5：如果节点w被激活成功，那么节点w转为活跃状态，将对其邻接 非活跃节点产生影响；否则，节点w不发生变化；
[0045] 步骤5.6：重复步骤5.4和5.5，直到不能再激活新的节点，传播过程结束；
[0046] 步骤5.7：每个节点在线上产品的数据集中激活的节点的个数就是它的影响 力，记为矩阵IN；
[0047] 步骤5.8：n＝n+1；
[0048] 步骤5.9：把M次求得的影响力累加起来，然后除以M，求每个节点在整个 网络中的平均影响，全部放在矩阵LIN中；
[0049] 步骤5.10：对矩阵LIN中的值进行排序，选取值最大的S个，其对应的节 点即为初始用户。
[0050] 本发明采用上述技术方案，具有以下有益效果：本发明针对影响力最大化问 题提出基于节点的t阶邻居快速选取种子节点的方法，通过计算节点的t阶邻居， (t＝1,2…n)计算节点在其邻居子图中的影响力，通过比较，选择使得影响力较高， 效果较好的。确定后，在节点的阶邻居中选择整体影响力最大的作为种子节点。 本方法可以极大地降低计算开销和存储开销，使得选择种子节点的时间大幅度降 低，降低了时间复杂度。
