一种多主题消息传播中结构洞节点的挖掘方法

摘要

本发明公布了一种多主题消息传播中结构洞节点的挖掘方法，以网络中传递的消息作为输入数据，包括：先令各节点的结构洞分数为零；生成综合网络拓扑结构和各主题下的子图；对各主题下的子图分别进行社区划分；通过多主题打分方法对各个节点进行多主题结构洞打分，得到各个节点的结构洞分数；输出结构洞分数最高的k个节点，作为结构洞节点。本发明提供方法能够准确高效的挖掘出有价值的结构洞节点，解决多主题下的结构洞挖掘问题；在保持较高的时间效率基础上，显著提升了结构洞节点挖掘结果的准确率；且综合考虑多主题下节点对消息传播的影响。

说明书

技术领域

本发明涉及社交网络分析领域，尤其涉及一种在多主题消息传播中起到重要作用的结构洞节点的挖掘方法。

背景技术

网络平台的流行，催生出人们对社交网络分析的极大兴趣，研究如何挖掘结构洞节点是其中的关键领域。结构洞节点即连接不同社区的节点；它掌握多个社区的信息动向、控制信息在不同社区之间的传播，因而发挥重要作用。例如，若某位研究人员是结构洞节点，他可以将一个与之相连社区的技术应用到另一个社区的研究问题中，或综合几个社区的研究思路来谋求创新。良好的分析和利用已有的主题信息和网络拓扑结构信息，是挖掘结构洞节点的有效途径，这对于后续的社交网络分析领域(如，社区发现及网络中边类型的预测)有着重要的帮助。

现有结构洞挖掘领域的研究基于网络拓扑结构分析，均没有考虑到传播内容的主题分布，对传播内容不敏感。现有研究中，或对于经过节点的最短路径计数，在降序排序中选择前k个节点作为结构洞节点；或对于节点不直接相连的邻居节点对数进行计数，选择计数值最高的前k个节点作为结构洞节点；或使用Google的PageRank算法对每个节点的重要性进行评估，选择PageRank得分最高的前k个节点作为结构洞节点；亦有研究将参与社区数量、最小切等因素和方法考虑在内。然而，现有的传统结构洞挖掘模型只考虑了拓扑结构以及与拓扑结构相关的社交理论，往往忽视了社交主题的影响，没有综合考虑多主题的结构洞节点挖掘，无法在社交网络中挖掘到更有价值的信息，难以做到更加贴近真实环境。

发明内容

为了克服上述现有技术的不足，本发明提供一种多主题下的结构洞节点的挖掘方法，通过多主题打分方法对节点进行结构洞打分评估，由此得到的分数最高的k个节点，即为所求的挖掘结果。本发明提供方法能够准确高效的挖掘出有价值的结构洞节点，解决多主题下的结构洞挖掘问题，满足实际应用需求。

本发明的原理是：综合考虑多主题的结构洞节点挖掘更加贴近真实环境，能够在社交网络中挖掘到更有价值的信息。因此，本发明考虑到社交网络中信息多主题的因素，提出一套多主题下结构洞节点挖掘方法。依据结构洞的特点，它能够在多个社区之间的信息传播中发挥重要作用；在多主题的条件下，哪些节点更能为与之关联社区提供新颖独特、有价值的信息，则更加具有结构洞所体现的意义；而消息的新颖和价值，往往由于人们之前对它了解和接触的并不多，例如学科交叉所带来的优势。本发明进一步分析多主题条件下影响结构洞打分的三项因素，帮助挖掘出一批与传统方法不同的、更加具有现实意义和价值的结构洞节点。本发明首先将各节点结构洞分数初始化为零；先依据原始输入数据生成综合网络拓扑结构及各主题下的子图；对各主题下的子图分别进行社区划分；再通过多主题打分方法对节点进行结构洞打分评估，由此得到的分数最高的k个节点，即为所求的挖掘结果。该方法能够准确高效的挖掘出有价值的结构洞节点，解决多主题下的结构洞挖掘问题，满足实际应用需求。

本发明提供的技术方案是：

一种多主题消息传播中的结构洞节点的挖掘方法，所述方法以网络中传递的消息作为输入数据(即消息发布节点、被转发节点、以及消息内容)，根据节点对多主题在社区间传播的促进作用和贡献程度进行打分，从而得到各节点的结构洞分数；具体包括如下步骤：

