有符号图中的高效最大平衡CliPlex枚举

《IEEE Transactions on Knowledge and Data Engineering》：Efficient Maximal Balanced CliPlex Enumeration in Signed Graphs

平衡超 clique 模型在带符号图分析中的应用。针对传统平衡 clique 需完全负跨组连接的限制，提出 k-BCP 模型，通过 k-plex 理念放宽负连接约束，并设计基线算法结合分区方法和优化策略高效求解 NP 难问题，在 10 个真实网络中验证有效性。

　　

摘要：

在符号图分析中，平衡团模型近来受到了越来越多的关注。如果一个团可以被划分为两个不相交的子群，并且子群内部的连接为正，而子群之间的连接为负，则称该团是平衡的。然而，要求子群之间的连接完全为负过于严格，因为现实世界中的符号网络中正负边的分布往往是不平衡的，这可能导致一些重要社区被忽略。受此启发，我们利用了k-复形的概念，提出了一种新的模型，称为平衡kk-CliPlex（k-BCP），该模型放宽了平衡团中两个子群之间必须为负连接的要求。在本文中，我们的目标是枚举所有满足大小约束的最大k-BCPs，这被证明是一个NP难问题。为了解决这个问题，我们首先通过扩展现有的最大平衡团枚举方法并引入两种加速技术，提出了一个合理的基线算法。为了处理大型图，我们进一步引入了一种分割方法，该方法可以显著减少搜索空间，并提出了三种优化策略来过滤枚举过程中不必要的搜索分支。我们在10个真实世界网络上进行了全面实验，以证明所提出技术和模型的效率和有效性。

引言

在诸如社交网络[1]、生物信息学[2]和经济学[3]等各种领域，符号图作为一种关键的数据结构，已被用来建模复杂的关系。在符号图中，顶点表示实体，而边则带有正（+）或负（?）符号，这些符号表示实体之间的关系性质，例如信任[4]与不信任[5]、友谊[6]与敌对[7]。在符号网络分析中，平衡理论[6][7]作为探索个体之间结构关系的重要原则[8][9][10]，其基于“我的朋友的朋友是我的朋友”和“我的敌人的敌人是我的朋友”这一直觉。平衡理论认为，如果一个网络中的所有循环都包含零个或偶数个负边[11]，那么这个网络就是平衡的。具体来说，一个符号图G被认为是平衡的，如果它可以被划分为两个不相交的部分，且每个部分内的所有边都是正的，而两个部分之间的所有边都是负的。