本发明涉及社交网络分析和挖掘领域，具体涉及一种面向符号社交网络的对抗社区搜索方法及装置。
背景技术：
1、随着社交媒体、万维网搜索和知识库的发展，图数据管理受到了越来越多的关注，其核心任务之一是社区搜索。与传统社交网络不同，符号社交网络同时包含积极社交关系和消极社交关系，其可以描述单词网络之间同义关系与反义关系。给定一个查询点，为了寻找包含该查询点的两个对抗社区，引入一种平衡核，其要求两个社区之间的不存在积极社交关系，单个社区中不存在消极社交关系，且对两个对抗社区中的每个顶点，至少有个顶点与其保持积极社交关系，至少有个顶点与其保持消极社交关系。基于平衡核模型，设计一种面向符号社交网络的对抗社区搜索方法。
2、在实现本发明的过程中，发明人发现现有技术至少存在如下问题：
3、首先，当前符号社交网络中的社区模型一般只描述一个社区，而不是两个对抗的社区，因此导致只能找到查询点所在的社区，而不能同时找到与该社区对抗的社区。
4、另外，当前符号社交网络中的对抗社区模型一般不能同时保证社区的紧密性和对抗性，难以应用于实际社交网络的对抗社区搜索。
5、此外，部分当前符号社交网络中的社区模型约束条件过强，导致在真实符号社交网络中，基本不存在满足该社区模型约束的子图。
技术实现思路
1、针对上述技术问题以及本领域存在的不足之处，本发明提供了一种面向符号社交网络的对抗社区搜索方法及装置，利用符号社交网络拉普拉斯矩阵最小特征值与其平衡约束的关系，启发式地搜索一个满足平衡约束的子图；利用符号社交网络拉普拉斯最小特征值的估计公式，高效、准确地进行近似计算；验证当前删除的顶点是否可加回到社区中，尽可能保证社区的完整性。
2、一种面向符号社交网络的对抗社区搜索方法，包括步骤：
3、s11：获取符号社交网络和查询顶点；
4、s12：迭代删除获取的符号社交网络中满足a）、b）任一条件的顶点，完成度数约束：a）正度数小于正阈值；b）负度数小于负阈值；
5、s13：对当前符号社交网络中的任意一个顶点，计算其跟随集合，所述跟随集合为该顶点和因该顶点被删除而被级联删除的点的集合，进一步计算删除该跟随集合后的符号社交网络的拉普拉斯矩阵的最小特征值；遍历所述当前符号社交网络中的所有顶点，获得与这些顶点一一对应的最小特征值；
6、s14：采用使所述最小特征值降低速度最快的策略获取所述当前符号社交网络中的一个独立集合；
7、s15：在所述当前符号社交网络中删除所述独立集合中每一个顶点的跟随集合，将删除后的符号社交网络中查询顶点所在连通分量作为所得符号社交网络；
8、s16：所得符号社交网络若满足平衡条件，则将对抗社区初始化为所得符号社交网络，否则，跳转至步骤s13；所述满足平衡条件指：能够将所得符号社交网络的顶点集划分为两个集合，使得任何一条正边的两个端点不分别在两个集合中，且任何一条负边的两个端点不能在同一个集合中；
9、s17：检查步骤s15中删除过的所有顶点能否加回到对抗社区中，若加回到对抗社区中后不影响平衡性约束和度数约束，则将其加回到对抗社区中，将步骤s15中删除过的所有顶点处理完毕后，获得最终的对抗社区。
10、在一些实施例中，步骤s12中，完成度数约束的符号社交网络中的任意一个顶点的正度数不小于给定正阈值，负度数不小于给定负阈值。
11、在一些实施例中，步骤s13中，对当前符号社交网络中的任意一个顶点，拷贝当前符号社交网络中的正度数列表和负度数列表以维护该顶点的跟随集合。
12、在一些实施例中，步骤s13中，所述的对当前符号社交网络中的任意一个顶点，计算其跟随集合具体包括：
13、（1）对任意一个顶点的跟随集合进行初始化，将该顶点加入到跟随集合中，对顶点的正邻居节点，在正度数列表中将其正度数减1，对顶点的负邻居节点，在负度数列表中将其负度数减1；
14、（2）将顶点的正邻居节点中正度数小于的顶点和负邻居节点中负度数小于的顶点的集合加入到跟随集合中；
15、（3）遍历集合，对其中任意一个顶点，若顶点第一次被加入到跟随集合中，则重复与顶点相同的操作，直到当前访问的顶点与顶点之间的跳数达到阈值，得到最终的跟随集合。
16、在一些实施例中，步骤s13中，使用最小特征值上界计算删除跟随集合后的符号社交网络的拉普拉斯矩阵的最小特征值，计算公式为：
17、，
18、其中，表示顶点索引，和分别表示删除任意一个顶点的跟随集合前符号社交网络的拉普拉斯矩阵的最小特征值和对应的单位特征向量，、、分别表示单位特征向量中索引为、、的元素，和分别表示索引为的顶点的邻居集合和邻居个数，表示拉普拉斯矩阵第行、第列的元素。
19、在一些实施例中，步骤s14具体包括步骤：
20、s41：将步骤s13获得的所有最小特征值组合为一个维向量，为所述当前符号社交网络中的顶点数量，从所述当前符号社交网络中选取与中值最小的一维对应的顶点，将独立集合初始化，仅包含一个元素，即顶点；
21、s42：从所述当前符号社交网络中按照对应向量中元素从小到大的顺序依次选取与独立集合中顶点无连边的顶点，加入到独立集合中，形成最终的独立集合。
22、在一些实施例中，所述独立集合中的顶点数量为100。
23、本发明还提供了一种计算机设备，包括存储器和处理器，所述存储器用于存储计算机程序，所述处理器用于执行所述存储器中存储的计算机程序，所述计算机程序运行时使得所述处理器执行所述的面向符号社交网络的对抗社区搜索方法。
24、本发明还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储程序或指令，在程序或指令被计算机设备执行的情况下，使得计算机设备执行所述的面向符号社交网络的对抗社区搜索方法。
25、本发明还提供了一种计算机程序产品，包括计算机程序，在计算机程序被计算机设备执行的情况下，使得计算机设备执行所述的面向符号社交网络的对抗社区搜索方法。
26、本发明还提供了一种面向符号社交网络的对抗社区搜索装置，包括：
27、获取模块，用于获取符号社交网络和查询顶点；
28、预处理模块，用于迭代删除获取模块获取的符号社交网络中满足a）、b）任一条件的顶点，完成度数约束：a）正度数小于正阈值；b）负度数小于负阈值；
29、计算模块，用于：i）对当前符号社交网络中的任意一个顶点，计算其跟随集合，所述跟随集合为该顶点和因该顶点被删除而被级联删除的点的集合，进一步计算删除该跟随集合后的符号社交网络的拉普拉斯矩阵的最小特征值；遍历所述当前符号社交网络中的所有顶点，获得与这些顶点一一对应的最小特征值；ii）采用使所述最小特征值降低速度最快的策略获取所述当前符号社交网络中的一个独立集合；iii）在所述当前符号社交网络中删除所述独立集合中每一个顶点的跟随集合，将删除后的符号社交网络中查询顶点所在连通分量作为所得符号社交网络；iv）所得符号社交网络若满足平衡条件，则将对抗社区初始化为所得符号社交网络，否则，跳转至i）；所述满足平衡条件指：能够将所得符号社交网络的顶点集划分为两个集合，使得任何一条正边的两个端点不分别在两个集合中，且任何一条负边的两个端点不能在同一个集合中；
30、验证模块，用于检查计算模块iii）中删除过的所有顶点能否加回到对抗社区中，若加回到对抗社区中后不影响平衡性约束和度数约束，则将其加回到对抗社区中，将计算模块iii）中删除过的所有顶点处理完毕后，获得最终的对抗社区。
31、所述的面向符号社交网络的对抗社区搜索装置在运行时可执行所述的面向符号社交网络的对抗社区搜索方法。
32、本发明与现有技术相比，有益效果有：
33、本发明针对符号社交网络构建了一种高效且近似程度高的对抗社区搜索的方法。本发明利用符号社交网络拉普拉斯矩阵最小特征值与其平衡约束的关系，启发式地搜索一个满足平衡约束的子图；利用符号社交网络拉普拉斯最小特征值的估计公式，高效、准确地进行近似计算；验证当前删除的顶点是否可加回到社区中，尽可能保证社区的完整性。
1.一种面向符号社交网络的对抗社区搜索方法，其特征在于，包括步骤：
2.根据权利要求1所述的面向符号社交网络的对抗社区搜索方法，其特征在于，步骤s12中，完成度数约束的符号社交网络中的任意一个顶点的正度数不小于给定正阈值，负度数不小于给定负阈值。
3.根据权利要求2所述的面向符号社交网络的对抗社区搜索方法，其特征在于，步骤s13中，对当前符号社交网络中的任意一个顶点，拷贝当前符号社交网络中的正度数列表和负度数列表以维护该顶点的跟随集合；
4.根据权利要求1所述的面向符号社交网络的对抗社区搜索方法，其特征在于，步骤s13中，使用最小特征值上界计算删除跟随集合后的符号社交网络的拉普拉斯矩阵的最小特征值，计算公式为：
5.根据权利要求1所述的面向符号社交网络的对抗社区搜索方法，其特征在于，步骤s14具体包括步骤：
6.根据权利要求1或5所述的面向符号社交网络的对抗社区搜索方法，其特征在于，所述独立集合中的顶点数量为100。
7.一种计算机设备，包括存储器和处理器，所述存储器用于存储计算机程序，所述处理器用于执行所述存储器中存储的计算机程序，其特征在于，所述计算机程序运行时使得所述处理器执行权利要求1~6任一项所述的面向符号社交网络的对抗社区搜索方法。
8.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储程序或指令，在程序或指令被计算机设备执行的情况下，使得计算机设备执行权利要求1~6任一项所述的面向符号社交网络的对抗社区搜索方法。
9.一种计算机程序产品，包括计算机程序，其特征在于，在计算机程序被计算机设备执行的情况下，使得计算机设备执行权利要求1~6任一项所述的面向符号社交网络的对抗社区搜索方法。
10.一种面向符号社交网络的对抗社区搜索装置，其特征在于，包括：