1)首先令各节点的结构洞分数H(v)为零；

2)生成综合网络拓扑结构G＝(V,E)和各主题t下的子图G^t＝(V,E^t)；

3)对各主题t下的子图分别进行社区划分，得到一组社区的集合

4)通过多主题打分方法对各个节点进行多主题结构洞打分，得到其结构洞分数H(v)；

5)输出结构洞分数最高的k个节点，作为结构洞节点。

针对上述多主题下的结构洞节点挖掘方法，进一步地，

步骤2)所述生成综合网络拓扑结构及各主题下子图的方法，具体包括如下步骤：

21)利用隐含狄利克雷分布模型(Latent Dirichlet Allocation，简称LDA)，将每条消息内容分解为主题向量其中表示该条消息内容在t_i主题上的分量；

22)对于每条消息k，取其在网络上被转发的次数r_k作为该消息的影响力衡量指标；

23)计算每对节点a与b之间的边上信息：其中，分量包含边(a,b)在t_i主题上的边权和影响力信息，具体为：计算边上经过的所有消息在t_i主题下的主题分量之均值，即体现边(a,b)在t_i主题下的边权，称为度量边(a,b)上经过的所有消息k在t_i主题下的影响力，即

24)每对节点经过上述步骤22)-23)的处理，得到综合网络拓扑结构G＝(V,E)，其中V为节点集，E为e组成的边集；

25)生成主题t_i下的子图其中由各条边在t_i上的分量组成，即

步骤3)所述对各主题下的网络子图进行社区划分的方法，具体包括如下步骤：

31)计算V所有可能的子集，作为潜在社区S；

为减少时间消耗，可设置至少包含节点个数的阈值；称这样的子集为潜在社区S；

针对每个主题t_i，执行操作32)～36)，得到子图上的一组社区：

32)对每个潜在社区S，计算子图中，S包含边的个数(仅考虑边权分量大于阈值q的边，q一般取0.005～0.01之间)，记为m_s；

33)对每个潜在社区S，计算子图中，S向外伸出的边的个数(仅考虑边权分量大于阈值q的边，q一般取0.005～0.01之间)，即边的一个顶点在S中，一个顶点不在S中，记为c_s；

34)计算跨界边比例f(S)，即跨S的边在S所涉及的所有边中所占的比例；该值越大，S成为社区的可能性越低；

35)以1/f(S)作为潜在社区S成为社区的评分依据，对所有潜在社区进行降序排名；

36)选择排名前l个潜在社区，即得子图上的一组社区

式2中，为主题t_i下一组社区的集合；为其中的一个社区；l一般取潜在社区总数的5％～10％；

由此得到各主题下的网络子图相对应的社区集合；

步骤4)所述对节点进行多主题结构洞打分的方法，具体包括如下步骤：

401)首先，计算社区在主题t_i上的活跃度(或称贡献度)该指标反映若作为消息供源，提供信息的可靠性和质量：

式3中，在步骤23)中计算，表示边上经过的所有消息在t_i主题下的影响力；

402)将各主题t_i下满足式4的社区记为典型社区：

403)将各主题t_i下满足式5的边记为弱边：

式5中，在步骤23)中计算，表示t_i主题下的边权；

404)遍历每个节点的连接情况：若节点a既通过边e连接t₁主题下典型社区也通过边e′连接t₂主题下典型社区且连接a与的边e在分量上是弱边，则认为e上传播的关于t₂的消息，是经由a对的影响；将上述情况记为a的一个加分项，即对应的t₁、t₂、的信息保存为一项；作为消息供源，其活跃度影响a作为结构洞节点的价值；

405)e上传播的t₂消息的影响力为亦体现a的结构洞价值，在步骤23)中计算；

406)针对每一节点a，404)中所述每个加分项将对a在t₂主题下的结构洞分数H(a,t₂)贡献的加分值；

407)a在t₂主题下的结构洞分数H(a,t₂)先赋为406)中a的所有加分值之和；

同于步骤404)-407)，逐个处理V中各个节点；

408)考虑到社区与有重叠节点，此类节点所发挥的结构洞成分与a构成竞争；对于a的每个加分值进行更新处理，即：

