科研之友
微信
新浪微博
Facebook
分享链接
摘要
图子集选取问题旨在从图节点集中采样少部分代表性节点，利用观测的节点信号值去重构原始图信号。在资源有限的情况下，可以降低数据维度和计算复杂度，提高对复杂多变图结构的适应性，从而为网络数据的传输处理提供高效的技术支撑。现有的确定性算法大多采用贪心优化，后序采样点的选择依赖于前序已采样节点，对初始值敏感，且可能陷入局部最优；同时，大多数频域算法没有考虑顶点域内采样集节点的空间关系。该文提出基于局部算子的两步采样算法，通过构建节点局部算子的内积完全图来度量采样节点的距离，首先求解标准图割，将节点集按距离划分指定个数簇；其次，在各个簇内依据稀疏性度量选择最优点，从而生成最终的采样集。该算法同时结合了频域与节点域的信息，并使得采样可并行执行。在多种图场景下与多种代表性算法相比，该算法都可以取得最优或相近的重构效果。
- 单位
