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 | |
| State | Published - 1 Jan 2014 |
| Externally published | Yes |
Fingerprint
Keywords
- Branch-and-bound
- Maximum clique problem
- Probabilistic clique
- Probabilistic programming
Cite this
}
An exact algorithm for the maximum probabilistic clique problem. / Miao, Zhuqi; Balasundaram, Balabhaskar; Pasiliao, Eduardo L.
In: Journal of Combinatorial Optimization, Vol. 28, No. 1, 01.01.2014, p. 105-120.Research output: Contribution to journal › Article
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 -