式6中，h表示社区与重叠部分的节点，H(h,t₂)表示节点h在t₂主题下的结构洞分数；

409)使用新的加分值tmp′更新a在t₂主题下的结构洞分数H(a,t₂),更新后的H(a,t₂)即为所有tmp′之和；

410)同于步骤408)-409)，逐个处理V中各个节点，得到节点在各主题下的结构洞得分；节点在所有主题上的结构洞总分为：

其中T为所有主题的集合；上式反映在某一主题上能力突出的节点、比各主题能力平平的节点更能获得较高的结构洞分数；

411)筛选得分最高的k个节点，即为挖掘出的结构洞节点；k一般取总节点数的1％～3％。当k的取值偏大时，召回率较高、准确率偏低；当k的取值偏小时，准确率较高、召回率偏低。

与现有技术相比，本发明的有益效果是：

本发明提供一种多主题下的结构洞节点的挖掘方法，通过多主题打分方法对节点进行结构洞打分评估，由此得到的分数最高的k个节点，即为所求的挖掘结果。本发明提供方法能够准确高效的挖掘出有价值的结构洞节点，解决多主题下的结构洞挖掘问题；在保持较高的时间效率基础上，显著提升了结构洞节点挖掘结果的准确率，可以成为真实世界中挖掘结构洞节点的有效手段；且综合考虑多主题下，节点对消息传播的影响，相比于传统模型仅仅基于网络拓扑结构进行挖掘，本方法得到的结构洞节点更加具有现实意义和价值。

附图说明

图1是本发明提供的结构洞节点挖掘方法的整体流程框图。

图2是本发明生成综合网络拓扑结构及各主题下子图的流程框图。

图3是本发明的对各主题下的网络子图进行社区划分的流程框图。

图4是本发明的多主题下结构洞打分的流程框图。

具体实施方式

下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。

本发明提供一种多主题下的结构洞节点挖掘方法，图1是本发明提供方法的整体流程图，首先将各节点结构洞分数初始化为零；接着依据原始输入数据，生成综合网络拓扑结构及各主题下的子图；再对各主题下的子图分别进行社区划分；进一步地，基于多主题打分方法对节点进行结构洞打分评估；由此得到分数最高的k个节点，即结构洞节点。具体包括如下步骤：

1)将各节点结构洞分数初始化为零

因为本方法主要针对大规模社交网络的结构洞节点挖掘问题，故首先将所有节点的结构洞分数初始化为0；经过后续计算，最终选择分数最高的k个节点作为输出结果。

2)生成综合网络拓扑结构，及各主题下子图

本步骤为后序社区划分及计算结构洞分数提供基础数据。简单来说，首先利用主题模型对每条消息内容进行分解；计算每对节点边上的信息；合成整个网络的综合拓扑结构；并进一步拆分为各个主题下的子图。

图2是本发明的生成综合网络拓扑结构及各主题下子图的流程图。基本流程包括如下过程：

21)利用主题模型，将每条消息内容分解为主题向量

22)计算每条消息的影响力；

23)计算每对节点之间的边上信息：具体分为计算边权分量和边影响力分量；

24)合并每对节点的边上信息，得到综合网络拓扑结构G＝(V,E)；

25)基于综合网络拓扑结构拆分出各主题下的子图；

3)对各主题下的网络子图进行社区划分

由于后续结构洞打分过程中，需要提取到与节点相连的社区以及计算社区在某一主题上的活跃度，以便评估节点对于社区之间消息传递所能发挥的作用，因此需要首先进行社区的划分。简单来说，首先计算所有潜在社区内部包含的边数、以及向外伸出的边数，计算跨界边比例；并以跨界边比例的倒数作为潜在社区被选为社区的排名依据，选定前l个潜在社区并记录每个潜在社区所包含的节点，至此社区划分完成。

图3是本发明的根据拓扑结构划分各子图中社区的流程图。基本流程包括如下过程：

31)计算V所有可能的潜在社区S；

32)针对每个子图下的每个潜在社区S，计算S包含边的个数m_s；

33)针对每个子图下的每个潜在社区S，计算S向外伸出的边的个数c_s；

34)计算跨界边比例f(S)；

