An exact algorithm for the maximum probabilistic clique problem

Zhuqi Miao; Balabhaskar Balasundaram; Eduardo L. Pasiliao

doi:10.1007/s10878-013-9699-4

An exact algorithm for the maximum probabilistic clique problem

Zhuqi Miao, Balabhaskar Balasundaram, Eduardo L. Pasiliao

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

Original language	English
Pages (from-to)	105-120
Number of pages	16
Journal	Journal of Combinatorial Optimization
Volume	28
Issue number	1
DOIs	https://doi.org/10.1007/s10878-013-9699-4
State	Published - 1 Jan 2014
Externally published	Yes

Keywords

Branch-and-bound
Maximum clique problem
Probabilistic clique
Probabilistic programming

Access to Document

10.1007/s10878-013-9699-4

Fingerprint Dive into the research topics of 'An exact algorithm for the maximum probabilistic clique problem'. Together they form a unique fingerprint.

Cite this

@article{aed59629a7f745b3847b9cbcc64aa877,

title = "An exact algorithm for the maximum probabilistic clique problem",

abstract = "The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.",

keywords = "Branch-and-bound, Maximum clique problem, Probabilistic clique, Probabilistic programming",

author = "Zhuqi Miao and Balabhaskar Balasundaram and Pasiliao, {Eduardo L.}",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/s10878-013-9699-4",

language = "English",

volume = "28",

pages = "105--120",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - An exact algorithm for the maximum probabilistic clique problem

AU - Miao, Zhuqi

AU - Balasundaram, Balabhaskar

AU - Pasiliao, Eduardo L.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

AB - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

KW - Branch-and-bound

KW - Maximum clique problem

KW - Probabilistic clique

KW - Probabilistic programming

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

U2 - 10.1007/s10878-013-9699-4

DO - 10.1007/s10878-013-9699-4

M3 - Article

AN - SCOPUS:84903594187

VL - 28

SP - 105

EP - 120

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 1

ER -