On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks

Authors

  • Chuan Zhou Institute of Information Engineering, Chinese Academy of Sciences
  • Wei-Xue Lu Academy of Mathematics and Systems Science, Chinese Academy of Sciences
  • Peng Zhang University of Technology, Sydney
  • Jia Wu Centre for Quantum Computation & Intelligent Systems, University of Technology, Sydney
  • Yue Hu Institute of Information Engineering, Chinese Academy of Sciences
  • Li Guo Institute of Information Engineering, Chinese Academy of Sciences

DOI:

https://doi.org/10.1609/aaai.v30i1.10005

Keywords:

Differentially Resolving Set, Diffusion Source Inference, Networks

Abstract

In this paper we theoretically study the minimum Differentially Resolving Set (DRS) problem derived from the classical sensor placement optimization problem in network source locating. A DRS of a graph G = (V, E) is defined as a subset S ⊆ V where any two elements in V can be distinguished by their different differential characteristic sets defined on S. The minimum DRS problem aims to find a DRS S in the graph G with minimum total weight Σv∈Sw(v). In this paper we establish a group of Integer Linear Programming (ILP) models as the solution. By the weighted set cover theory, we propose an approximation algorithm with the Θ(ln n) approximability for the minimum DRS problem on general graphs, where n is the graph size.

AAAI 2016 Proceedings Cover

Downloads

Published

2016-02-21

How to Cite

Zhou, C., Lu, W.-X., Zhang, P., Wu, J., Hu, Y., & Guo, L. (2016). On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10005

Issue

Vol. 30 No. 1 (2016): Thirtieth AAAI Conference on Artificial Intelligence

Section

Technical Papers: Applications