基于标签索引的信息传播多样性最大化快速查询系统

本发明涉及社交网络分析，更确切地说，它涉及基于标签索引的信息传播多样性最大化快速查询系统。

背景技术：

1、在社交网络平台的运营中，信息扩散优化是一项基础性技术，广泛应用于精准营销、内容推荐和舆情引导等业务场景。如何从大量候选用户中筛选出有限数量的种子用户，使信息经由社交关系链传播后能够触达尽可能广泛的受众群体，是该领域持续关注的技术问题。

2、现有技术通常将上述问题建模为社交网络图上的影响力最大化问题。给定图g=(v,e)，节点代表用户，边代表用户间的社交关系，边权表示信息传播概率，要求在预算约束k下选取不超过k个种子节点，使信息扩散期望规模最大化。该问题已被证明为np-hard问题，但其目标函数具有单调性和子模性，可采用贪心策略获得具有近似保证的求解效果。

3、在工程化求解方面，主流技术方案基于反向信息采样，通过在全图中生成大量反向可达集来估计节点影响力，单次查询的复杂度与网络规模呈近线性关系，后续改进方案进一步优化了采样策略以减少冗余计算。然而，上述方案在实际系统部署中仍存在以下技术缺陷：

4、其一，查询计算开销与网络整体规模强相关。每次查询均需在全局范围内遍历或采样大量节点及边，当网络规模达到亿级节点和百亿级边时，单次查询即消耗大量计算资源，响应时延难以满足在线服务要求。

5、其二，服务器端存在系统性资源瓶颈。上述方案需为每个并发查询维护独立的反向可达集或反复执行蒙特卡洛模拟，导致cpu长期高负荷运行、内存峰值溢出以及频繁的i/o阻塞，严重制约了服务系统的吞吐量和响应稳定性。

6、其三，批量并发查询处理能力不足。不同业务方在同一时段提交的大量查询具有各异的候选节点集合和预算约束，现有技术对各查询独立执行完整计算，无法共享中间结果，总负载随查询数量线性增长，难以支撑平台级的批量处理需求。

7、此外，图查询领域存在一类标签索引技术，通过预选地标节点并存储其与图中其他节点的关系信息，在查询阶段仅需访问索引数据而无需遍历全图，已在最短路径查询等任务中获得显著加速效果。然而，将该类标签索引框架应用于信息传播多样性最大化查询的技术路径尚不明确，主要挑战在于地标节点的选择策略、索引数据结构的设计以及基于索引的近似查询质量保证。

技术实现思路

1、本发明的目的是克服现有技术中的不足，提供了基于标签索引的信息传播多样性最大化快速查询系统。

2、第一方面，提供了基于标签索引的信息传播多样性最大化快速查询方法，包括：

3、s1、获取社交网络图，基于顶点覆盖策略从所述社交网络图中选择地标节点集合，使得所述社交网络图中的每条边至少有一个端点被选为地标节点；

4、s2、对所述地标节点集合中的每个地标节点，预计算其信息扩散向量，所述信息扩散向量用于表征该地标节点对社交网络中至少一个社区的信息扩散能力；

5、s3、根据各所述地标节点及其对应的信息扩散向量构建标签索引，并存储所述标签索引；

6、s4、接收多样性最大化查询，所述查询包含候选节点集合和预算约束；

7、s5、响应于所述查询，基于所述标签索引构建下界估计函数，所述下界估计函数用于估计任意种子集合的信息扩散下界值；

8、s6、利用贪心算法，根据所述下界估计函数从所述候选节点集合中迭代选择种子节点，直至所选种子节点的数量达到所述预算约束；

9、s7、输出由所选种子节点构成的种子集合作为查询结果。

10、作为优选，s1中，所述顶点覆盖策略采用2-近似算法，具体包括：按任意顺序遍历未访问的边，将当前遍历到的边的一个端点加入地标节点集合，并标记所有与该端点相连的边为已访问，重复上述过程直至所有边均被访问。

11、作为优选，s2中，预计算信息扩散向量具体包括：对每个地标节点，采用蒙特卡洛模拟方法执行多次信息扩散模拟，统计各社区在每次模拟中被激活的节点数量，取平均值作为该地标节点对各社区的信息扩散期望值，得到所述信息扩散向量。

12、作为优选，s3中所述标签索引采用键值对格式存储，其中键为地标节点的标识符，值为该地标节点的信息扩散向量；所述标签索引存储于内存数据库或图数据库中。

13、作为优选，s5中，所述下界估计函数根据被种子节点激活的地标节点来计算信息扩散的下界值，其中任一节点被种子集合激活的概率基于该节点与种子集合中各节点之间边的信息扩散概率计算得到。

14、作为优选，s6中，所述贪心算法每次迭代选择使所述下界估计函数的边际增益最大的候选节点加入种子集合。

15、第二方面，提供了基于标签索引的信息传播多样性最大化快速查询系统，用于执行如第一方面任一所述的方法，包括：

16、获取模块，用于获取社交网络图，基于顶点覆盖策略从所述社交网络图中选择地标节点集合，使得所述社交网络图中的每条边至少有一个端点被选为地标节点；

17、预计算模块，用于对所述地标节点集合中的每个地标节点，预计算其信息扩散向量，所述信息扩散向量用于表征该地标节点对社交网络中至少一个社区的信息扩散能力；

18、构建模块，用于根据各所述地标节点及其对应的信息扩散向量构建标签索引，并存储所述标签索引；

19、接收模块，用于接收多样性最大化查询，所述查询包含候选节点集合和预算约束；

20、响应模块，用于响应于所述查询，基于所述标签索引构建下界估计函数，所述下界估计函数用于估计任意种子集合的信息扩散下界值；

21、选择模块，用于利用贪心算法，根据所述下界估计函数从所述候选节点集合中迭代选择种子节点，直至所选种子节点的数量达到所述预算约束；

22、输出模块，用于输出由所选种子节点构成的种子集合作为查询结果。

23、第三方面，提供了一种计算机存储介质，所述计算机存储介质内存储有计算机程序；所述计算机程序在计算机上运行时，使得计算机执行第一方面任一所述的方法。

24、第四方面，提供了电子设备，包括：

25、存储器，用于保存计算机程序；

26、处理器，用于执行所述计算机程序以实现如第一方面任一所述的方法。

27、本发明的有益效果是：

28、1．降低服务器cpu占用率与内存消耗：本发明将查询时间复杂度从近线性降低至，与网络规模n和边数m无关。由于查询阶段无需实时遍历全图或维护庞大的反向可达集，显著减少了服务器cpu计算开销和内存峰值占用，在高并发批量查询场景下可有效避免内存溢出和算力瓶颈。

29、2．降低高并发i/o阻塞风险：由于查询处理仅依赖预建的标签索引，单次查询无需访问磁盘或进行复杂的图遍历操作，大幅降低了磁盘i/o和网络i/o压力，使得系统能够稳定支撑大量并发查询请求。

30、3．近似质量保证：通过证明下界函数的单调性和子模性，本发明提供了的近似比保证，确保查询结果的质量。

31、4. 灵活可扩展：本发明的索引框架不依赖特定假设，可方便地扩展到主题感知、社区感知等变体问题。