A Controlled Sensing Approach to Graph Classification
A Controlled Sensing Approach to Graph Classification
复制标题
图分类的受控感知方法
DOI：
--
复制
发表时间：
2013
影响因子：
5.4
通讯作者：
V. Veeravalli
中科院分区：
文献类型：
--
作者：
Jonathan G. Ligo;George K. Atia;V. Veeravalli
通过节点的部分观察对连通性进行图分类的问题被提出为具有受控感知的复合假设检验问题。节点处的观察是根据概率模型绘制的完整图上与该节点相关的边的子集，该概率模型是固定基础图的函数。连接性通过平均节点度来衡量，并根据阈值进行分类。在 Erdös-Rènyi 图上导出并模拟受控传感测试的简单近似，以将误差概率描述为预期停止时间的函数。该测试还通过长尾侏儒鸟社会结构的现实示例进行了实验验证。结果表明，所提出的测试在分类误差和测量次数之间实现了有利的权衡。此外，该测试优于现有方法，尤其是在目标错误率较低的情况下。此外，所提出的测试实现了最佳误差指数。
The problem of classifying graphs with respect to connectivity via partial observations of nodes is posed as a composite hypothesis testing problem with controlled sensing. An observation at a node is a subset of edges incident to the node on the complete graph drawn according to a probability model, which is a function of a fixed underlying graph. Connectivity is measured through average node degree and is classified with respect to a threshold. A simple approximation of the controlled sensing test is derived and simulated on Erdös-Rènyi graphs to characterize the error probabilities as a function of the expected stopping times. The test is also experimentally validated on a real-world example of the social structure of Long-Tailed Manakins. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements. Furthermore, the test outperforms existing approaches, especially at low target error rates. In addition, the proposed test achieves the optimal error exponent.