35)根据1/f(S)对所有潜在社区进行降序排名；

36)选择前l个潜在社区，即得子图上的一组社区

通过上述方法，可以根据拓扑结构对各个子图进行社区划分，为后续步骤提供支撑。

4)对节点进行多主题结构洞打分

对节点进行多主题结构洞打分时，即需考虑节点对于多主题消息在社区间传播所起到的促进作用，也需考虑同类结构洞节点之间的竞争关系，综合进行打分。这一步是本专利的核心，体现本方法与传统的基于拓扑结构进行结构洞挖掘的不同。本方法实则通过分析和利用原始数据中消息的内容，追溯节点对于多主题消息在社区间传播所发挥的作用，从而更加准确的挖掘结构洞节点。

图4是本发明的对节点进行多主题结构洞打分的流程图。对节点进行结构洞打分的基本流程包括如下过程：

41)计算社区在主题t_i上的活跃度

42)标记各主题t_i下的典型社区

43)标记各主题t_i下的弱边；

44)遍历每个节点的连接情况，即：节点同时连接两个不同主题下的典型社区、且与其中之一的连边上存在另一主题的弱边分量；

45)针对每一节点a，计算44)中所述每个加分项对H(a,t₂)贡献的加分值；

46)a在t₂主题下的结构洞分数H(a,t₂)先赋为a的所有加分值之和；同于步骤44)-46)，逐个处理V中各个节点；

47)根据竞争规则，更新a的每个加分项的加分值，即为tmp′；

48)使用新的加分值tmp′更新a在t₂主题下的结构洞分数H(a,t₂)；

49)同于步骤47)-48)，逐个处理V中各个节点,计算各节点在各主题下的结构洞得分和节点在所有主题下的结构洞总分；

通过上述方法，可以筛选出V中得分最高的k个节点，即得到挖掘出的结构洞节点。

本发明以下实施例针对新浪微博平台，使用平台的用户作为网络节点，输入数据为每条社交平台上发布的消息内容、发布节点和被转发节点。经过LDA主题模型的分析，得到主题向量。通过本发明提供的多主题下的结构洞节点挖掘方法，提取网络拓扑结构信息、划分社区、并挖掘出结构洞节点。该平台经过多年经营，使用用户广泛，拥有海量数据资料。快速挖掘多主题下的结构洞节点，能够帮助工作人员更好的进行社交网络分析，对于研究影响力最大化、舆论控制、市场营销和广告投放等领域也有着重要作用。传统仅仅基于网络拓扑结构进行结构洞节点发掘的方法，已渐渐不适合于日趋复杂的现实世界社交平台。现采用多主题下的结构洞节点挖掘方法，以提供更准确的结构洞节点挖掘策略。

首先，利用平台接口等工具，采集并存储相关数据，例如发布用户id、被转发用户id、消息内容等信息。按照如下步骤，对各节点进行打分：

步骤一：初始化结构洞分数为零；

步骤二：利用主题模型，将每条消息内容分解为主题向量w；

主题向量其中表示该条消息内容在t_i主题上的分量；例如，微软官方微博发布了一则关于新产品Surface>

步骤三：计算每条消息的影响力；

对于每条消息k，本实施例取其在网络上被转发的次数r_k作为该消息的影响力衡量指标；例如Surface>

步骤四：计算每对节点之间的边上信息；

计算每对节点a与b之间的边上信息：其中，分量包含边(a,b)在t_i主题上的情况，具体为：计算边上经过的所有消息在t_i主题下的主题分量之均值，即体现边(a,b)在t_i主题下的边权，称为度量边(a,b)上经过的所有消息k在t_i主题下的影响力，即例如，其中为边在生活方式主题下的信息；为边在工作方式主题下的信息；为边在计算机主题下的信息；以为例，

步骤五：合并每对节点的边上信息，得到综合网络拓扑结构；

每对节点都经过步骤四进行处理，合并得到综合网络拓扑结构G＝(V,E)，其中V为节点集，E为e组成的边集；例如，提取到的微博网络包括1024个节点和5301条边；

步骤六：基于综合网络拓扑结构拆分出各主题下的子图；

生成主题t_i下的子图，记为其中由各条边在t_i上的分量组成，即

步骤七：计算所有潜在社区S；

