联手信息系统专业委员会：“图结构稳定性”术语发布 | CCF术语快线

InfoBox：

中文名：图结构稳定性

外文名：Graph Structural Stability

简写：GSS

学科：图数据库

实质：利用图数据的结构表现，衡量图所代表的网络的稳定性

基本简介：

大规模网络通常被模式化为图结构，其稳定性表示相应网络维持其服务水平，以及防御外部攻击的能力。图稳定性作为一项重要图结构指标，其研究在不同的应用领域受到广泛关注，包括社交网络、金融、生物领域等。通过图结构稳定性的高效计算，可以实时掌握图结构稳定性的动态，采取合适的策略来增强或维护图稳定性，如通过激励手段来增强关键用户的参与度，阻止重要用户的流失等。

研究意义：

近期的图结构稳定性研究工作起源于Friendster社交网络的崩塌研究。基于真实崩塌数据的研究发现图结构稳定性与网络活跃程度高度相关[1]，例如大量紧密相连的用户群体（较好的结构稳定性）往往表明网络整体用户比较活跃。Friendster曾经非常活跃，在21世纪早期拥有超过1亿用户，但是由于持续的用户参与度降低以及用户流失，该网络停止服务。在Friendster崩塌的过程中，其图结构稳定性相应持续下降。

图结构稳定性的计算研究具有高度的应用潜力，更多应用示例包括（a）电商市场：电商平台的参与者（买家、卖家）自然组成一种图结构，其稳定性是平台运营的关键指标。通过计算电商网络的稳定性，我们可以监测平台运行态势并且制定合理的运营决策；（b）网络安全：稳定性计算可以聚焦于局部的图数据，如社交网络中传播谣言的社群。针对这些社群进行稳定性计算可以发现社群中的关键用户和连接，采取应对措施阻止谣言的进一步传播。此外，针对P2P网络的非法内容传播所组成的局部图结构数据，稳定性计算也可以发现关键节点和连接，阻止非法内容的传播；（c）生态系统：不同的物种通过交互关系（如捕食关系）所连接，自然组成图结构并且呈现相应的结构稳定性，其中关键生物的消失会导致生态系统稳定性的下降，甚至系统崩塌。图稳定性计算能够监控生态系统网络的发展和衰退，推荐合理策略以维护生态多样性[2]；（d）金融市场：在e-MID同行拆借市场中，针对交易数据组成的图结构，采用图稳定性计算（如中心性指标）可以指导银行的借出借入策略[3]。

研究发展概况：

虽然图结构稳定性应用于不同领域，其面向的本质问题是共通的：使用图分析方法对网络稳定性进行合理模式化，并且对稳定性动态进行高效计算。图结构稳定性的研究有三个基础科学问题：图稳定性本身的计算（实时计算当前网络的结构稳定性）；图稳定性增强的计算（加强重要节点和连接，以增强图结构稳定性）；和图稳定性防御的计算（寻找重要节点和连接进行防护，以抵挡针对图结构稳定性的攻击）。

近年来，基于稠密子图模型的图结构稳定性研究受到广泛关注, 包括基于k-core、k-truss等模型的计算。不同于图鲁棒性/抗毁性指标的研究，如节点连通性、中心性、聚集系数、图直径等[4-6]，稠密子图计算考虑每个用户在网络的参与度，例如k-core计算赋予每个节点一个独特的coreness值。由于k-core计算的退化特性能够有效拟合网络崩塌的动态，基于真实社交网络结构数据的研究表明：一个用户的coreness值是衡量用户网络参与度的“最佳实践”[7, 8]。因此，图结构稳定性可以用全图coreness聚合值准确表达。

针对稠密子图本身的计算，现有的理论和算法集中于静态图数据的分析, 仅有部分工作研究了稠密子图的动态维护问题[9]。对于稳定性增强问题，现有工作通过图操作（如节点增强、增加新边）使得特定模型的稳定性数值最大化[10-12]，其中anchored coreness问题致力于增强一定数量的节点最大化coreness收益[8]。对于图稳定性防御问题，关键节点和连接的损失会导致稳定性指标最小化，一些工作致力于保护这些节点和连接来抵挡稳定性攻击[13-16]，其中collapsed coreness问题致力于保护一定数量的关键节点避免coreness损失[14]。此外，基于稠密子图模型，也有一些工作研究社群的稳定性计算[17, 18]。

图结构稳定性的研究是图数据领域的一个新兴方向，未来研究热点包括多种稳定性指标的有效性研究，面向动态图数据的稳定性更新算法的设计，以及图结构稳定性系统的开发等。

参考文献