寻找社会脆弱群体：最小K三角形断开组在在线社交网络中的应用

"这篇论文探讨了在线社交网络中寻找社会脆弱群体的问题，提出了新的概念——最小K三角形断开组（MKTG），并设计了相应的算法TARA和TRA-ADV来解决这个问题。" 在当前的在线社交网络环境中，如Facebook、LinkedIn等，社区检测和活动协调的研究日益受到重视。然而，尽管大多数工作都集中在发现社交网络中的紧密群体，即那些成员间存在强连接的子图，但社会脆弱群体（Socially Tenuous Groups, STGs）的识别同样具有重要的应用价值。STGs是指成员之间社会交互较少、关系较弱的子图，比如在心理教育团体的构建或审稿人选择等场景中，这样的群体能够避免内部形成强大的亚群体，从而保证活动的公平性和有效性。 论文中，作者引入了“K三角”这一概念，用于量化群组中的最小社会连接度。随后，他们提出了一个新的研究问题——最小K三角形断开组（Minimum K-Triangle Group, MKTG），目标是在在线社交网络中寻找这样的社会脆弱群体。他们证明了在任意图上，MKTG问题是NP难且无法近似求解的，但在阈值图中可以使用多项式时间算法解决。 为了应对一般图上的MKTG问题，作者设计了两种算法：TARA和TRA-ADV。这两种算法基于图论原理，能够在保持效率的同时提供高质量的解决方案。通过在七个真实数据集上的实验，结果显示提出的算法在效率和解决方案质量上均优于现有的方法。 以心理教育团体的建立为例，理想的STG应由相互之间关系不紧密的成员组成，以避免形成可能影响治疗过程的小圈子。传统的仅考虑边数减少的方法并不足够，因为即使没有直接的社会关系，成员之间可能存在间接联系，这可能会影响群体的动态平衡。论文中的例子展示了如何使用MKTG的概念来避免这种问题，确保形成适合心理治疗的STG。 这篇论文为理解和处理在线社交网络中的社会脆弱群体提供了新的理论基础和实用工具，对于社区分析和特定应用场景的优化具有重要意义。