计算V所有可能的子集，作为潜在社区S；本实施例中，为减少时间消耗，可设置节点个数阈值(一般取3个节点以上)，节点个数大于阈值的子集为潜在社区S；

步骤八：通过式1计算得到跨界边比例f(S)；

跨界边比例f(S)为跨S的边在S所涉及的所有边中所占的比例；该值越大，S成为社区的可能性越低；

其中，对每个潜在社区S，计算子图中，S包含边的个数(仅考虑边权分量大于阈值q的边，q一般取0.005～0.01之间)，记为m_s；计算子图中，S向外伸出的边的个数(仅考虑边权分量大于阈值q的边，q一般取0.005～0.01之间)，即边的一个顶点在S中，一个顶点不在S中，记为c_s；

步骤九：以1/f(S)作为潜在社区S成为社区的评分依据，对所有潜在社区进行降序排名，选择前l个潜在社区，即得例如，在计算机主题下，划分得到5个社区

对各社区，采用多主题打分方法进行打分，包括以下步骤：

步骤十：计算各社区在对应主题下的活跃度；

计算社区在主题t_i上的活跃度(或称贡献度)该指标反映若作为消息供源，提供信息的可靠性和质量：

式3中，在步骤四中计算，表示边上经过的所有消息在t_i主题下的影响力；

步骤十一：标记各主题t_i下的典型社区和弱边；

即当各主题t_i下的社区满足式4(阈值一般取0.4以上)：

为各主题t_i下的典型社区；

即当各主题t_i下的边满足式5(阈值一般取0.2以下)：

为各主题t_i下的弱边；

步骤十二：遍历每个节点的连接情况，标记所有可加分案例；

遍历每个节点的连接情况：若节点a既通过边e连接t₁主题下典型社区也通过边e′连接t₂主题下典型社区且连接a与的边e在分量上是弱边，则认为e上传播的关于t₂的消息，是经由a对的影响；将上述情况记为a的一个加分项，即对应的t₁、t₂、的信息保存为一项；作为消息供源，其活跃度影响a作为结构洞节点的价值；例如，节点a既连接关于生活方式的典型社区、又连接关于计算机的典型社区，且连接a与生活方式下的典型社区的边在计算机主题中是弱边，可认为这条弱边上传播的关于计算机的消息是受到计算机典型社区的影响；

另外，e上传播的t₂消息的影响力为亦体现a的结构洞价值，在步骤四中计算；

步骤十三：对每一节点，计算每个加分项贡献的加分值；

针对每一节点a，每个加分项对a在t₂主题下的结构洞分数H(a,t₂)贡献的加分值；计算得到每个加分项贡献的加分值；

步骤十四：结构洞分数先赋为节点的所有加分值之和；

将节点的所有加分值之和作为结构洞分数；同于步骤十二、十三、十四，逐个处理V中各个节点；

步骤十五：根据两典型社区的重叠节点，按竞争规则更新节点的每个加分项的加分值；

考虑到社区与有重叠节点，此类节点所发挥的结构洞成分与a构成竞争；对于a的每个加分项进行更新处理，即：

式6中，h表示社区与重叠部分的节点，H(h,t₂)表示节点h在t₂主题下的结构洞分数；

步骤十六：使用新的加分值tmp′更新节点的结构洞分数H(a,t₂),更新后的H(a,t₂)即为所有tmp′之和；

依据步骤十五、十六，逐个计算每个节点在各主题下的结构洞得分；节点在所有主题上的结构洞总分为：

其中，T为所有主题的集合；上式反映在某一主题上能力突出的节点、比各主题能力平平的节点更能获得较高的结构洞分数；筛选得分最高的k个节点，即为挖掘出的结构洞节点。

按照上述步骤对下一节点进行计算，直到所有节点都计算完毕，算法结束，筛选得分最高的k个节点，即为挖掘出的结构洞节点。

上述具体过程运用到社交平台用户节点、交互消息的内容等数据，综合考虑多主题条件下结构洞对消息传播的影响机制，对结构洞节点进行挖掘。通过本发明提供的技术方案，社交平台管理和分析人员可以极大的提高效率和决策的科学性，快速准确的获知在消息传播过程中起到关键作用的结构洞节点，并以此作为管理决策的合理依据。

需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。