### 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

*Journal of Combinatorial Optimization*,

*28*(1), 105-120. https://doi.org/10.1007/s10878-013-9699-4

}

*Journal of Combinatorial Optimization*, vol. 28, no. 1, pp. 105-120. https://doi.org/10.1007/s10878-013-9699-4

**An exact algorithm for the maximum probabilistic clique problem.** / Miao, Zhuqi; Balasundaram, Balabhaskar; Pasiliao, Eduardo L.

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 -