1.一种基于社区结构的社交网络影响力最大化方法,其特征在于,所述方法包括下列步骤:
(1)如果网站中的两个产品经常被共同购买,就会有一个链接关系,形成一个有向图,获取来自购买网站中产品购买数据,构建社交网络图:G=(V,E),其中G代表社交网络,V代表节点集合,E代表网络的边集合;
(2)划分社区,生成候选节点集:首先采用Louvain算法对输入的网络G进行社区划分,产生M个社区,即C=(C1,C2,...CM),其次找出每个社区的边界节点集Sboundary以及核心节点集Score取并集,形成候选节点集CS,其中Score是根据度中心性选择每个社区数目的10%的度较大的节点作为核心节点集;
(3)启发式地选择节点:启发式的从步骤(2)形成的候选节点集中选择 个潜在影响力最大的节点加入种子节点集S,同时利用线性阈值模型执行种子节点集S的激活过程,产生初始的活跃节点集A,其中k代表目标节点集合S的数目,c代表启发因子;
(4)执行贪心算法:利用贪心算法继续从步骤(3)形成的候选节点集中选择 个边际收益最大的节点加入种子集S,同时利用线性阈值模型进行激活,产生新的活跃节点加入集合A;
步骤(3)中选择潜在影响力最大的节点加入种子节点集,则每个节点的潜在影响力的计算过程如下:
(a)对于图G中的任意一个节点v,首先判断每个节点的社区属性,即核心节点或边界节点,并基于社区结构分别计算每个节点的社区影响力;
(b)对于核心节点,综合节点的度以及节点所在的社区数来评估其社区影响力,计算公式如下:
CI(v)=CD(v)+CS(v)/2其中,CD(v)代表社区的度,CS(v)代表节点所在的社区规模;
(c)对于边界节点,综合节点的度,节点直接相连的社区数以及该节点的邻居社区的社区规模均值来评估其社区影响力,计算公式如下:CI(v)=CD(v)+CN(v)+AvgNS(v)/3其中,CD(v)代表社区的度,CN(v)代表节点直接相连的社区数,AvgNS(v)代表节点的邻居社区的社区规模均值,计算公式为:其中,|Ci(w)|代表节点v的邻居w所在社区的规模;
(d)为了使每个指标对社区影响力的贡献一致,使用归一化标准来优化,综合步骤(b)和(c),网络中每一个节点v的社区影响力定义如下:其中,每一个指标都是归一化以后的结果;
(e)除了步骤(d)得到的社区影响力,每一个节点v对邻居节点w都有一个直接影响力权重bvw,综合两者,网络中每一个节点v的潜在影响力计算如下:其中,w∈neighbor(v), 表示节点w是节点v的非活跃邻居。
2.根据权利要求1所述的一种基于社区结构的社交网络影响力最大化方法,其特征在于,所述步骤(2)中Louvain算法的具体操作步骤如下:(a)合并社区:将网络中的每一个节点当作一个社区,然后基于模块度增益最大化标准决定哪些邻居社区进行合并,重复进行此过程,直到模块度增益不再增长,模块度增益的定义如下:
其中,∑in表示在社团C中的所有边权值之和,∑tot表示所有连接到社团C的边的权值之和,ki,in表示节点i到社团C的所有边的权值之和,m表示网络的总边数;
(b)构建新的网络:将步骤(a)得到的新的社区当作一个新节点,构建新的网络重复执行步骤(a);
(c)这两个阶段重复进行,直到模块度增益不再变化。
3.根据权利要求1所述的一种基于社区结构的社交网络影响力最大化方法,其特征在于,所述步骤(4)中贪心算法的具体操作步骤如下:(a)初始化:对种子节点集S进行初始化;
(b)计算每个节点v的边际收益:其表示为通过加入一个节点v到种子集S中所能带来的最终影响力增量,则计算公式如下:σ(S+v)‑σ(S)
其中,σ(g)表示影响力函数;
(c)选择种子节点:选择影响力增益最大的节点加入种子集S,并对每个节点的影响力进行更新;
(d)重复进行步骤(c),直到选择满足目标的k个节点。