On the minimum differentially resolving set problem for diffusion source inference in networks

Chuan Zhou; Wei-Xue Lu; Peng Zhang; Jia Wu; Yue Hu; Li Guo

On the minimum differentially resolving set problem for diffusion source inference in networks

Chuan Zhou, Wei-Xue Lu, Peng Zhang, Jia Wu, Yue Hu, Li Guo

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

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∈S w(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.

Original language	English
Title of host publication	AAAI 2016
Subtitle of host publication	Proceedings of the 30th AAAI Conference on Artificial Intelligence
Place of Publication	Palo Alto, CA
Publisher	Association for the Advancement of Artificial Intelligence
Pages	79-85
Number of pages	7
ISBN (Electronic)	9781577357605
Publication status	Published - 2016
Externally published	Yes
Event	30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, United States Duration: 12 Feb 2016 → 17 Feb 2016

Conference

Conference	30th AAAI Conference on Artificial Intelligence, AAAI 2016
Country/Territory	United States
City	Phoenix
Period	12/02/16 → 17/02/16

Keywords

Differentially Resolving Set
Diffusion Source Inferenc
Networks

Access to Document

https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12230

Cite this

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. In AAAI 2016: Proceedings of the 30th AAAI Conference on Artificial Intelligence (pp. 79-85). Association for the Advancement of Artificial Intelligence. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12230

@inproceedings{876afacb85fc42aea9f4e776fa50d59d,

title = "On the minimum differentially resolving set problem for diffusion source inference in 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∈S w(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.",

keywords = "Differentially Resolving Set, Diffusion Source Inferenc, Networks",

author = "Chuan Zhou and Wei-Xue Lu and Peng Zhang and Jia Wu and Yue Hu and Li Guo",

year = "2016",

language = "English",

pages = "79--85",

booktitle = "AAAI 2016",

publisher = "Association for the Advancement of Artificial Intelligence",

address = "United States",

note = "30th AAAI Conference on Artificial Intelligence, AAAI 2016 ; Conference date: 12-02-2016 Through 17-02-2016",

}

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. in AAAI 2016: Proceedings of the 30th AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, Palo Alto, CA, pp. 79-85, 30th AAAI Conference on Artificial Intelligence, AAAI 2016, Phoenix, United States, 12/02/16. <https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12230>

On the minimum differentially resolving set problem for diffusion source inference in networks. / Zhou, Chuan; Lu, Wei-Xue; Zhang, Peng et al.
AAAI 2016: Proceedings of the 30th AAAI Conference on Artificial Intelligence. Palo Alto, CA: Association for the Advancement of Artificial Intelligence, 2016. p. 79-85.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - On the minimum differentially resolving set problem for diffusion source inference in networks

AU - Zhou, Chuan

AU - Lu, Wei-Xue

AU - Zhang, Peng

AU - Wu, Jia

AU - Hu, Yue

AU - Guo, Li

PY - 2016

Y1 - 2016

N2 - 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∈S w(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.

AB - 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∈S w(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.

KW - Differentially Resolving Set

KW - Diffusion Source Inferenc

KW - Networks

UR - http://www.scopus.com/inward/record.url?scp=85007275572&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP140102206

M3 - Conference proceeding contribution

AN - SCOPUS:85007275572

SP - 79

EP - 85

BT - AAAI 2016

PB - Association for the Advancement of Artificial Intelligence

CY - Palo Alto, CA

T2 - 30th AAAI Conference on Artificial Intelligence, AAAI 2016

Y2 - 12 February 2016 through 17 February 2016

ER -

On the minimum differentially resolving set problem for diffusion source inference in networks

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this